\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{P3}{DUE: October 3, 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: Random-bit hybrid argument}

Recall the theorem from lecture, that if $(G', E', D')$ is a GM-secure
cryptosystem operating on 1-bit messages, then $(G, E, D)$ is a
GM-secure cryptosystem operating on $l$-bit messages where $l$
is some polynomial on $k$, and where $(G, E, D)$ just uses $(G', E',
D')$ to encrypt a longer message bit-by-bit.  That is, 

\begin{tabbing}
XXX\=\kill
$G(1^k)$:\\
\>1.  Return output of $G'(1^k)$\\
$E(PK, m = b_1 \circ b_2 \circ \ldots \circ b_l)$: \\
\>1.  For each $1 \leq i \leq l$, compute $c_i = E'(PK, m_i)$\\
\>2.  Return $c_1 \circ c_2 \circ \ldots \circ c_l$\\
$D(SK, c = c_1 \circ \ldots c_l)$: \\
\>1.  For each $1 \leq i \leq l$, compute $b_i = D'(SK, c_i)$\\
\>2.  Return $m = b_1 \circ \ldots \circ b_l.$
\end{tabbing}

Consider the following reduction $R'$.

\begin{tabbing}
XXX\=\kill
$R'(m_0, m_1, A, PK, c, k)$:\\
\>1.  Pick $i$ at random from the range $[0, l]$.\\
\>2.  For $1 \leq j \leq i$, compute $c'_j = E'(PK, b'_j)$\\
\>3.  Set $c'_{i+1} = c$\\
\>4.  For $i+1 \leq j \leq l$, compute $c'_j = E'(PK, b_j)$\\
\>5.  Return $b' = A(PK, c'_1 \circ \ldots \circ  c'_l, m_0, m_1)$
\end{tabbing}

Prove that if $A$ is an adversary that breaks the GM-security of $(G,
E, D)$ on messages $m_0, m_1$, then $R'$ provides an adversary that
breaks the GM-security of $(G', E', D')$.  


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

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

\section*{Problem 2: Moses Security}

Recall that the Hamming weight of a binary string is the
number of 1s in that string.  Let $\mathcal{H}_k^i$ be the set of all
strings of length exactly $k$ and of Hamming weight exactly $i$.

We say that a cryptosystem $(G, E, D)$ is $i$-Moses secure if

\begin{tabbing}
$\forall \{A_n\}~\exists f \in neg$ such that $\forall k > i \in
\N~\forall m_0, m_1 \in \{0,1\}^k$ such that $m_0 \oplus m_1 \in \mathcal{H}_k^i$\\ 
$\Pr[$\=$(PK, SK) \leftarrow G(1^k); b \leftarrow \{0, 1\}; c \leftarrow
E(PK, m_b);$ \\
\>$b' \leftarrow A_k(PK, c, m_0, m_1): b' = b] \leq 1/2 + f(k)$
\end{tabbing}

\bigskip{\bf (a)} Prove or disprove: For all odd $i$, $i$-Moses
security is equivalent to GM-security.

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

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

\bigskip{\bf (b)} Prove or disprove: For all even $i$, $i$-Moses
security is equivalent to GM-security.

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

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

\end{document}