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

\begin{document}
\handout{P2}{DUE: September 26, 2001}{Instructor: Anna Lysyanskaya}
{Teaching Assistant: Moses Liskov}
{*********** INSERT YOUR NAME HERE ***********: PS 2}

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

\section*{Problem 1}

(40 points.)  For each of the following definitions of security for a
cryptosystem, compare them to GM-security.  Some of the definitions
may be too strong, that is, unattainable.  If the definition is
unattainable, prove it.  Otherwise, for each definition you should
prove or disprove that

\begin{enumerate}

\item If $(G, E, D)$ is secure under that definition then it is GM-secure, and

\item If $(G, E, D)$ is GM-secure then it is secure under the given definition.

\end{enumerate}



\bigskip
{\bf (a)} {\em $2^{-k}$ security.}  Do we need to be so general about
the negligible function?

\begin{tabbing}
XXX\=\kill
$\forall \; \{A_n\} \in PPT \; \exists K \in {\Bbb N} $ such that $
\forall k > K,$\\
\>$\Pr[(PK, SK) \leftarrow G(1^k); b \leftarrow \{0,1\};$\\
\>$c \leftarrow E(PK, b); b' \leftarrow A_k(PK, c): b'=b] \leq 1/2 + 2^{-k}$
\end{tabbing}

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

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

\bigskip
{\bf (b)} {\em Almost-all-parameter security.}  Do {\em all}
sufficiently large $k$ have to work?

\begin{tabbing}
XXX\=\kill
$\forall \; \{A_n\} \in PPT \; \exists f \in neg, K \in {\Bbb N} $ such that $
\forall k > K $ such that $ k \neq 2^i$ for any $i,$\\
\>$\Pr[(PK, SK) \leftarrow G(1^k); b \leftarrow \{0,1\};$\\ 
\>$c \leftarrow E(PK, b); b' \leftarrow A_k(PK, c): b'=b] \leq 1/2 + f(k)$
\end{tabbing}

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

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

\bigskip
{\bf (c)} {\em All-parameter security.}  Do we need the assertion that
$k$ has to be sufficiently large?

\begin{tabbing}
XXX\=\kill
$\forall \; \{A_n\} \in PPT \; \exists f \in neg $ such that $
\forall k \in {\Bbb N},$\\
\>$\Pr[(PK, SK) \leftarrow G(1^k); b \leftarrow \{0,1\};$\\
\>$c \leftarrow E(PK, b); b' \leftarrow A_k(PK, c): b'=b] \leq 1/2 + f(k)$
\end{tabbing}

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

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

\bigskip
{\bf (d)} {\em All-message security.}  Do we need to pick the
message randomly during the protocol?

\begin{tabbing}
XXX\=\kill
$\forall \; \{A_n\} \in PPT \; \exists f \in neg, K \in {\Bbb N} \;\;
\forall k > K \; \forall b \in \{0,1\},$\\
\>$Pr[(PK, SK) \leftarrow G(1^k);$\\
\>$c \leftarrow E(PK, b); b' \leftarrow A_k(PK, c): b'=b] \leq 1/2 + f(k)$
\end{tabbing}

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

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

\bigskip
{\bf (e)} {\em Ciphertext game security.}  Can we define security
differently: say a cryptosystem is secure if the chance an adversary
determines a message given its encryption is only negligibly better
than the probability that the adversary determines the message given a
random encryption of some kind?

\begin{tabbing}
XXX\=\kill
$\forall \; \{A_n\} \in PPT \; \exists f \in neg, K \in {\Bbb N} \; \;
\forall k > K,$\\
\>$\Pr[ $\=$ (PK, SK) \leftarrow G(1^k); b_0, b_1 \leftarrow \{0,1\}$\\
\>$c \leftarrow E(PK, b_0); b' \leftarrow A_k(PK, c): b'=b_0] -$\\
\>$\Pr[ $\>$ (PK, SK) \leftarrow G(1^k); b_0, b_1 \leftarrow \{0,1\}$\\
\>$c \leftarrow E(PK, b_1); b' \leftarrow A_k(PK, c): b'=b_0] \leq f(k)$
\end{tabbing}

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

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

\section*{Problem 2}

(20 points.)  Prove that if for any $0 < q \leq 1/2$, the
Goldwasser-Micali cryptosystem is $q$-GM-secure, then it is GM-secure.

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

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


\section*{Problem 3}

(20 points.)  Is $q$-GM-security equivalent to GM-security?  Prove or
disprove each: For any $0 < q \leq 1/2$,
$q$-GM-security implies GM-security; for any $0 < q \leq 1/2$,
GM-security implies $q$-GM-security.

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

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

\section*{Problem 4}

(20 points.)  Prove that if there exists a GM-secure cryptosystem $(G,
E, D)$ then $P \neq NP$.  For simplicity, you may assume that $(G, E,
D)$ has faithfulness 1.


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

***************** INSERT PROBLEM 4 SOLUTION HERE **************

\end{document}