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

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

\bigskip

\section*{Problem 1: Random Functions and Random Permutations}

Let $\calO_0 = R(n)$ be a random (length-preserving) function oracle:
on any input from $\{0, 1\}^n$, if it has not yet given an answer for
that input, it returns a random value from $\{0, 1\}^n$.

Let $\calO_1 = \Pi(n)$ be a random permutation oracle: on any input
from $\{0, 1\}^n$, if it has not yet given an answer for that input, it
returns a random value in $\{0, 1\}^n$ that it has never returned before.

Prove that $\calO_0(n)$ is indistinguishable from ${\mathcal O}_1(n)$,
in the strongest sense you can.

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

\section*{Problem 2: Attacking Luby-Rackoff}

Recall the Luby-Rackoff construction for a pseudorandom permutation
from a pseudorandom function.  Let $F_i$ be a set of pseudorandom
functions, and let 

$$LR_i(L, R) = (R, F_i(R) \oplus L )$$ 

define the $i^{th}$ round of operation of the Luby-Rackoff
construction.  For an integer $k$, define 

$$LR-k(L, R) = LR_k(LR_{k-1}( \ldots (L, R) \ldots )$$

to be the output of $k$-round Luby-Rackoff.

We say a permutation family $P_S$ over $\{0, 1\}^{l(k)}$ is
pseudorandom if:

\begin{tabbing}
$\forall \{A^{?}_k\} \in PPT~\exists \nu \in negl~\forall k$\\
$\Pr[$\=$S \leftarrow \{0, 1\}^k; \calO_0 \leftarrow P_S;$\\
\>${\mathcal  O}_1 \leftarrow  \Pi(l(k));$\\
\>$b' \leftarrow A^{\calO_b}_k: b' = b] < 1/2 + \nu(k)$
\end{tabbing}

{\bf (a)} Prove that $LR-2$ is not a pseudorandom permutation family.

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

\bigskip

We say a permutation family $P_S$ is strongly pseudorandom if:

\begin{tabbing}
$\forall \{A^{?,?}_n\} \in PPT~\exists \nu \in negl~\forall k$\\
$\Pr[$\=$S \leftarrow \{0, 1\}^k; \calO_0 \leftarrow P_S; 
{\mathcal O'}_0 \leftarrow P^{-1}_S$\\
\>${\mathcal  O}_1 \leftarrow  \Pi; {\mathcal
O'}_1 \leftarrow \Pi^{-1};$\\
\>$b' \leftarrow A^{\calO_b,{\mathcal O'}_b}: b' = b] < 1/2 + \nu(k)$
\end{tabbing}

where $\Pi^{-1}$ inverts  $\Pi$.  Think of $\Pi$ as  being a fixed but
randomly chosen perumtation, and $\Pi^{-1}$ as its inverse.

{\bf (b)} Prove that $LR-3$ is not a strong pseudorandom permutation family.

\bigskip {\bf Solution:}
*************** INSERT PROBLEM 2b SOLUTION HERE ***********
 
\section*{Problem 3: Four-Round Luby-Rackoff}

In class we proved that $LR-3$ is a pseudorandom permutation family.
Prove that $LR-4$ is a strong pseudorandom permutation family.  This
is rather difficult to come up with from scratch, so we provide a
proof sketch that you should fill in.

{\bf Proof sketch}: First of all, assume we have an adversary
$A^{?,?}$ which defeats the security of $LR-4$.  Prove that without
loss of generality we can assume that the adversary never asks $\calO$ or
$\calO'$ the same question twice, that the adversary never queries $\calO$ on
an output of $\calO'$, and that the adversary never queries $\calO'$ on the
output of $\calO$.  

Next, formulate a construction for $LR-4R$, which performs the
Luby-Rackoff function with 4 random functions instead of $F_1, F_2,
F_3, F_4$.  This construction is just like the one from class, except
for $LR-4$ instead of $LR-3$.  Prove that $LR-4R$ is indistinguishable
from a random function, similarly to how we did in class.

Next, formulate a construction for $(LR-4R)^{-1}$, which operates
with the oracle $LR-4R$, and prove that adversaries that have oracle
access to $LR-4R$ and another (challenge) oracle cannot tell whether
the challenge oracle was $(LR-4R)^{-1}$ or a random function.  This
is the meat of the proof.

Finally, put it all together and prove that $LR-4$ is
indistinguishable from a random permutation in this model.  Your proof
should assume this is not the case and derive a contradiction by
proving that one of the functions $F_i$ is not pseudorandom.

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

\section*{Problem 4: Encrypting the Secret Key}

Let $(G, E, D)$ be a (one-pass) GM-secure cryptosystem.  This should
be thought of as a ``secure envelope'' -- the adversary cannot see its
contents, no matter what the message is.  This problem shows that one
has to be careful with this intuition.  Namely, we ask the question,
``Can I trust my encryption to the extent that I can publish the
encryption of my secret key?''  

\bigskip {\bf (a)} (7 points) Construct a cryptosystem $(G', E', D')$
based on $(G, E, D)$ such that given $t = E'(PK', SK')$, the adversary
can easily distinguish the encryptions of {\em any} two messages $m_0$
and $m_1$.  (Hint: $t$ should somehow contain $SK'$.  Try to imagine
how this can be done without making $(G', E', D')$ insecure.)

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

\bigskip {\bf (b)} (7 points) Construct a cryptosystem $(G'', E'',
D'')$ based on $(G, E, D)$ such that even giving $t = E''(PK'', SK'')$
to the adversary, the scheme is still GM-secure.  You should imagine
that the adversary learns $t$ at the same time as $PK''$.  (Hint: $t$
should somehow contain random garbage.  Try to imagine how we can do
this but {\em still be able to decrypt $t$})

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

\bigskip {\bf (c)} (6 points) Suppose Alice and Bob each have keys,
$(PK_A, SK_A)$ and $(PK_B, SK_B)$ under $(G, E, D)$.  Prove that Alice
can securely encrypt {\em her} secret key under {\em Bob's} public
key.  That is, prove that $(G, E, D)$ is still GM-secure even when the
adversary knows $PK_A, PK_B$, and $E(PK_B, SK_A)$.  Formally, prove that

\begin{tabbing}
$\forall \{A_k\} \in PPT~\exists \nu \in negl~\forall k$\\
$\Pr[$\=$(PK_A, SK_A) \leftarrow G(1^k); (PK_B, SK_B) \leftarrow
G(1^k); t \leftarrow E(PK_B, SK_A)$;\\
\>$(\alpha, m_0, m_1) \leftarrow A(PK_A, PK_B, t); b \leftarrow \{0, 1\};
b' \leftarrow A(\alpha, E(PK_A, m_b)): b'=b] < 1/2 + \nu(k)$
\end{tabbing}

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

\section*{Problem 5: Insecure Signatures}

All of the signature schemes presented in this problem are insecure.
A signature scheme can be broken in a number of ways: it can be shown
to be existentially forgeable, it can be target-message forgeable, or
its secret key can be completely recoverable.  In order to break
a signature scheme, different flavors of attacks can be launched:
a public-key only attack, or an interactive attack where the adversary
asks for signatures on messages of his choice.

In this problem, you are asked to break each in the strongest
sense possible, using the weakest attack you can.

On the other hand, each of these signature schemes is secure in a weak
sense:  namely, on input a public key and a message, it is infeasible
to compute the signature.  Prove this weak security property
for each signature scheme.

\bigskip {\bf (a)} (8 points) Suppose a family of trapdoor
permutations $\{p_{PK}\}$ over $\{0,1\}^k$ is given.  The message
space is $\{0,1\}^k$.  A public key is the public key $PK$ of a member
of the TDP; the secret key is the correspoding $SK$.  The signature on
message $m$ is the value $x$ such that $p_{PK}(x) = m$.

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


\bigskip {\bf (b)} (6 points) Assume that RSA is a family of trapdoor
permutations.  A signature scheme is as follows: the public key is an
RSA public key $(n,e)$, and the secret key is the corresponding RSA
secret key $d$.  The message space is $\Z_n^*$.  The signature on
message $m$ is the value $m^d \bmod n$.


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

\bigskip {\bf (c)} (6 points) Assume that factoring is hard.  The
public key of this signature scheme consists of a Blum integer $n =
pq$.  (Recall that Blum integers have the property that $-1$ is a
quadratic non-residue with Jacobi symbol $1$).  The secret key is
$n$'s factorization.  The message space is $J_1(n)$, i.e. the set of
elements of $\Z_n^*$ that have Jacobi symbol $1$.  A signature
$\sigma$ on message $m \in J_1(n)$ is computed as follows: if $m$ is a
qudratic residue, then $\sigma$ is some arbitrary square root of $m$.
Otherwise, $\sigma$ is some arbitrary square root of $-m$.

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

\end{document}

