\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 3}
  \end{center}
  {\bf Due:} May 10, 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 [10 points]}

For each of the following statements, say whether it is 
TRUE or FALSE. Write \textit{at most one sentence} to justify
your answer.

\begin{enumerate}[label=(\alph*), leftmargin=*]
	\item Let $\langle P, V \rangle$ be a zero-knowledge interactive protocol for some language. The protocol has perfect completeness and soundness error $1/3$. Which of the following are true:
	\begin{enumerate} 
		\item[i] A malicious verifier interacting with an honest prover will always accept a true statement.
		\item[ii] An honest verifier interacting with a malicious prover will ``learn nothing'' besides the statements validity.  
	\end{enumerate}

	\item Consider a modified version of Schnorr's signature in which the signing
	nonce $r$ is computed as $r \gets H(m)$, where $H: \zo^* \to \Z_q$ is a
	hash function (modeled as a random oracle), $m$ is the message to be signed, and $q$ is the order
	of the group used for the signature scheme.
	This deterministic version of Schnorr's signature scheme is secure.

	\item The security of the Fiat-Shamir transform implies that a sigma protocol with a random challenge and soundness 1/2 can be \emph{directly} converted to a NIZK by replacing the challenge message with a hash, so long as the hash function is modeled as a random oracle.
	
	\item Recall the SNARG constructed in class from the PCP theorem and a
          merkle tree.
          If the PCP theorem is instantiated with soundness error $\epsilon$,
          then the SNARG also has soundness error $\epsilon$.
\end{enumerate}

\problem{Understanding Interactive Proofs [15 points]}
\textit{(Problems from ``The Foundations of Cryptography - Volume 1, Basic Techniques'' by Oded Goldreich)}

\begin{enumerate}[label=(\alph*), leftmargin=*]
	\item \textit{The role of verifier randomness:} Let $L$ be a language with an 
	interactive proof system where the verifier $V$ is deterministic. 
	Show that $L \in \classNP$.
	
	\item \textit{The role of prover randomness:} Let $L$ be a language with 
	an interactive proof system. Show that there exists an interactive proof 
	system for $L$ for which the prover $P$ is deterministic.\newline
	[\textbf{Hint:} Use the fact that $P$ is unbounded.]
	
	\item \textit{The role of errors:} Let $L$ be a language with an interactive
	proof system with perfect soundness, that is if $x \notin L$, the verifier 
	\emph{never} accepts (not even with negligible probability). 
	Show that $L \in \classNP$.
\end{enumerate}

\newpage

\problem{Sigma Protocol for Circuit Satisfiability [10 points]}

Let $\cSAT$ be the language of satisfiable Boolean circuits%
%
\footnote{You can assume without loss of generality that a Boolean circuit consists of only \textsc{xor} and \textsc{and} gates.}
%
:
\[ \cSAT = \left\{ C \colon \zo^n \to \zo \mid n\in\N,\: \exists (x_1, \ldots,
x_n) \in \zo^n \text{ such that } C(x_1, \ldots, x_n) = 1 \right\}\,.
\]
Let $\Comm \colon \zo \times \calR \to \calC$ be a perfectly-binding and computationally-hiding
commitment scheme with message
space $\zo$, randomness space $\calR$, and commitment space $\calC$. Suppose
that there exist Sigma protocols $\pro{P_{\textsc{xor}}, V_{\textsc{xor}}}$
and $\pro{P_{\textsc{and}}, V_{\textsc{and}}}$ for languages $\calL_{\textsc{xor}}$ and $\calL_{\textsc{and}}$, respectively, where:
\begin{align*}
&\calL_{\textsc{xor}} = \left\{ (c_1, c_2, c_3) \in \calC^3 ~\left|~ \begin{array}{c} \exists (m_1, m_2, m_3) \in
\zo^3, (r_1, r_2, r_3) \in \calR^3 \text{ such that } \\ \forall i \in
\set{1,2,3}~ c_i = \Comm(m_i; r_i) \text{ and } m_1 \oplus m_2 = m_3
\end{array} \right. \right\}\\
&\calL_{\textsc{and}} = \left\{ (c_1, c_2, c_3) \in \calC^3 ~\left|~ \begin{array}{c} \exists (m_1, m_2, m_3) \in
\zo^3, (r_1, r_2, r_3) \in \calR^3 \text{ such that } \\ \forall i \in
\set{1,2,3}~ c_i = \Comm(m_i; r_i) \text{ and } m_1 \land m_2 = m_3
\end{array} \right. \right\}\,.
\end{align*}

