\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}