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

\begin{document}
\handout{P4}{DUE: October 15, 2001}{Instructor: Anna Lysyanskaya}
{Teaching Assistant: Moses Liskov}
{*********** INSERT YOUR NAME HERE ***********: PS 3}

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

\section*{Problem 1: Sampling Domain Security}

Consider the following definition of security, which we call sampling
domain security (SD security).  Let $(G, E, D)$ be a public-key
cryptosystem, and let $\mathcal{M} = \{M_n\}$ be a sequence of message
spaces, each with a uniform distribution.  $(G, E, D)$ is SD secure if
there exists a probabilistic polynomial time algorithm $S$ (for
``sampling'') such that

\begin{tabbing}
$\forall \{A_n\}~\exists f \in neg$ such that $\forall k \in \N$\\
$\Pr[$\=$(PK, SK) \leftarrow G(1^k); m \leftarrow M_k; c_0 \leftarrow
E(PK, m); c_1 \leftarrow S(1^k, PK);$\\
\>$b \leftarrow \{0, 1\}; b' \leftarrow A_k(PK, c_b, m): b'=b] \leq 1/2 + f(k)$
\end{tabbing}

\bigskip {\bf (a)}
If $M_n = \{0,1\}$ for every $n$, then GM-security implies SD
security.

\bigskip 
{\bf Solution:} \bigskip \noindent

***************** INSERT PROBLEM 1a SOLUTION HERE ***************

\bigskip {\bf (b)}
If $M_n = \{0,1\}$ for every $n$, then SD security implies
GM-security.

\bigskip 
{\bf Solution:} \bigskip \noindent

***************** INSERT PROBLEM 1b SOLUTION HERE ***************


\bigskip {\bf (c)}
If $M_n = \{0,1\}^n$ for every $n$, then GM-security implies
SD security.

\bigskip 
{\bf Solution:} \bigskip \noindent

***************** INSERT PROBLEM 1c SOLUTION HERE ***************


\bigskip {\bf (d)}
If $M_n = \{0,1\}^n$ for every $n$, then SD security implies
GM-security.

\bigskip 
{\bf Solution:} \bigskip \noindent

***************** INSERT PROBLEM 1d SOLUTION HERE ***************


\section*{Problem 2: Random Message Security}

Consider the following definition of security, which we
call random message security (RM security).  We say that a
cryptosystem $(G, E, D)$ on a sequence of message spaces $\mathcal{M}
= \{M_n\}$ is RM secure if

\begin{tabbing}
$\forall \{A_n\}~\exists f \in neg$ such that $\forall k \in \N$\\ 
$\Pr[$\=$(PK, SK) \leftarrow G(1^k); (\alpha, m) \leftarrow A_k(PK, 1^k);
r \leftarrow M_k;$\\ 
\>$c_0 \leftarrow E(PK, m); c_1 \leftarrow E(PK, r); b \leftarrow \{0,1\};$\\
\>$b' \leftarrow A_k(PK, c_b, m, r): b'=b] \leq 1/2 + f(k)$
\end{tabbing}

Prove or disprove that for all polynomials $p$, for the sequence of
message spaces $\{M_n = \{0,1\}^{p(n)}\}$, RM security is
equivalent to GM security.

\bigskip
{\bf Solution:} \bigskip \noindent

***************** INSERT PROBLEM 2 SOLUTION HERE **************

\section*{Problem 3: Security of ElGamal-A}

Prove that under the decisional Diffie-Hellman assumption, the ElGamal-A
cryptosystem is GM-secure.

***************** INSERT PROBLEM 3 SOLUTION HERE **************

\end{document}