%\begin{enumerate}[label=(\alph*), leftmargin=*]   
%  \item 
Give a Sigma protocol for $\cSAT$. In addition to describing a protocol,
you will also need to show that your protocol satisfies completeness, soundness,
and honest-verifier zero-knowledge. [\textbf{Hint:} When showing that your protocol is honest-verifier
zero-knowledge, you may want to use a hybrid argument. Some of your hybrids might rely on
the commitment scheme being computationally hiding, and the other hybrid might rely on the
underlying Sigma protocols being honest-verifier zero-knowledge.]

\problem{Using Polynomial Commitments [12 pts]} 
  \begin{enumerate}[label=(\alph*), leftmargin=*]
    \item
      \textbf{Aggregation}
      One interesting property of the KZG polynomial commitment scheme
      is that it permits \textit{aggregation}: a single proof can establish
      openings for multiple polynomials. Aggregation for a polynomial commitment
      is expressed through two algorithms:
    \begin{itemize}
      \item $\ms{Open2}(pp, c_0, c_1, f_0, f_1, x) \to \pi$:
        Creates an opening proof for $f_0(x)$ \textbf{and} $f_1(x)$ (which have
        commitments $c_0$ and $c_1$ respectively).
      \item $\ms{Check2}(pp, c_0, c_1, y_0, y_1, x, \pi) \to \zo$:
        Checks that $\pi$ proves $y_0 = f_0(x)$ \textbf{and} $y_1 = f_1(x)$.
    \end{itemize}
    With aggregation, we need a few extra security properties to capture the
    fact that legitimate proofs are always accepted, and illegitimate proofs are
    almost always rejected.
    \begin{itemize}
        \item \textbf{(Perfect) Aggregate Correctness:} For all $d$, all polynomials $f_0$ and
        $f_1$ in the field, of degree at most $d$, and all $x$ in the field,
      \[ \Pr\left[
        \begin{array}[h]{l}
          pp \gets \ms{Setup}(d)\\
          c_0 \gets \ms{Commit}(pp, f_0)\\
          c_1 \gets \ms{Commit}(pp, f_1)\\
          \pi \gets \ms{Open2}(pp, c_0, c_1, f_0, f_1, x)
        \end{array}
        :
        \begin{array}[h]{r}
          \ms{Check2}(pp, c_0, c_1, f_0(x),\\ f_1(x), x, \pi) = 1
        \end{array}
            \right]
              =  1 \]
    (where $\ms{Commit}$ is from the base polynomial commitment scheme).
      \item \textbf{Aggregate Evaluation Binding:} For all efficient adversaries $\calA$, if we set
        $pp \gets \ms{Setup}(d)$ and
      $(x, c_0, c_1, \pi, \pi', y_0, y_1, y'_0, y'_1) \gets \calA(pp, d)$, then
      \[ \Pr\left[
        \begin{array}[h]{c}
        \ms{Check2}(pp, c_0, c_1, y_0, y_1, x, \pi) = 1
        \\
        \land
            \ms{Check2}(pp, c_0, c_1, y'_0, y'_1, x, \pi') = 1
            \\
            \land (y_0, y_1) \ne (y'_0, y'_1)
        \end{array}
            \right]
              =  \negl(\lambda). \]


    \end{itemize}

    For this problem, construct $\ms{Open2}$ and $\ms{Check2}$
    and
    show that your construction satisfies aggregate correctness.
    Then, give an informal argument (2 or 3 sentences)
    that it satisfies aggregate evaluation
    binding (assuming t-SDH is hard)
    in the random oracle model.

    \textbf{[Extra Credit (2 pts)]} Give a formal proof that your scheme is
    aggregate evaluation binding (assuming t-SDH is ard) in the random oracle
    model.

    You may use a random oracle over whichever domain you like.

    \textit{Hint: you may want to revisit aggregation for BLS signatures.}

  \item \textbf{Accumulators}
    Cryptographic accumulators represent a data structure as a small digest in
    such a way that operations over the data structure can be verified with
    access to only the digest.
    A \textit{set accumulator} over universe $\calU$ comprises five algorithms:
    \begin{itemize}
      \item $\ms{Create}(S \subset \calU) \to d$:
        Creates a digest representing the set $S \subset \calU$.
      \item $\ms{ProveMem}(S \subset \calU, d, x \in S) \to \pi$:
        Creates a proof that $x \in S$.
      \item $\ms{VerifyMem}(d, x, \pi) \to \zo$:
        Verifies a proof that $x \in S$.
      \item $\ms{ProveNonMem}(S \subset \calU, d, x \notin S) \to \bar\pi$:
        Creates a proof that $x \notin S$.
      \item $\ms{VerifyNonMem}(d, x, \bar\pi) \to \zo$:
        Verifies a proof that $x \notin S$.
    \end{itemize}

    A set accumulator is
    \textit{membership-secure}
    if forging membership proofs for elements not in the set is hard.
    Similarly, a set accumulator is
    \textit{non-membership-secure}
    if forging non-membership proofs for elements in the set is hard.
    \unskip\footnote{
      In the literature, both properties are called ``collision resistance''.
      We avoid that name here to avoid a confusion with hash functions.
    }
    That is,
    if for all efficient adversaries $\calA$,
    the following probabilities are negligible in $\lambda$:
    \[
      \Pr\left[
        \begin{array}[h]{l}
          (S, x, \pi) \gets \calA(\calU) \\
          d \gets \ms{Create}(S)
        \end{array}
        :
        \begin{array}[h]{c}
          x \notin S\ \land\\
          \ms{VerifyMem}(d, x, \pi) = 1
        \end{array}
      \right]
      \quad
      \Pr\left[
        \begin{array}[h]{l}
          (S, x, \bar\pi) \gets \calA(\calU) \\
          d \gets \ms{Create}(S)
        \end{array}
        :
        \begin{array}[h]{c}
          x \in S\ \land\\
          \ms{VerifyNonMem}(d, x, \bar\pi) = 1
        \end{array}
      \right]
    \]

    Using an evaluation-binding polynomial commitment scheme
    (which may, or may not be the KZG scheme)
    for polynomials over $\mathbb{F}$,
    build a set accumulator for $\calU = \mathbb{F}$.
    Prove that your accumulator is membership and non-membership secure,
    assuming that the underlying polynomial commitment scheme is binding.

    \textit{Hint: What set of values is naturally associated with a polynomial?}


   \item \textbf{Extra Credit [3 points].}
     Now, assume that your accumulator construction is instantiated with the KZG
     polynomial commitment scheme.

     Show how one can compute the digest $d'$ of $S\cup\{y\}$ given the digest
     $d$ for $S$, and the secret exponent of the polynomial commitment scheme,
     $\alpha$. Your algorithm,
     \begin{itemize}
       \item $\ms{Update}(S, d, y) \to d'$:
         returns a digest $d'$ equal to $\ms{Create}(S\cup\{y\})$
     \end{itemize}
     should run in time independent of $|S|$,
     and you should show it is correct.

     Furthermore, show how one can compute a single update token, $u$,
     that allows any membership proof $\pi$ for some $x$
     which is valid with respect to $d$
     to be updated into a new membership proof $\pi'$ which is valid
     with respect to $d'$.
     That is, given two algorithms:
     \begin{itemize}
       \item $\ms{MakeToken}(S, d, y) \to u$:
         creates update token $u$ for membership proofs with respect to $d$
       \item $\ms{UpdateProof}(d, x, \pi, u) \to \pi'$:
         creates a new proof $\pi'$ which is valid with respect to $d'$
     \end{itemize}
     and show that these algorithms produce a valid $\pi'$.
     \unskip{\footnote{
         Note:
         Some accumulator constructions to not admit the efficient update
         algorithms you build in this sub-problem.
         We suspect yours will,
         but
         if you're worried that your construction for part (b) does not allow
         for efficient updates, feel free to consult with the teaching staff.
     }}

  \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}
\end{document}
