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

%=================================================================
% My macros
%=================================================================
\newcommand{\Zstar}[1]{\ensuremath{\mathbb{Z}_{#1}^*}}
%\newcommand{\Zps}{\Zstar{p}}
%\newcommand{\Zp}{\ensuremath{\mathbb{Z}_{p}}}
%\newcommand{\Zq}{\ensuremath{\mathbb{Z}_{q}}}

\begin{document}
\newcommand{\pk}{\mathit{pk}}
\newcommand{\PK}{\mathit{PK}}
\newcommand{\SK}{\mathit{SK}}
\newcommand{\pr}{\Pr}
\newcommand{\gen}{\mathit{Gen}}
\newcommand{\keygen}{\mathsf{Keygen}}
\newcommand{\sign}{\mathsf{Sign}}
\newcommand{\verify}{\mathsf{Verify}}
\newcommand{\Extr}{\mathit{Extr}}

\handout{Final}{11:59 pm April 30, 2007}{Instructor: Anna Lysyanskaya}{Due: 11:59pm May 7, 2007}{Final Exam}


Note: this is an open-book exam.



 
\problem{A Zero Knowledge Proof of Knowledge}

In class, we defined an $\epsilon$-sound zero knowledge proof system in which we required that a cheating prover be able to prove a false statement with probabiliy at most $1-\epsilon$.  

In some applications, we might want something stronger.  We might want the verifier to be convinced, not only that the statment is true, but also that the prover knows why it is true, i.e. that the prover must know a witness showing that the statement is true.  How can we ensure that the prover ``knows'' something?  We require that there be some algorithm which interacts with the prover and can extract the witness he uses in the proof.  This extractor algorithm must have extra powers (since a standard verifier should not be able to extract anything from the prover), so we allow it to rewind the prover polynomially many times.  A proof system for which there exists such an extractor is called a proof of knowledge.  

More formally, a protocol $P,V$ is a zero knowledge proof of knowledge for a language $L$ if the following properties hold:
\begin{description}
\item [Correctness] $\forall x\in L$, $\forall$ witnesses $w$, 
$$\pr[P(1^k,x,w) \leftrightarrow V(1^k,x) \rightarrow \mbox{Accept}]=1$$

\item [Zero Knowledge] $\forall$ ppt $V'$, $\exists$ ppt $S$ such that $\forall x\in L$, $\forall$ witnesses $w$ the following two distributions are indistinguishable:
$$D_0 = \{P(1^k,x,w) \leftrightarrow V'(1^k,x) \rightarrow view:view\}$$
$$D_1 = \{S(1^k,x) \leftrightarrow^* V'(1^k,x) \rightarrow view:view\}$$
Note that in the second experiment, $S$ is allowed to rewind $V'$ and run him on different inputs polynomially many times.

\item [Extraction] 
$\forall$ ppt $P'$, $\exists$ ppt $\Extr$ such that $\forall x\in L$,
$\forall$ extra information $w'$ there exists negligible $\nu$ such
that 
$$ \pr[P'(1^k,x,w')\leftrightarrow V(1^k,x) \rightarrow \mbox{Accept}]$$ 
$$-\pr[P'(1^k,x,w') \leftrightarrow^* \Extr(1^k,x)\rightarrow w: w
\mbox{ is valid witness for }x\in L]\leq \nu(k)$$

Note that in the second probability $\Extr$ is allowed to rewind $P'$ and run him on different inputs polynomially many times.
\end{description}


Recall the zero knowledge proof protocol for graph coloring that we saw in class.  We will show that this proof is also a proof of knowledge.

\begin{alphabetize}
\item Describe an extractor algorithm which interacts with the graph coloring prover (and rewinds it polynomially many times) and extracts a valid coloring of the graph.
\item Suppose we have a potentially cheating prover $P'$, who manages
to convince the verifier that the graph is colorable with probability
$1-\nu(k)$ for negligible $\nu(k)$.  Prove that in this case, if the commitment
scheme used in the protocol is binding, then the extractor you
described will be able to extract a valid coloring with probability $1-\nu'(k)$ for negligible $\nu'(k)$.
\end{alphabetize}




\problem{An Efficient Signature Scheme}

Let's look at a signature scheme which is both efficient and provably secure.

Let $P_k$ be the set of primes of length $k$.
Suppose we have a family of collision resistant hash functions, $h_\pk:\{0,1\}^* \rightarrow P_k$, with key generation algorithm $G$.

Consider the following scheme:
\begin{description}
\item[$\keygen(1^k)$:] 
Choose random $k$-bit safe primes $p_1,p_2,q$ (Recall that a prime $p$ is
safe if there exists prime $p'$ such that $p=2p'+1$). Compute $n=p_1p_2$.
Choose $s\leftarrow \Zstar{n}$.  Choose $g_1,g_2 \leftarrow QR_q$, such that $g_1,g_2\neq 1$ and $g_1\neq g_2$.  Run $G(1^k)$ to obtain hash function key $\pk$.

Output $\PK = n,s,q, \pk, g_1,g_2$, $\SK = p_1,p_2$.

\item[$\sign((n,s,q, \pk), (p_1,p_2), m)$] Choose random $r\leftarrow Z_q^*$.  Compute $H_\pk(m) = h_\pk(g_1^mg_2^r)$.  Finally, use $p_1,p_2$ to compute $\sigma = s^{\frac{1}{H_{\pk}(m)}}$.  Output signature $(\sigma, r)$.

\item[$\verify((n,s,q),(\sigma,r), m)$]  Compute $H_\pk(m)=h_\pk(g_1^mg_2^r)$.  Accept iff $\sigma^{H_\pk(m)} = s$.  
\end{description}

We will use the following assumptions:\\
Recall the discrete log assumption which says:\\
Let $\gen(1^k)$ be an algorithm which generates a $k$-bit prime $q$, and a generator $g$ of $Z_q^*$.  We assume that for all PPT adversaries $\A$ there exists negligible $\nu$ such that
$$\Pr[(q,g)\leftarrow \gen(1^k); i\leftarrow Z_q; i' \leftarrow \A(p,g,g^i\mod q):g^i=g^{i'}~ \mod q] = \nu(k)$$

We will also use a variation on the RSA assmuption known as the Strong
RSA assmuption which says:\\
 Let $\gen(1^k)$ be an algorithm which
generates 2 $k$-bit primes $p_1, p_2$, and outputs $n=p_1p_2$.
We assume that for all PPT adversaries $\A$ there exists negligible $\nu$
such that
$$\Pr[n\leftarrow \gen(1^k); y\leftarrow Z_n^*; (x,e) \leftarrow \A(n,y): y=x^e] = \nu(k)$$

\noindent
We will assume that these assumptions holds when $q,p_1, p_2$ are safe primes.

We can show that if these assumptions hold, and if $h$ is family of collision
resistant hash functions, then the above signature scheme is existentially
unforgeable even when the adversary is allowed to make an interactive
attack in which he can request signatures for arbitrary messages.

Suppose there exists an adversary who can make such an attack and
produce a valid forgery.  Then we consider the following three cases:
\begin{alphabetize}
\item Suppose that with nonnegligible probability, after querying for
signatures on messages $m_1, \ldots m_l$, $\A$ produces a successful
forgery $(m^*, (\sigma^*, r^*))$ such that for some $i\in \{1, \ldots
l\}$, $m^*\neq m_i$ and $g_1^{m^*}g_2^{r^*} = g_1^{m_i}g_2^{r_i}$.
Show that if such an adversary exists then the discrete logarithm
assumption does not hold.

\item Suppose that with nonnegligible probability, after querying for
signatures on messages $m_1, \ldots m_l$, $\A$ produces a successful
forgery $(m^*, (\sigma^*, r^*))$ such that for some $i\in \{1, \ldots
l\}$, $g_1^{m^*}g_2^{r^*} \neq g_1^{m_i}g_2^{r_i}$ and
$h_\pk(g_1^{m^*}g_2^{r^*}) = h_\pk(g_1^{m_i}g_2^{r_i})$.  Show that if
such an adversary exists then $h$ is not collision resistant.

\item Suppose that with nonnegligible probability, after querying for
signatures on messages $m_1, \ldots m_l$, $\A$ produces a successful
forgery $(m^*, (\sigma^*, r^*))$ such that for all $i\in \{1, \ldots
l\}$, $h_\pk(g_1^{m^*}g_2^{r^*})\neq h_\pk(g_1^{m_i}g_2^{r_i})$, but
such that $\verify(\PK, m^*, (\sigma^*,r^*))$ accepts.  Show that if
such an adversary exists then the strong RSA assumption does not hold.
\end{alphabetize}
Note that in each of the above cases, you must describe a reduction
which (1) processes its input and gives input to the adversary, (2) answers the adversary's signing queries, and (3) processes the adversary's forgery.

\noindent
d.  Now conclude that if the strong RSA and discrete logarithm assumptions hold, and if $h$ is a family of collision resistant hash functions, then the above signature scheme is  existentially unforgeable against an interactive attack.


\problem{Essay Question}
Describe a possible application of secure two-party or multi-party computation.

\end{document}