\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 2021}  \\ [-0.3cm]
  \begin{center} 
    {\Large Problem Set 4}
  \end{center}
  {\bf Due:} May 24, 2021 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/21sp/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 Consider a hash function $H:\calX\to\calY$, and the NP-relation $\calR_n$ for knowledge of $n$
    pre-images of $H$. Formally, $\calR_n$ has inputs space $\calY^n$, witness
    space $\calX^n$, and is defined by
    \(
    \{ (
      w \in \calX^n
      ,
      y \in \calY^n
      ):
        (H(w_1) = y_1)
        \land (H(w_2) = y_2)
        \land \cdots
        \land (H(w_n) = y_n)
      \}
    \).
    A SNARG for $\calR_n$ must have $o(n)$ verification time.

\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 $t<n$. The shareholders
suspect that the dealer secretly holds a grudge against one of them and has
given that person an invalid share, inconsistent with the rest of the shares
(i.e., the dealer runs $(s_1,\dotsc,s_n)\gets G(n,t,\alpha)$, gives $s_j'\neq
s_j$ to shareholder $j$ and $s_i$ to shareholder $i\neq j$.) In this problem, we
assume that all shareholders are honest.
  
\begin{enumerate}[label=(\alph*), leftmargin=*]   
\item Show that if they are willing to reveal all their shares, the shareholders
can detect if one of them has indeed been given an invalid share.
\end{enumerate}

We would like the shareholders to be able to detect an invalid share
\emph{without having to reveal their shares}. To do this, consider the following
modification to Shamir's secret-sharing scheme: 

\begin{figure}[H]
\begin{framed}
  Let $\G$ be a cyclic group of prime order $q>n$, 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 enable 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{Compiling to R1CS [10 pts]}
  The SNARG discussed in class (``Marlin-Lite'')
  operates on relations expressed as rank-1 constraint systems (R1CSs).
  Recall that an R1CS instance comprises a set of variables, $\{z_1, \ldots z_n\}$ in a finite field $\F$,
  and constraints of the form
  \(
  \left( a_0 + \sum_{i=1}^n a_iz_i \right)
  \left( b_0 + \sum_{i=1}^n b_iz_i \right)
  =
  c_0 + \sum_{i=1}^n c_iz_i
  \)
  where $a_i, b_i, c_i$ are constants.
  Thus, each constraint requires the product of two linear combinations of
  variables to equal a third linear combination.

  To express relations defined in terms of booleans or fixed-width
  integers (like in the C programming language), these objects must be encoded as field elements,
  and operations over them must be expressed as rank-1 constraints.
  %
  In this problem, we'll consider booleans
  encoded as $0\in\F$ (false) or $1\in\F$ (true).
  %
  For a field element $x$ which is bit-valued (zero or one),
  let $\mathsf{bool}(x)$ denote the corresponding boolean.

  In each part you're given
  some inputs,
  assumptions that you can make about those inputs,
  and desired outputs.
  %
  You should write the rank-1 constraints
  necessary to ensure that the
  outputs have the desired property,
  given the assumptions about the inputs.
  %
  You may introduce new witness variables if needed.

  Unless otherwise noted, each part requires only one or two constraints
  (you may use more if you wish).
  \textbf{[Extra Credit (1pt)]}
  If you use (what we believe to be) the minimal number of constraints in parts
  (a) through (j), you'll get 1 point of extra credit.

  You can write your constraints without writing the $a, b, c$ vectors
  explicitly.
  That is, $(x - 5y)x = z$ is an acceptable way of writing a constraint over
  variables $x, y, z$.


  \begin{enumerate}[label=(\alph*), leftmargin=*]
    \item
      \textbf{FORCE-BIT}:
      Given $x \in \F$,
      ensure
      it is bit-valued
      (there is no output).
      This can be done with one constraint.
    \item
      \textbf{NOT}:
      Given bit-valued $x \in \F$,
      ensure
      $r \in \F$ is bit-valued
      and
      $\mathsf{bool}(r) = \lnot \mathsf{bool}(x)$
      \unskip.
      This can be done with one constraint.

    \item
      \textbf{AND}:
      Given bit-valued $x,y \in \F$,
      ensure
      $r \in \F$ is bit-valued
      and
      $\mathsf{bool}(r) = (\mathsf{bool}(x) \land \mathsf{bool}(y))$
      \unskip.
      This can be done with one constraint.

    \item
      \textbf{OR}:
      Given bit-valued $x,y \in \F$,
      ensure
      $r \in \F$ is bit-valued
      and
      $\mathsf{bool}(r) = (\mathsf{bool}(x) \lor \mathsf{bool}(y))$
      \unskip.
      This can be done with one constraint.
    \item
      \textbf{XOR}:
      Given bit-valued $x,y \in \F$,
      ensure
      $r \in \F$ is bit-valued
      and
      $\mathsf{bool}(r) = (\mathsf{bool}(x) \oplus \mathsf{bool}(y))$
      \unskip.
      This can be done with one constraint.
    \item
      \textbf{BIT-EQUAL}:
      Given bit-valued $x,y \in \F$,
      ensure
      $r \in \F$ is bit-valued
      and
      $\mathsf{bool}(r) = (\mathsf{bool}(x) \iff \mathsf{bool}(y))$
      \unskip.
      This can be done with one constraint.
    \item
      \textbf{FORCE-NON-ZERO}:
      Given $x\in\F$,
      ensure
      that is it non-zero
      (there is no output).
      Briefly explain why your constraints provide this guarantee.
      This can be done with one constraint.

      \textit{Hint: what value can the prover provide that only exists for
      non-zero elements? Write a constraint to check the correctness
      of this value.}
    \item
      \textbf{IS-ZERO}:
      Given $x\in\F$
      ensure
      $r \in \F$ is bit-valued
      and
      $\mathsf{bool}(r)$ is true iff
      $x$ is zero.
      Briefly explain why your constraints provide this guarantee.
      This can be done with two constraints.
    \item
      \textbf{EQUAL}:
      Given $x,y \in \F$,
      ensure
      $r \in \F$ is bit-valued
      and
      $\mathsf{bool}(r)$ is true iff
      $x=y$.
      Briefly explain why your constraints provide this guarantee.
      This can be done with two constraints.
    \item
      %{[\textbf{Extra Credit (2pts.)}]}
      \textbf{$n$-ary-AND}
      Given 
      bit-values $x_1, \ldots, x_n \in \F$,
      ensure
      $r \in \F$ is bit-valued
      and
      $\mathsf{bool}(r) = (\mathsf{bool}(x_1) \land \cdots \land \mathsf{bool}(x_n))$.
      Briefly explain why your constraints provide this guarantee.
      This can be done with two constraints.

      You may assume that $n \ll |\F|$, and you may use only $O(1)$ constraints.
    \item
      {[\textbf{Extra Credit (2pts.)}]}
      \textbf{$n$-ary-XOR}
      Given 
      bit-values $x_1, \ldots, x_n \in \F$,
      ensure
      $r \in \F$ is bit-valued
      and
      $\mathsf{bool}(r) = \mathsf{bool}(x_1) \oplus \cdots \oplus \mathsf{bool}(x_n)$.
      Briefly explain why your constraints provide this guarantee.

      You may assume that $n \ll |\F|$, and you may use only $O(\log n)$ constraints.
  \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}
