\documentclass{article}
\usepackage{amsmath}                            % want AMS fonts
\usepackage{amssymb}                            % use AMS symbols
%\usepackage[ruled]{algorithm2e}
%\usepackage{url}
\input{p}

%=================================================================
% My macros
%=================================================================
%\newcommand{\Zstar}[1]{\ensuremath{\mathbb{Z}_{#1}^*}}
%\newcommand{\Zps}{\Zstar{p}}
%\newcommand{\Zp}{\ensuremath{\mathbb{Z}_{p}}}
%\newcommand{\Zq}{\ensuremath{\mathbb{Z}_{q}}}

\begin{document}
\newcommand{\pk}{\mathit{PK}}
\renewcommand{\sk}{\mathit{SK}}
\newcommand{\pr}{\Pr}
\newcommand{\fake}{\mathit{Fake}}
\newcommand{\enc}{\mathit{Enc}}
\newcommand{\dec}{\mathit{Dec}}
\newcommand{\FakeCiphertext}{\mathit{FakeCiphertext}}


\handout{Midterm}{11:59 pm March 14, 2007}{Instructor: Anna Lysyanskaya}{Due: 11:59pm March 21, 2007}{Midterm Exam}


Note: this is an open-book exam.

\problem{Diffie Hellman Key Exchange} Suppose Alice and Bob share no
secret information, and Eve can eavesdrop on any comunication between
them.  It turns out that Alice and Bob can compute a shared secret key, in such a way that Eve will have no information about the key.  Consider the following protocol:
\begin{itemize}
\item Alice chooses 
a $k$-bit prime number $p$, an element $g\in\Zps$, and some
$x\in\Zp$, and computes $X=g^x\bmod p$.  She sends $(p,g,X)$ to Bob.
\item Bob receives $(p,g,X)$ from Alice.  
He chooses some $y\in\Zp$, and computes $Y = g^y\bmod p$.  He also computes $K_B = X^y\bmod p$, which will be his key.  He sends $Y$ to Alice.
\item Alice receives $Y$, and computes $K_A=Y^x\bmod p$, which will be her key.
\end{itemize}
This protocol was first proposed by Diffie and Hellman, in their seminal
paper ``New Directions in Cryptography,'' which started the study of public-key
encryption, and of modern cryptography in general.
\begin{alphabetize}
\item Show that this algorithm is correct, i.e. that Alice and Bob
will always get the same key.  (Note, we are only allowing Eve to
eavesdrop---she is not allowed to modify messages.)
\item An important detail that we left out of the above description
was how the values $p$,$g$,$x$, and $y$ are chosen.  
Suppose Alice chooses $g$ as a generator of
$\Zps$ (i.e. for all $h\in \Zps$, there is some integer $i$ such that
$h=g^i$), and Alice and Bob choose their $x$ and $y$ uniformly
at random from $\Zp$.  (It may be helpful to think of a concrete example:
consider $p=13$, and $g = 2$.)  Then we can show that this protocol
will not be fully secure---Eve will know that some keys are more
common than others.
\begin{itemize}
\item In our example where $p=13$, and $g=2$, what is the probability
that $X$ that Alice sends will be a square? (Hint: consider all
possibilities.)
\item In our example where $p=13$, and $g=2$, what is the probability
that $Y$ that Bob sends will be a square?
\item In our example where $p=13$, and $g=2$, what is the probability
that the key $K_A=K_B$ that Alice and Bob agree on will be a square?
\item In general, what is the probability that $X$ that Alice sends
will be a square?  Why?
\item In general, what is the probability that $Y$ that Bob sends will
be a square?  Why?
\item In general, what is the probability that $K_A = K_B$ will be a
square?  Why?
\end{itemize}

\item Suppose instead that Alice picks $p=2q+1$ where both $p$ and $q$ 
are
primes.  Further, suppose that she picked $g\in\QR_p$.  Finally, $x$ and $y$ 
are both chosen uniformly at
random from $\Zq$.  (For a concrete example, think of $p=23$, $q=11$, and $g = 4$.) 

\begin{itemize}
\item In this case, how many elements are in the group generated by
$g$, i.e. how many distinct elements $h\in \Zps$ exist such that $g^i
=h$ for some $i\in Z$? (Hint: first consider the case where $p=23$ and
$g=4$, and then generalize.)
\item In our example where $p=23$, and $g=4$, what is the probability that $X$ that Alice sends will be a square?
\item In our example where $p=23$, and $g=4$, what is the probability that $Y$ that Bob sends will be a square?
\item In our example where $p=23$, and $g=4$, what is the probability that the key $K_A=K_B$ that Alice and Bob agree on will be a square?
\item In general, what is the probability that $X$ that Alice sends will be a square?  Why?
\item In general, what is the probability that $Y$ that Bob sends will be a square?  Why?
\item In general, what is the probability that $K_A = K_B$ will be a square?  Why?
\item In general, what will be the distribution of possible values for
the key that Alice and Bob agree on ($K=K_A=K_B$)?
\end{itemize}
\end{alphabetize}
Note that, even though the value $K=K_A=K_B$ is never sent in the clear,
if Eve had unlimited computational ability, she would be able to 
discover it: she can find $x$ from $X$ by brute force, and similarly
can find $y$ from $Y$ by brute force.  
But if Eve is computationally bounded, can she discover $K$?
It is by now an established number-theoretic assumption, known as the 
decisional Diffie-Hellman assumption (DDH) that the key
$K$ is a random-looking element of the group $\QR_p$, so Eve cannot 
discover it, and more than that, she cannot even distinguish it from
random.  
More formally:

\begin{assumption}[DDH]
\label{assumption:ddh}
Let $\mathit{SafePrime}$ be an algorithm that, on input $1^k$, outputs
integers $p$ and $q$ such that $p$ and $q$ are both prime, 
$p$ is $k$-bit long, and $p=2q+1$.
We assume that the following distributions are computationally 
indistinguishable:
$$D_0 = \{(p,q)\leftarrow\mathit{SafePrime}(1^k); g \leftarrow \QR_p;
x\leftarrow \Zq; y\leftarrow \Zq~:~(p,g,g^x,g^y,g^{xy})\}$$
$$D_1 = \{(p,q)\leftarrow\mathit{SafePrime}(1^k); g \leftarrow \QR_p;
x\leftarrow \Zq; y\leftarrow \Zq; z\leftarrow \Zq~:~(p,g,g^x,g^y,g^z)\}$$
\end{assumption}

\problem{ElGamal Encryption}
Consider the following public-key cryptosystem:
\begin{description}
\item [Key Generation:] $G(1^k)$ first runs the
$\mathit{SafePrime}(1^k)$ procedure defined in Problem~1.  It then
picks $g\leftarrow \QR_p$, $s\leftarrow \Zq$.  The secret key will be
$\sk=s$, and the public key will be $\pk= (p,q,g,h)$, where $h=g^s$.
\item[Message space:] The message space corresponding to the public
key $\pk= (p,q,g,h)$ is the set $\QR_p$.
\item[Encryption]: For any $m\in\QR_p$, $\enc(\pk, m)$ parses $\pk$ as
$(p,q,g,h)$, chooses random $r\leftarrow \Zq$, and outputs ciphertext
$c=(g^r, h^rm)$.
\item[Decryption:] $\dec(\sk, \pk, c)$ parses $\pk$ as $(p,q,g,h)$,
and $c$ as $(c_1,c_2)$, and outputs $c_2/c_1^s$ (recall that $s=\sk$).
\end{description}
This is known as the ElGamal Cryptposystem.  Let's prove that it is secure.

\begin{alphabetize}
\item What is our definintion of security for encryption?  
\item To prove that ElGamal is secure, we need to show that here
exists an algorithm FakeCiphertext that satifies the above definition.
Propose such an algorithm.
\item Let's use the decisional Diffie-Hellman assumption 
as described in Problem~1 to prove that ElGamal is secure. 
First, what is the statement we are proving, and what is its contrapositive?
\item Outline a reduction proving this statement:  
Describe the inputs and outputs of the algorithm 
$\A$ that we are given.
Describe the inputs and outputs of 
the algorithm $\B$ that we are trying to build.
\item What should $\B$ do?
\item Suppose $\A$'s advantage was $\epsilon$.  Calculate $\B$'s advantage.
\end{alphabetize}

\problem{Pseudo-Random Generators and One Way Functions}

\begin{alphabetize}
\item What is the definition of a pseudo-random generator (in experiment notation)?
\item Rewrite this definition in English (without experiment notation).
\item What is the definition of a one way function (in experiment notation)?  
\item Rewrite this definition in English (without experiment notation).
\item Explain how a one way function is different from a one way permutation.
\item 
 Let $f: \{0,1\}^{k} \rightarrow \{0,1\}^{k}$ be a one-way function,
and let $G: \{0,1\}^k \rightarrow \{0,1\}^{2k}$ be a pseudorandom
generator.  Define the function $t(x) = G(f(x))$, i.e. $t$ is the
function which, on input $x$ first applies $f$ to $x$, and then
applies $G$ to the result.  Must $t$ be a pseudorandom generator?
\begin{itemize} 
\item 
If not, give a counterexample -- give $f$,$G$, and prove that $f$ is a
one way function and that $G$ is a pseudorandom generator.  Then show
that the $t$ resulting from combining these two functions is not a
PRG, by describing an adversary which breaks the definition of PRG for
this $t$.
\item 
If so, prove it.
\end{itemize}

\item \textit{version 1: We've rewritten this problem to make it more clear. If you've already solved this version, that's great.  Otherwise, look at version 2 below -- it should be clearer.}

\noindent
Let $f: \{0,1\}^{2k} \rightarrow \{0,1\}^{2k}$ be a one way
function, and let $G: \{0,1\}^k \rightarrow \{0,1\}^{2k}$ be a
pseudorandom generator.  Define the function $h(x) = f(G(x))$,
i.e. $h$ is the function which, on input $x$ first applies $G$ to $x$,
and then applies $f$ to the result.  Let's show that $h$ must be a one
way function.
\begin{itemize}

\item 
Suppose there exists an algorithm $\A$ that contradicts the one-wayness
of $h$.
Then what happens when we choose a random $x
\leftarrow \{0,1\}^{2k}$ and run $\A$ on $f(x)$?  Show that if $\A$
succeeds in this case with non-negligible probability, then $f$ is not
one-way.  Give the statement we are proving, its contrapositive,
describe the inputs and outputs of $\A$ that we are assuming, and the
inputs and outputs of $\B$ that we are building, and finally describe
the algorithm $\B$ which uses $\A$ to obtain $x'$ such that $f(x')=f(x)$.


\item Next consider the case where $\A$ succeeds with negligible
probability when run on $f(x)$ (for randomly chosen $x \leftarrow
\{0,1\}^{2k}$).  I.e., $\A$'s probability of outputing $x'$ such that
$h(x')=f(x)$ is negligible.  Show that this implies that $G$ is not a
pseudorandom generator.  Again give the statement we are proving, its
contrapositive, and a reduction.

\item
Finally, argue that this means that $h$ must be one way.
\end{itemize}

\noindent
\textit{3g version 2:}

Let $f: \{0,1\}^{2k} \rightarrow \{0,1\}^{2k}$ be a one way
function, and let $G: \{0,1\}^k \rightarrow \{0,1\}^{2k}$ be a
pseudorandom generator.  Define the function $h(x) = f(G(x))$,
i.e. $h$ is the function which, on input $x$ first applies $G$ to $x$,
and then applies $f$ to the result.  Let's show that $h$ must be a one
way function.
\begin{itemize}
\item What is the statement we proving (what are we given, and what do we want to show is implied)?  And what is the contrapositive?
\item This means we suppose we are given an algorithm $\A$ with what inputs and outputs?  What are we assuming about this algorithm $\A$? What does it mean for $\A$ to succeed on a given input?

\item  We want to show that given such an $\A$, either we can build $\B$ which \underline{~~~} or we can build $\B$ which \underline{~~~}.  Describe inputs and outputs of both possibilities for $\B$.
\item 
What happens when we choose a random $x
\leftarrow \{0,1\}^{2k}$ and run $\A$ on $f(x)$?  There are two cases: either $\A$ is such that it will succeed with nonnegligble probability, or not.
Let's consider the first case.  Show that if $\A$
succeeds on these inputs with non-negligible probability, then $f$ is not
one-way. Give the inputs and outputs of $\B$ that we are building (it will be one of those you specified above), and finally describe the algorithm $\B$
which uses $\A$ to obtain $x'$ such that $f(x')=f(x)$.


\item Next consider the case where $\A$ succeeds with negligible
probability when run on $f(x)$ (for randomly chosen $x \leftarrow
\{0,1\}^{2k}$).  I.e., $\A$'s probability of outputing $x'$ such that
$h(x')=f(x)$ is negligible.  Show that this implies that $G$ is not a
pseudorandom generator.  Again give the inputs and outputs of $\B$ that we are building (one of those above), and finally describe the algorithm $\B$ which uses $\A$ to break the pseudorandomness of $G$.


\item
Finally, argue that this means that $h$ must be one way.
\end{itemize}

\end{alphabetize}

 \end{document}