\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{P8}{DUE: December 5, 2001}{Instructor: Anna Lysyanskaya}
{Teaching Assistant: Moses Liskov}
{*********** INSERT YOUR NAME HERE ***********: PS 8}

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

\bigskip

\section*{Problem 1: Adaptive Attacks}

(40 points) When we considered the security of public-key
cryptosystems, we basically only considered allowing the adversary
access to the public key.  However, a stronger attack scenario may be
considered: where the adversary has access to a decryption oracle.
Informally, we want that the adversary cannot succeed in a one-pass GM
security scenario even when the adversary has access to a decryption
oracle under the relevant secret key, though of course querying the
oracle on the actual challenge should be disallowed.  


\bigskip {\bf (a)} (15 points)
Give a formal definition of a public-key cryptosystem which is
one-pass GM secure against adaptive chosen ciphertext attack, as
described above.

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

\bigskip {\bf (b)} (15 points)
Recall the ElGamal-A cryptosystem.  
Alice selects at random (1) a $k$-bit prime $p = 2q+1$ where $q$
is also prime,  (2) an element $g$ in $Z_p^*$
of order $q$,  and (3) an $x$ in $\Z_q^*$.
Then, she sets her public key to be $(p,g,h)$, where $h=g^x \bmod p$,
and her secret key to be $x$.

Alice's public key restricts the message space to consist of
all elements in $Z_p^*$ having order $q$.
To send such a message $m$ to Alice, one
picks an $r \leftarrow \Z_q$ and 
computes his ciphertext $c = (g^r \bmod p, h^rm \bmod p)$.

To decrypt $c = (a,b)$, Alice computes $b/(a^x) \bmod p$.

In this problem we go beyond proving that ElGamal-A is not secure
against adaptive chosen ciphertext attack.  Suppose the adversary has
access to a challenge ciphertext $c$, and may ask only {\em one} query
of the decryption oracle, which much be different from $c$.  Show how
to design a $c'$ from $c$ such that given the decryption of $c'$ it is
easy to recover the decryption of $c$.

Can you strengthen this result so that if $c = (a, b)$ and $c' = (a',
b')$ then $a \neq a'$ and $b \neq b'$?  If so, show how.

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


\bigskip {\bf (c)} (10 points) Suppose the adversary has access to a
ciphertext $c$ of a message under the (1-bit) Goldwasser-Micali
cryptosystem, and may ask one query of a decryption oracle, other than
$c$.  Show how to design a $c'$ from $c$ such that given the
decryption of $c'$ it is easy to recover the decryption of $c$.  Also,
generalize your attack on the 1-bit scheme to an attack on the
$\ell$-bit scheme.

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

\section*{Problem 2: Collision-resistant hashing}

(30 points) Define a family of collision-resistant hash functions
${\mathcal H}$ as follows:

\begin{enumerate}

\item On input $1^k$, ${\mathcal H}$ outputs the description of a
key $PK$.

\item For any $PK$, it is efficient to compute $H_{PK}$.

\item $H_{PK}$ is length decreasing: $\forall k, \forall PK \in
{\mathcal H}(1^k) \forall x \in \{0, 1\}^*, |H_{PK}(x)| \leq $ min$(k, 
|x|)$.

\item It is hard to find collisions:

\begin{tabbing}
$\forall \{A_k\} PPTF~\exists \nu \in negl~\forall k$\\
$\Pr[PK \leftarrow {\mathcal H}(1^k); (x, y) \leftarrow A_k(PK):
H_{PK}(x) = H_{PK}(y) \wedge x \neq y] < \nu(k)$
\end{tabbing}

\end{enumerate}

\bigskip {\bf (a)} Prove that the existence of a family of 
collision-resistant hash functions implies the existence of a one-way
function.


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

\bigskip {\bf (b)} Suppose a family of collision-resistant hash
functions ${\mathcal H}$ is given, and let ${\mathcal H'}$ be a family
of hash functions that takes two security parameters, $l$ and $n$, so
that it has two keys $PK_l \leftarrow {\mathcal H}(1^l)$ and $PK_n
\leftarrow {\mathcal H}(1^n)$.  Define $H'_{PK_l,PK_n}(x) =
H_{PK_l}(H_{PK_n}(x))$.  Prove or disprove: there is an infinite set
of security parameter pairs for which ${\mathcal H'}$ is not
collision-resistant.  Prove or disprove: for all pairs $(k, k)$,
${\mathcal H'}$ is a family of collision-resistant hash functions.

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

\bigskip {\bf (c)} Suppose $G$ is a PRG.  Now suppose ${\mathcal H}^G$
is a family of hash functions defined by ${\mathcal H}^G(1^k) =
{\mathcal H}(1^k)$ and $H^G_{PK}(x) = G(H_{PK}(x))$.  Prove or
disprove: ${\mathcal H}^G$ is a family of collision-resistant hash
functions.  Prove or disprove: ${\mathcal H}^G$ is a family of functions 
indistinguishable from random.

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


\section*{Problem 3: Signature Schemes in the Random Oracle Model}

(30 points) In the ``random oracle model,'' we make the assumption that some
function behaves as if it were a random oracle ${\mathcal O}$.  We
assume the adversary, signer, and verifier have access to the random
oracle.  Furthermore, we make the assumption only that for every $x
\in \{0, 1\}^*, {\mathcal O}(x)$ is a truly random string of the same
length as $x$.  

Assume that a TDP family $p_{PK}$ exists, and design a simple
signature scheme using $p$ and a random oracle.  Prove that the scheme
is non-existentially forgeable against an adaptive chosen message
attack.  (Hint: in order to do this, you will have to describe exactly
how the oracle ${\mathcal O}$ works, but ${\mathcal O}$ must still be
truly random.)

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

\end{document}