\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 3}
\end{center}
{\bf Due:} May 18, 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 [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 a linear PCP. If the linear PCP has 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. One 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{SNARGs in the Random Oracle Model [12 points]}
In this problem, we will show how to leverage probabilistically-checkable proofs
(PCPs) to construct a succinct non-interactive argument (SNARG) in the random
oracle model. We will rely on the following adaptation of the famous PCP
theorem:
\begin{framed}
\noindent \begin{minipage}{\textwidth}
\begin{theorems}[PCP]
Let $\calL$ be an $\classNP$ language. There exists two efficient
algorithms $(\calP, \calV)$ defined as follows:
\begin{itemize}[noitemsep, leftmargin=*]
\item The prover algorithm $\calP$ is a deterministic algorithm
that takes as input a statement $x \in \zo^n$, a witness
$w \in \zo^h$ and outputs a bitstring $\pi \in \zo^m$, where $h, m = \poly(n)$. We refer
to $\pi$ as the proof string.
\item The verifier algorithm $\calV^\pi$ is a {\em randomized}
algorithm that takes as input a statement $x \in \zo^n$
and has oracle access to a proof string $\pi \in \zo^m$. The verifier
reads $O(1)$ bits of $\pi$. The verifier chooses the bits it reads
{\em nonadaptively} (i.e., they can depend on the statement $x$,
but {\em not} on the values of any bit in $\pi$).
\end{itemize}
Moreover, $(\calP, \calV)$ satisfy the following properties:
\begin{itemize}[noitemsep, leftmargin=*]
\item \textbf{Completeness:} For all $x \in \calL$, if $w$ is a valid witness for $x$,
then
\[ \Pr[ \calV^\pi(x) = 1\colon \pi \gets \calP(x, w) ] = 1. \]
\item \textbf{Soundness:} If $x \notin \calL$, then for all $\pi \in \zo^m$,
\[ \Pr[ \calV^\pi(x) = 1 ] \le 1/2. \]
\end{itemize}
\end{theorems}
\end{minipage}
\end{framed}
\begin{enumerate}[label=(\alph*), leftmargin=*]
\item Let $\lambda$ be a security parameter and let
$H : \zo^* \to \zo^{\lambda}$ be a collision-resistant hash function. Use $H$ to
construct a commitment scheme $(\ms{Commit}, \ms{Open}, \ms{Verify})$
with the following properties:
\begin{itemize}
\item $\Commit(x) \to c$: The commitment algorithm should take a
message $x \in \zo^m$ and output a commitment $c \in \zo^\lambda$.
\item $\Open(x, c, i) \to \sigma$: The open algorithm takes a
message $x \in \zo^m$, a commitment $c \in \zo^\lambda$, and an index
$i \in [m]$, and outputs an opening $\sigma$.
\item $\Verify(c, i, b, \sigma) \to \zo$:
The verification algorithm takes a commitment $c \in \zo^\lambda$,
an index $i \in [m]$, a value $b \in \zo$,
and an opening $\sigma$, and outputs a bit.
\end{itemize}
Show that your commitment scheme satisfies the following properties:
\begin{itemize}
\item \textbf{Completeness:} For all $x \in \zo^m$ and $i \in [m]$,
\[ \Pr[\ms{Verify}(c, i, x_i, \sigma) = 1 \colon c \gets \Commit(x) ; \sigma \gets \Open(x, c, i)] = 1. \]
\item \textbf{Binding:} For all efficient adversaries $\calA$, if we set
$(c, i, (b, \sigma), (b', \sigma')) \gets \calA(1^\lambda)$, then
\[ \Pr[ b \ne b' \text{ and }
\Verify(c, i, b, \sigma) = 1 = \Verify(c, i, b', \sigma')] = \negl(\lambda). \]
\item \textbf{Succinctness:} The commitment $c$ output by $\Commit$ and opening $\sigma$
output by $\Open$ satisfy $\abs{c} = O(\lambda)$ and $\abs{\sigma} = O(\lambda \log m)$.
\end{itemize}
In other words, the commitment scheme $(\ms{Commit}, \ms{Open}, \ms{Verify})$ allows a user
to succinctly commit to a long bitstring and then selectively open up a single bit of the committed string. (In this question, we do not require any hiding properties from the commitment scheme.)
\item Let $\calL$ be an $\classNP$ language (with statements of length $n$).
Show how to construct a $3$-round succinct argument system for $\calL$ using your
commitment scheme from Part~(a). Specifically, your argument system should satisfy
perfect completeness, have soundness error
$\negl(\lambda)$ against computationally-bounded provers, and the
total communication complexity between the prover and the verifier
should be $\poly(\lambda, \log n)$. In particular, the
communication complexity scales {\em polylogarithmically} with the length of the $\classNP$ statement.
[\textbf{Hint:} Use the PCP theorem.]
\item Explain how to convert your succinct argument from Part~(b) into a
SNARG in the random oracle model.
\end{enumerate}
\end{document}