
\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{latexsym}
\input{texdefs}

\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 CS195-7: Introduction to Cryptography} \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{\ho}[4]{\handout{#1}{#2}{Instructor:
#3}{}{Handout #1: #4}}

\newcommand{\solution}[1]{\medskip
\noindent {\bf Solution:} \newline #1}
\newcommand{\set}[1]{\{#1\}}
\def\prf{{\sf PRF}}

\begin{document}
\handout{F}{DUE: December 17, 2002}{Instructor: Anna Lysyanskaya}
{\solution{*** Your name here *** }}{Final Exam}

\section*{Problem 1}
Let $(G,E,D)$ be a public-key cryptosystem.
Suppose Alice has a key pair $(\pk_A,\sk_A)$ for this cryptosystem,
obtained by running algorithm $G$.  One day,
Alice goes on vacation and wants her friend Bob to
read her mail while she is away.  So she needs to
give Bob 
her secret key $\sk_A$.  Bob lives in another city, and
so Alice has to send her secret key to him by e-mail.
Bob's public key $\pk_B$ is known to her, so she
generates the ciphertext $c_{\sk}\leftarrow E(\pk_B,\sk_A)$
and sends $c_{\sk}$ to Bob.

\bigskip {\bf (a)}  Explain what it means for Alice's
mail to be semantically secure even after the eavesdropper
Eve gets hold of the values $(\pk_A,\pk_B,c_{\sk})$.  (Since
we are only after {\em semantic} security, Eve is passive,
i.e., she does not ask Alice or Bob to actually decrypt any ciphertexts.)
Give
both an English explanation, and a formal definition.

\solution{
INSERT SOLUTION HERE
}

\bigskip {\bf (b)}  Show that if $(G,E,D)$ is semantically
secure, then Alice's mail remains semantically secure.

\solution{
INSERT SOLUTION HERE
}

\bigskip {\bf (c)}  Explain what it means for Alice's mail
to be chosen-ciphertext secure even after the eavesdropper 
Eve gets hold of the values $(\pk_A,\pk_B,c_{\sk})$ {\em and}
is allowed access to the appropriate decryption algorithms.
Does it follow that if $(G,E,D)$ is secure against 
chosen ciphertext attack, then in this altered scenario, Alice's
mail will also remain secure against the chosen ciphertext attack?
You do not have to give a formal proof, but argue why
your proof for part (b) works or does not work here.

\solution{
INSERT SOLUTION HERE
}

\bigskip {\bf (d)}  Suppose that, instead of encrypting
her $\sk_A$ under Bob's public key, Alice encrypted it under
her own public key $\pk_A$  (I have no idea why she would
want to do that!), and so $c_{\sk}\leftarrow E(\pk_A,\sk_A)$.
Does it follow that, if $(G,E,D)$ is a semantically secure
cryptosystem, Alice's mail will remain secure after the
adversary gets hold of $(\pk_A,c_{\sk})$?  
Does it follow that her mail becomes insecure?

\solution{
INSERT SOLUTION HERE
}


\section*{Problem 2}
Recall the ElGamal cryptosystem: 

\begin{description}
\item[Key generation]
On input $1^k$, the key generation algorithm outputs the values 
$(\pk=(p,q,g,h), \sk = x)$,
where (1)
$p=aq+1$ is a $k$-bit prime number;
(2) $q$ is a prime number of $O(k)$ bits (usually $p=2q+1$, but
it is unknown whether there is an infinite number
of such primes); (3) $g$ is a generator of a subgroup of $\Zps$ of order
$q$, denote this subgroup
by $G = \langle g \rangle$;  (4) $x \leftarrow \Zz_q$, $h = g^x \bmod p$.
\item[Encryption]
To encrypt a message $m \in G$, pick $r \leftarrow \Zz_q$, and output
the ciphertext $c = (g^r, h^rm)$.
\item[Decryption]
To decrypt a ciphertext $c = (a,b)$, output $m = b/a^x$.
\end{description}

In class, we saw that this cryptosystem is semantically secure under 
the decisional Diffie-Hellman assumption, i.e., the assumption that
the following two experiments produce indistinguishable
distributions:

\begin{description}
\item[Experiment DH]  On input $1^k$, 
choose $p$, $q$, $g$ as described above.
Pick random $x \leftarrow \Zz_q$, $y \leftarrow \Zz_q$,
and let $X = g^x$, $Y= g^y$, $Z=g^{xy}$.  Output $(p,q,g,X,Y,Z)$.
\item[Experiment R]  On input $1^k$, choose $p$, $q$, $g$ as described above.
Pick random $x \leftarrow \Zz_q$, $y \leftarrow \Zz_q$, $z \leftarrow \Zz_q$,
and let $X = g^x$, $Y= g^y$, $Z=g^{z}$. Output $(p,q,g,X,Y,Z)$.
\end{description}

Give a chosen-ciphertext attack against this cryptosystem.

\solution{
INSERT SOLUTION HERE
}

\section*{Problem 3}
The Schnorr signature scheme is secure in the random oracle
model under the assumption that the discrete logarithm problem
is hard.  It works as follows:

\begin{description}
\item[Key generation]
Pick a group $G$:  choose a $k$-bit prime $p = aq+1$, where $q$
is a prime number of length $O(k)$, and produce $(p,q,g)$, where
$g\in \Zps$ has order $q$.  Let $G = \langle g \rangle$.  
Pick a hash function $H~:~\bit^* \mapsto \Zq$.
Pick the secret key $x \leftarrow \Zq$.  
Let $h = g^x$.  Output the public key $(p,q,g,h)$.  
\item[Signing]  In order to sign a message $m$,
choose a random $r \leftarrow \Zq$.  Compute the following:
\begin{eqnarray*}
A &=& g^r \bmod p\\
c&=& H(m \circ A)\\
s&=& r+xc \bmod q
\end{eqnarray*}
and output the signature $(A,s)$.
\item[Verification]  In order to verify a signature $(A,s)$ on 
message $m$, compute $c = H(m\circ A)$, and check that $g^s = Ah^c$.
\end{description}
Here, we will prove this signature scheme secure.

\bigskip {\bf (a)}  Prove that the Schnorr signature scheme is non-trivial,
i.e., that any signature generated by the signing algorithm will pass
the verification test.

\solution{
INSERT SOLUTION HERE
}

\bigskip {\bf (b)}  Show that one must ``know'' $x$ in order to
compute a signature correctly, in the following sense: if for the same
$A$, one can give the right values $s_1$ and $s_2$ 
for two {\em different}
values $c_1$ and $c_2$ of $H(m\circ A)$, then $x$ can be derived.  More 
precisely, design an efficient algorithm that, 
given $(A,c_1,c_2,s_1,s_2)$, such that
$c_1 \neq c_2$, and $g^{s_1} = Ah^{c_1}$, while $g^{s_2} = Ah^{c_2}$,
outputs $x$ such that $h = g^x$.

\solution{
INSERT SOLUTION HERE
}

\bigskip {\bf (c)}  
As always, security has to be proved by reduction.
The reduction has access to an adversary that forges Schnorr signatures
with probability $P(k)$.  The reduction receives as input the
group $G$ represented by $(p,q,g)$, and the value $h = g^x$.
The goal of the reduction is to compute $x$.

The reduction must interact with the adversary, i.e., set up a
public key of a signature scheme and answer the adversary's signature
queries.  In addition, since this proof of security is in the random
oracle model, the reduction is allowed to implement the ideal hash function
$H$ for the adversary, i.e., answer the adversary's hash queries.

The reduction sets up the public key as follows $\pk = (p,q,g,h,H)$.
In order to answer a signature query on message $m$, the reduction
proceeds as follows: pick a random $c\leftarrow \Zq$ and $s\leftarrow \Zq$.
Let $A = g^s/h^c$.  Fix the random oracle such that $H(m\circ A) = c$.
In order to answer a hash query, the reduction just outputs a random string.

Eventually, the adversary outputs a forged signature $(A,s)$ on message $m$.
Since this is a valid forgery, $g^s = Ah^c$, where $c$ is the answer $H$
gave to the query $(m\circ A)$.  At this point, the reduction will {\em reset}
the adversary to the point in time in which it gave $c$ in response to
$(m\circ A)$, and respond with a different random $c'\leftarrow \Zq$,
and run the adversary from that point on.  If the adversary outputs a forgery
on the same message $m$ and for the same value $A$, then by part (b),
our reduction can compute $x$, and therefore succeeds.  
Otherwise, our reduction fails.

Show that if the success probability of the adversary
is $P(k)$, and his running time is $T(k)$, then the reduction 
described above
succeeds with probability at least $P^2(k)/T(k)$.

\solution{
INSERT SOLUTION HERE
}
\end{document}
