\documentclass{article}
\usepackage{amsmath}				% want AMS fonts
\usepackage{amssymb}                            % use AMS symbols
%\usepackage[ruled]{algorithm2e}
\input{p}

%=================================================================
% My macros
%=================================================================
\newcommand{\Zstar}[1]{\ensuremath{\mathbb{Z}_{#1}^*}}

\newcommand{\pk}{\mathit{PK}}
\renewcommand{\sk}{\mathit{SK}}

\newcommand{\pr}{\mbox{Pr}}

\newcommand{\gen}{\mathit{Gen}}
\newcommand{\dom}{\mathit{Dom}}
\newcommand{\fakecom}{\mathit{FakeCom}}

\newcommand{\lsb}{\mathit{LSB}}
\newcommand{\RSA}{\mathit{RSA}}

\renewcommand{\mod}{\mbox{mod}}
\newcommand{\commit}{\mathit{Commit}}

\begin{document}
\homework{10}{April 18, 2007}{April 25, 2007}{Anna Lysyanskaya}


\problem{Parallel Zero Knowledge Proofs}


Consider the following zero-knowledge protocol for proving that a
value $a$ is a quadratic residue modulo $n$, in which 

Input: $n$ and $a$.  Let $\alpha^2 \equiv a \bmod n$ be the square
root of $a$.  
Let $\gen,\commit$ be a perfectly hiding, computationally binding commitment scheme.

\begin{enumerate}
\item $P$ chooses a public key $\pk \leftarrow \gen(1^k)$ for the commitment scheme.  $P$ sends $\pk$ to $V$. 

\item $V$ computes a random string $c$ of length $k$ and a random $r$,
and sends $C = \commit_\pk(c,r)$ to $P$.

\item $P$ chooses $k$ random values $r_1, \ldots, r_k$ and
computes $R_i = r_i^2$ and sends $R_1, \ldots, R_k$ to $V$.

\item $V$ sends $r$ and $c$ to $P$.

\item $P$ checks that $C = \commit_\pk(c,r)$.  If so, $P$ sends to $V$, for each
$i$, the value $s_i = r_i \alpha^{c_i}$, where $c = c_1 \circ \ldots
\circ c_k$. 

\item $V$ checks that $s_i^2 \equiv R_i a^{c_i}$ for each $i$.  If so, $V$ accepts, otherwise $V$ rejects.
\end{enumerate}

This defines a $P, V$ which you will prove is a zero-knowledge proof
system.  It should be clear that $P, V$ has the completeness property.  The idea
of this construction is to simply parallelize the ZKP we presented in
class for quadratic residuosity.  In order to prove zero-knowledge
we need to add the commitment $C$ into the protocol, as you will see
when proving this.

\begin{alphabetize}
\item 
Let's prove that $P, V$ has negligible soundness (ie, $V$ can only be
convinced with negligible probability if $a$ is a quadratic
non-residue modulo $n$).

Note that since this is a perfectly hiding commitment scheme, after step 3, there are many possible r,c pairs that $V$ might send in step 4 (In fact, for every $c'$, there exists an $r'$ such that $\commit(c',r')=C$ where $C$ is from step 2.  The binding property tells us that $V$ can only know one of them).  Show that if there was more than one pair $r,c$ that $V$ could send(in step 4) such that $P$ could respond(as in step 5) and make $V$ accept (as in step 6), then $a$ must be in $\QR_n$.

Then argue that this implies negligible soundness.  



\item Prove that if the commitment scheme $\commit$ is computationally binding, then $P,V$ is zero knowledge.  Design a simulator for verifier $V'$.  Show that if the simulation fails, then $\commit$ is not computationally binding.

\item Explain why the commitment $C$ was necessary.

\end{alphabetize}


\problem{A Not Zero Knowledge Proof }
Consider the following protocol\\
Input: RSA modulus $n$, and a value $x \in \QNR_n$\\
The prover knows the factorization of $n$ and wants to prove that $x$ is in $\QNR_n$.
\begin{enumerate}
\item The verifier forms a challenge value as follows: choose $c\leftarrow \{0,1\}$, choose random $r\in Z_n^*$.   $V$ sends $y=r^2 x^c$ to $P$.

\item The prover uses the factorization of $n$ to determine whether $y\in \QR_n$.  If so, let $c'=0$.  Otherwise, let $c'=1$.  Sent $c'$ to $V$.

\item V checks that $c'=c$.  If so, $V$ accepts, otherwise $V$ rejects.
\end{enumerate}

It turns out that this protocol is sound, but it is NOT zero-knowledge.
\begin{alphabetize}
\item Prove that this protcol satisfies the soundness property.
\item Explain where the proof of zk property would break down -- why we
wouldn't be able to build a valid simulator? Note the simulator would not know $p,q$, as these are not known to the verifier.
\item Explain how a cheating verifier could use an honest prover to learn something 
\end{alphabetize}

\problem{Commitments}


Let's look at another  commitment scheme.  Suppose there are public
parameters $p, q$, primes such that $p=2q+1$ and $g,h\in \QR_p$ where
$g\neq 1, h\neq 1, g\neq h$ and that these are chosen at random at the start
and made available to both parties.

To commit to $x\in Z_q$, the committer chooses a random $r$ and
computes $\commit(x,r)=g^xh^r$. To open the commitment, the committer
reveals $r$ and $x$.

Let's first prove that this is a secure commitment scheme.
\begin{alphabetize}
\item Prove that this scheme satisfies the perfect hiding property
\item Prove that, if the discrete log problem is hard, then this scheme satisfies the computational binding property.
\item  If instead the committer generates $p$, $q$, $g$, and
$h$, is the scheme secure?  Prove your answer.  
\item If instead the receiver generates $p$, $q$, $g$, and
$h$, is the scheme secure?  Prove your answer. 
\end{alphabetize}
\end{document}