\iffalse

NOTE:  If you do not collaborate with anyone, simply remove the '****
INSERT COLLABORATORS HERE****' and replace it with 'nobody.' Don't erase
the collaboration statement!  Thanks.


INSTRUCTIONS: (if this is not ps1, use the right file name)

  Clip out the ********* INSERT HERE ********* bits below and insert
appropriate TeX code.  Once you are done with your file, run

  ``latex ps7.tex''

from the Athena shell.  If your TeX code is clean, the latex will exit
back to a prompt.  Once this is done, run

  ``dvips ps7.dvi''

which should print your file to the nearest printer.  There will be
residual files called ps1.log, ps1.aux, and ps1.dvi.  All these can be
deleted, but do not delete ps1.tex.

\fi
\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{latexsym}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\newcommand{\handout}[5]{
   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { {\bf 6.875J/18.425J Cryptography and
  Cryptanalysis} \hfill #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\al}{\alpha}
\newcommand{\Z}{\mathbb Z}
\newcommand{\N}{\mathbb N}
\newcommand{\calO}{{\cal O}}

\begin{document}
\handout{P9}{DUE: December 12, 2001}{Instructor: Anna Lysyanskaya}
{Teaching Assistant: Moses Liskov}
{*********** INSERT YOUR NAME HERE ***********: PS 9}

I collaborated with ******** INSERT COLLABORATORS OR `nobody' HERE **********.

\bigskip

\section*{Problem 1}

(33 points) Recall that in a commitment scheme there are two ITMs, $C$
and $R$ (for committer and receiver), which operate in two stages
(they are given an auxillary input, either $`c'$ or $`r'$, to indicate
which stage they are in at the time).  Recall the definition:

\begin{tabbing}
Correctness:\\
$\forall b \in \{0, 1\}~\forall k$\\
$\Pr[$\=$u \leftarrow C(b, 1^k, `c') \leftrightarrow R(1^k, `c') \rightarrow v;$\\
\>$C(u, `r') \leftrightarrow R(v, `r') \rightarrow b': b' = b] = 1$\\
\\
Hiding:\\
$\forall \{R'_k\} PPTF~\exists \nu \in negl~\forall k$\\
$\Pr[b \leftarrow \{0, 1\}; u \leftarrow C(b, 1^k, `c') \leftrightarrow R'_k(1^k, `c') \rightarrow b':$\\
\>$b = b'] < 1/2 + \nu(k)$\\
\\
Binding:\\
$\forall \{C'_k\} PPTF~\exists \nu \in negl~\forall k$\\
$\Pr[u \leftarrow C'_k(1^k, `c') \leftrightarrow R(1^k, `c') \rightarrow v;
C'_k(u, 0, `r') \leftrightarrow R(v, `r') \rightarrow b_0;$\\
\>$C'_k(u, 1, `r') \leftrightarrow R(v, `r') \rightarrow b_1: b_0 \neq b_1] < \nu(k)$\\
\end{tabbing}

Prove that if a commitment scheme exists, then a one-way function
exists.  Hint: Be careful to remember that in a commitment scheme, the
commit stage may take multiple messages.

\bigskip {\bf Solution:}
******************* INSERT PROBLEM 1 SOLUTION HERE ***************

\section*{Problem 2}

Consider the following commitment scheme.  Suppose there are public
parameters $p$ (a prime), and $g$ and $h$, two generators modulo $p$,
and that these are chosen at random at the start and made available to
both parties.

To commit to a bit $b$, the committer chooses a random $r$ and
computes $g^rh^b$, which is sent to the verifier.  To open the
commitment, the committer reveals $r$ and $b$.

\bigskip {\bf (a)} (11 points) Prove that this is a secure commitment scheme.
More precisely, prove that this scheme is correct, that it is hiding
unconditionally, and that it is binding if the discrete log problem is
hard.

\bigskip {\bf Solution:}
******************* INSERT PROBLEM 2a SOLUTION HERE ***************

\bigskip {\bf (b)} (11 points) If instead the committer generates $p$, $g$, and
$h$, is the scheme secure?  Prove your answer.  If no, is there a way
to fix it easily?

\bigskip {\bf Solution:}
******************* INSERT PROBLEM 2b SOLUTION HERE ***************

\bigskip {\bf (c)} (11 points)  If instead the receiver generates $p$, $g$, and
$h$, is the scheme secure?  Prove your answer.  If no, is there a way
to fix it easily?

\bigskip {\bf Solution:}
******************* INSERT PROBLEM 2c SOLUTION HERE ***************

\section*{Problem 3}

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$.

\begin{enumerate}
\item $P$ chooses a random prime $p = 2q+1$ where $q$ is a random
$k$-bit prime, and a random $g$ or order $q$, and randomly chooses $\beta$
and sets $h = g^{\beta} \bmod p$.  $P$ sends $p, q, g, h$ to $V$.

\item $V$ computes a random string $c$ of length $k$ and a random $r$,
and sends $x = g^rh^c$ to $P$.

\item $P$ chooses $k$ random values $r_1, \ldots, r_k$ and
computes $s_i = r_i^2$ and sends $s_1, \ldots, s_k$ to $V$.

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

\item $P$ checks that $x = g^rh^c$.  If so, $P$ sends to $V$, for each
$i$, the value $t_i = r_i \alpha^{c_i}$, where $c = c_1 \circ \ldots
\circ c_k$.  $P$ also sends $\beta$ to $V$

\item $V$ checks that $t_i^2 \equiv s_i a^{c_i}$ for each $i$, and
that $h = g^{\beta}$.  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 completeness 1.  The idea
of this construction is to simply parallelize the ZKP we presented in
class for quadratic residuosity.  In order to prove zero-knowledgeness
we need to add the commitment $x$ into the protocol, as you will see
when proving this.

\bigskip {\bf (a)} (17 points) 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$).

\bigskip {\bf Solution:}
******************* INSERT PROBLEM 3a SOLUTION HERE ***************

\bigskip {\bf (b)} (17 points) Prove that if the discrete logarithm
problem is hard, then $P, V$ is zero-knowledge.

\bigskip {\bf Solution:}
******************* INSERT PROBLEM 3b SOLUTION HERE ***************



\end{document}
