\documentclass[11pt]{article}
\usepackage[margin=0.75in]{geometry}
\input{latexdefs}
\usepackage{chngcntr}
%\counterwithin*{equation}{section}
\newtheorem*{defn*}{Definition}
\begin{document}
\newlength{\boxwidth}
\setlength{\boxwidth}{\textwidth}
\addtolength{\boxwidth}{-2cm}
\noindent\framebox[\textwidth]{
\begin{minipage}[t]{\boxwidth}
{\bf CS 355: Topics in Cryptography \hfill Spring 2020} \\ [-0.3cm]
\begin{center}
{\Large Problem Set 4}
\end{center}
{\bf Due:} June 1, 2020 at 11:59pm
\end{minipage}}
\vspace{0.7cm}
\noindent \textbf{Instructions:} You {\bf must} typeset your solution in LaTeX
using the provided template:
\begin{center}
\url{https://crypto.stanford.edu/cs355/20sp/homework.tex}
\end{center}
\noindent \textbf{Submission Instructions:} You must submit your problem set via
\href{https://www.gradescope.com/courses/84284}{Gradescope}. Note that
Gradescope requires that the solution to each problem starts on a \textbf{new
page}.
\medskip
\noindent \textbf{Bugs:} We make mistakes! If it looks like there might be a
mistake in the statement of a problem, please ask a clarifying question on
Piazza.
\hrule
\problem{Conceptual Questions [8 points]}
\begin{enumerate}[label=(\alph*), leftmargin=*]
\item Securely computing a function $f\colon \zo^n\times \zo^m \to \zo$ using
Yao's protocol (as described in lecture), requires the two parties to
exchange at most $O(n+m)$ bits in the worst case.
\item There exists a linear polynomial over $\Z_{6}$ that intersects with each
of the points $(0, 0), (2,1) \in \Z_{6}^2$.
\item You and your friends want to determine which one of you has the lowest
salary. You design and run a protocol, at the end of which all your friends
learn that their Big 4 salaries$\textsuperscript{TM}$ are higher than yours.
This blatant invasion of your privacy could have been avoided if you had used a
proper maliciously-secure MPC protocol.
\item Suppose $n$ parties give their data to a trusted curator, who answers an
analyst's query $q$ using an $\epsilon$-differentially private mechanism $M$. If
the $n$ parties do not want to trust the curator, but still retain
$\epsilon$-differential privacy, they can use a secure MPC protocol where $n+1$
parties (the data holders and the analyst) jointly compute $M$ over the $n$ data
points and query $q$.
\end{enumerate}
\problem{Verifiable Secret Sharing [10 points]}
Consider a dealer who wants to share a secret $\alpha$ between $n$ shareholders
using a $t$-out-of-$n$ secret-sharing scheme where $tn$, and let $g,h$ each be a
generator of $\G$.
\begin{enumerate}
\item The dealer chooses $\beta,a_1,b_1,\dotsc,a_{t-1},b_{t-1}\getsr\Z_q$ and
constructs the polynomials $A(x)=\alpha+a_1x+a_2x^2+\dots+a_{t-1}x^{t-1}$ and
$B(x)=\beta+b_1x+b_2x^2+\dots+b_{t-1}x^{t-1}$ over $\Z_q$.
\item The dealer creates $t$ Pedersen commitments $c_0,c_1,\dots,c_{t-1}\in\G$
where $c_o=\Comm(\alpha;\beta)=g^\alpha h^\beta$ and
$c_j=\Comm(a_j;b_j)=g^{a_j}h^{b_j}$ for $j\in[t-1]$. The dealer publicly
broadcasts all the commitments to all the shareholders.
\item The dealer creates $n$ shares $\left\{(i,s_i,r_i)\right\}_{i=1}^n$,
where $s_i=A(i)$ and $r_i=B(i)$ are computed over $\Z_q$. The dealer privately
sends each of the $n$ shareholders her own share.
\end{enumerate}
\end{framed}
\end{figure}
\begin{enumerate}[label=(\alph*), leftmargin=*]
\addtocounter{enumi}{1}
\item Describe a verification routine that allows the shareholders to jointly
verify that all the shares given to them are valid without having to reveal
them.
\item \label{part:hide} Prove that the protocol preserves the secrecy of the
secret $\alpha$ against any coalition of fewer than $t$ shareholders.
[\textbf{Hint:} Specify the view of any coalition of $t-1$ shareholders and
then prove this view is distributed independently of the secret $\alpha$.]
\item \textbf{Extra Credit [5 points].} \label{part:bind} Prove that if a
dealer can trick the shareholders into accepting an invalid set of shares it
can solve the disrete log of $h$ with respect to $g$.
\end{enumerate}
\problem{Generating Beaver Multiplication Triples [15 points]}
Recall from lecture that Beaver multiplication triples enables general
multiparty computation on secret-shared data. In this problem, we will explore
two methods that can be used to generate Beaver multiplication triples. For
simplicity, we will just consider the two-party setting and we will generate
Beaver multiplication triples over the binary field $\Z_2$ (where addition
corresponds to xor). To be precise, we first describe an ``idealized process''
for generating a single multiplication triple. In this ``idealized process'', a
trusted party generates the triple and then distributes the shares of the triple
to the two parties Alice and Bob.
\begin{enumerate}
\item The trusted party chooses $a, b \getsr \Z_2$ and computes $c = ab \in
\Z_2$.
\item The trusted party distributes a 2-out-of-2 secret sharing of $a$, $b$,
and $c$ to Alice and Bob. Specifically, the trusted party samples $r_a, r_b,
r_c \getsr \Z_2$ and gives $r_a, r_b, r_c$ to Alice. The trusted party then
computes $s_a = a \oplus r_a$, $s_b = b \oplus r_b$, and $s_c = c \oplus r_c$,
and gives $s_a, s_b, s_c$ to Bob.
\end{enumerate}
By construction $[a] = (r_a, s_a)$ is an additive secret-sharing of $a$, $[b] =
(r_b, s_b)$ is an additive secret-sharing of $b$, and $[c] = (r_c, s_c)$ is an
additive secret-sharing of $c$. Moreover, $c = ab$, so $([a], [b], [c])$ is a
valid Beaver multiplication triple.
\medskip
\noindent We will show how Alice and Bob can generate these Beaver triples
without relying on a trusted party. Throughout this problem, you may assume that
Alice and Bob are ``honest-but-curious'' (namely, they follow the protocol
exactly as described, but may try to infer additional information from the
protocol transcript---this is the model that we considered in lecture).
\begin{enumerate}[label=(\alph*), leftmargin=*]
\item Show how Alice and Bob can generate a Beaver multiplication triple using
Yao's protocol.\footnote{You may use the variant of Yao's protocol where only
one party receives output (and the other party learns nothing).} Your
construction should not make any modifications to the internal details of Yao's
protocol (in fact, any secure two-party computation protocol can be used here).
Then, give an {\em informal} argument why your protocol is correct and secure.
[\textbf{Hint:} To apply Yao's protocol, you will need to come up with a
two-party functionality $f$ that Alice and Bob will jointly compute. Try
letting Alice's inputs to $f$ be her shares $(r_a, r_b, r_c)$, which she
samples uniformly at random at the beginning of the protocol.]
\item Show how Alice and Bob can use a {\em single invocation} of an
$1$-out-of-$4$ oblivious transfer (OT) protocol (on $1$-bit messages) to
generate a Beaver multiplication triple. Give an {\em informal} argument why
your protocol is correct and secure. (In a $1$-out-of-$n$ OT, the sender has
$n$ messages $m_1, \ldots, m_n$, while the receiver has a single index $i \in
[n]$. At the end of the protocol execution, the sender learns nothing while the
receiver learns $m_i$ (and nothing else). The formal definitions of sender and
receiver privacy are the analogs of those presented in lecture.)
[\textbf{Hint:} Try using OT to directly evaluate the functionality $f$ you
constructed from Part~(a).]
\item Let $\ell \in \N$ be a constant. Show how to build a $1$-out-of-$2^\ell$
OT protocol (on $1$-bit messages) using $\ell$ invocations of an $1$-out-of-$2$
OT protocol (on $\lambda$-bit messages) together with a PRF $F \colon
\zo^\lambda \times \zo^\ell \to \zo$. Here, $\zo^\lambda$ is the key-space of
the PRF and $\zo^\ell$ is the domain of the PRF. Then, give an {\em informal}
argument for why your protocol satisfies correctness, sender privacy, and
receiver privacy. [\textbf{Hint:} Start by having the sender sample $2 \ell$
independent PRF keys. The sender will use these keys to blind each of its
messages $m_1, \ldots, m_{2^\ell}$.]
\end{enumerate}
\problem{Local Differential Privacy [10 points]}
The differential-privacy model we saw in class, where a trusted curator
aggregates all the data and then randomizes responses to queries, is also called
the \emph{central model} of differential privacy.
In the \emph{local model} of differential privacy, the users do not want to
trust the aggregator, so they each randomize their own data locally, before
sending it to the aggregator. We'll look at a very simple local DP algorithm
called \emph{Randomized Response} (RR), which was proposed by Warner in 1965,
four decades before differential privacy was invented! The goal of RR is to
collect sensitive statistics (e.g., ``how many people do drugs'') while allowing
each individual participant in the survey some amount of \emph{deniability}.
Formally, each of the $n$ users holds a private bit $b_i\in \{0,1\}$. The
quantity we are interested in estimating is $a \coloneqq \frac1n\sum_{i=1}^n
b_i$. Consider the following RR mechanism, that is run independently by each
user:
\begin{itemize}[itemsep=0pt, label=-]
\item Flip two unbiased coins.
\item If the first coin is heads, send $b_i$ to the aggregator.
\item Otherwise, look at the second coin:
\begin{itemize}[topsep=0pt,itemsep=0pt, label=-]
\item If heads, send $0$ to the aggregator.
\item If tails, send $1$ to the aggregator.
\end{itemize}
\end{itemize}
\begin{enumerate}[label=(\alph*), leftmargin=*]
\item Show that RR guarantees $\epsilon$-differential privacy for
$\epsilon=\ln(3)$ for each individual user's bit.
\item Let $\hat{b}_i$ be the $i$-th user's randomized response. Show that the
untrusted aggregator that receives all these noisy bits can compute an
unbiased estimate $\hat{a}$ of $a$ (i.e., $\Exp[\hat{a}] = a$).
\item Show that the estimation error $\hat{a} - a$ has standard deviation
$O(1/\sqrt{n})$.
\item How much worse is this than what we can achieve in the central model?
Suppose all users send their bits $b_i$ to a trusted curator that uses the
Laplace mechanism to output a noisy estimate $\hat{a}_{\text{c}}$ of $a$ that
is $\ln(3)$-differentially private. Show that the estimation error
$\hat{a}_{\text{c}}-a$ has standard deviation $O(1/n)$.
\end{enumerate}
\begin{problem}{Time Spent [3 points for answering]}
How long did you spend on this problem set? This is for calibration purposes,
and the response you provide will not affect your score.
\end{problem}
\paragraph{Optional Feedback [0 points].} Please answer the following questions
to help us design future problem sets. You do not need to answer these
questions, and if you would prefer to answer anonymously, please use this
\href{https://stanforduniversity.qualtrics.com/jfe/form/SV_6XTKIK2cWZyqpRr}{form}.
However, we do encourage you to provide us feedback on how to improve the course
experience.
\begin{enumerate}[label=(\alph*), leftmargin=*]
\item What was your favorite problem on this problem set? Why?
\item What was your least favorite problem on this problem set? Why?
\item Do you have any other feedback for this problem set?
\item Do you have any other feedback on the course so far?
\end{enumerate}
\end{document}