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



\begin{document}
\exam{Midterm Exam}{March 21, 2007}{Andrew Chin}

\problem{Diffie Hellman Key Exchange}

\begin{alphabetize}
\item
We would like to show that Alice's key ($K_A$) is equal to Bob's key ($K_B$).  

\begin{eqnarray*}
K_B &=& K_A \\
X^y \mod p &=& Y^x \mod p \\
\left(g^x\right)^y \mod p &=& (g^y)^x \mod p \\
g^{xy} \mod p &=& g^{yx} \mod p
\end{eqnarray*}
Because $xy = yx$, $K_A = K_B$.

We also would like to show that Eve is unable to compute the shared key.  Here is the information that Eve knows: 
$p$, $g$, $g^x \mod p$, $g^y \mod p$.  To compute the key, Eve would need to know both $x$ and $y$, but she can
not compute either $x$ or $y$ given the information she knows.  (TODO:  expand here)

\item
	\begin{itemize}
	 \item When $p=13$, $g = 2$:\\
		\begin{tabular}{r|l l}
		$x$ & $X$\\
		\hline 
		0 & $2^0 \mod 13 $&$= 1 =1^2$ \\
		1 & $2^1 \mod 13 $&$= 2$\\
		2 & $2^2 \mod 13 $&$= 4 = 2^2$\\
		3 & $2^3 \mod 13 $&$= 8$ \\
		4 & $2^4 \mod 13 $&$= 3 = 4^2$ \\
		5 & $2^5 \mod 13 $&$= 6$ \\
		6 & $2^6 \mod 13 $&$= 12 = 5^2$ \\
		7 & $2^7 \mod 13 $&$= 11$ \\
		8 & $2^8 \mod 13 $&$= 9 = 3^2$\\
		9 & $2^9 \mod 13 $&$= 5$ \\
		10 & $2^10 \mod 13 $&$= 10 = 6^2$ \\
		11 & $2^11 \mod 13 $&$= 7$ \\
		12 & $2^12 \mod 13 $&$= 1$\\
		\hline

		\end{tabular}
		The probability that $X$ will be a square is $\frac{6}{13}$
	\item The probability that $Y$ will be a square is also $\frac{6}{13}$
	\item $K_A = K_B = X^y \mod p = Y^x \mod p$ will be a square $\frac{6}{13}^{th}$ of the time.
	\item In general, the probability that $X = g^x$ will be a square is $\frac{p-1}{2p}$.   If $p$ is a prime, and $<g> = \mathbb{Z}_p^*$, then $g^x$ is a square iff $x$ is even.  Because $x \gets \mathbb{Z}_p$ and there are $\frac{p-1}{2}$ even numbers in $\mathbb{Z}_p$, Pr[$X$ is a square] = Pr[$x$ is even] = $\frac{\frac{p-1}{2}}{|\mathbb{Z}_p|} = \frac{\frac{p-1}{2}}{p} = \frac{p-1}{2p}$
	\item The probability that $Y = g^y$ will be a square is the same probability that $X$ will be a square
	\item

		Asking when $K_A = K_B$ will be a square is asking `When is $X^y$ a quadratic residue modulo p?' or:
		\begin{eqnarray*}
  		&&Pr[X^y = a^2 \pmod{13}] \\
		&=& Pr[\left(b^2\right)^y = a^2 \pmod{13} | X = b^2] \\
		&=& Pr[\left(b^y\right)^2 = a^2 \pmod{13} | X = b^2]  \\
		&=& Pr[X = b^2] 
		\end{eqnarray*}		
		The probability that he key $K_A$ will be square is the same as the probability that $X$ is square.

	\end{itemize}
\item 
	\begin{itemize}
	\item If $p=23$ and $q = 11$ and $g= 4$: 

	\begin{tabular}{r|l}
	$i$ & $4^i$ \\
	\hline
	0 & 1\\
	1 & 4\\
	2 & 16\\
	3 & 18\\
	4 & 3\\
	5 & 12\\
	6 & 2\\
	7 & 8 \\
	8 & 9\\
	9 & 13\\
	10 & 6\\
	11 & 1\\
	\end{tabular}

		$|\langle g \rangle | = 11 = q$

	\item In our example where $p = 23$, and $g = 4$, $X$ will always be a square.
	\item When $p =23$ and $g = 4$, $Y$ will always be a square.
	\item When $p=23$ and $g=4$, $X$ will always be a square.
	\item If $g \gets QR_p$, then $g$ is a square (i.e. there exists some $a$ such that $a^2 = g \mod p$).  $X = g^x$ for $x \gets \mathbb{Z}_p$.   Because $g$ is a square, $X = (a^2)^x = a^{2x} = a^{x2} = (a^x)^2$.  We can see that if $g$ is a square, then $X$ will always be a square. 
	\item The same it true for $Y = g^y$ (because $x$ and $y$ are both chosen from the same distribution). $Y = (a^2)^y = a^{2y} = a^{y2} = (a^y)^2$.  We can see that if $g$ is a square, then $Y$ will always be a square.
	\item $K_B = X^y \pmod{p}$.  Using what we know about $X$ and $g$, we see that:  $K_B = X^y = (g^x)^y = g^{(xy)} = (a^2)^{(xy)} = a^{(2xy)} = (a^{(xy)})^2$.  We see that $K_B$ will always be a square if $g$ is a square.  
	\item In general, if $g \gets QR_p$, then $K = K_A = K_B$ will always be in $QR_p$, which is considerably smaller than the size of $\mathbb{Z}_p$
	

\end{itemize}



\end{alphabetize}

\problem{ElGamal Encryption}


\begin{alphabetize}
\item
	We consider an encryption scheme to be secure if there exists an algorithm
FakeCiphertext such that for all $m$, the following two distribution are equivalent:
\[D_{Enc}(m) = \{(PK, SK) \gets GPK(1k); c \gets Enc(PK,m); (c, m, PK)\} \]
and
\[ D_{Fake} (m)\{(PK, SK) \gets GPK(1k); \hat{c} \gets FakeCiphertext(PK, |m|); (\hat{c}, m, PK)\}\]

\item
	For ElGamal encryption, here is a potential FakeCiphertext:

FakeCiphertext, on input $(PK, |m|)$ will:\\
Parse $PK$ into $(p,q,g,h)$\\
Choose a random $m' \gets QR_p$\\
Choose a random $r \gets \mathbb{Z}_q$ \\
Calculate $c' = (g^r, h^r m)$ \\
Output $c'$

\item To show that this is secure, we want to show that $D_{Enc}(m) \approx D_{Fake}(m)$.  Using the DDH assumption:
If $D_0 \approx D_1$ then $D_{Enc}(m) \approx D_{Fake}(m)$.  We can show this by showing the contrapositive, that is:
If $\neg (D_{Enc}(m) \approx D_{Fake}(m)$) then  $\neg (D_0 \approx D_1)$

\item Here is the reduction:

Assume we have $\A$ which can distinguish between $D_{Enc}$ and $D_{Fake}$ successfully with a probability of $\epsilon$.  $\A$ will take as inputs 
$(c,m,PK)$ and will output a $1$ if the input is from $D_{Enc}(m)$ and will output a $0$ if the input is from $D_{Fake}(m)$.  Using $\A$, we can construct a 
$\B$ which will be able to distinguish between $D_0$ and $D_1$.  On input $(p,g,x,y,z)$, $\B$ will output a $0$ if the input is from $D_0$ and will
output a $1$ if the input is from $D_1$.

\item Here is how we would build $\B$.

On input $(p,g,x,y,z)$:\\
Using $p$ (which is a safe prime), calculate $q = \frac{p-1}{2}$\\
Generate $PK = (p,q,g,x)$\\
Generate $c = (y,m,z*m)$\\
$b \gets \A(c,m,PK)$\\
If $b = 1$, then $\A$ thinks that it was given an input from $D_{Enc}$, so output $0$.
If $b = 0$, then $\A$ thinks that it was given an input from $D_{Fake}$, so output $1$.

\item

Assume $\A$'s advantage was $\epsilon$.  That is:
\begin{eqnarray*}
Pr[\A\ \text{suceeds}] &=& |Pr[(PK,SK) \gets GPK(1^k); c \gets Enc(PK,m); b \gets \A(c,m,PK) : b=1] - \\
&&Pr[(PK,SK) \gets GPK(1^k), c' \gets 
 FakeCiphertext(PK,|m|); b' \gets \A(c',m,PK) : b = 1] | \\
&=& \epsilon
\end{eqnarray*}

$\dots$ not finished $\dots$


\end{alphabetize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem{Pseudo-Random Generators and One Way Functions}%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{alphabetize}
\item  G is a PNG iif $D_{PR}$ is indistinguishable from $D_{Random}$:

\[D_{PR} = \{ x \gets \{0,1\}^k : G(x) \} \]
\[D_{Random} = \{ R \gets \{0,1\}^{2k} : R \} \]


\[ | Pr[x' \gets D_{PR}; b \gets \A(x'); b = 0] - Pr[x \gets D_{Random}; b \gets \A(x); b = 0] | = \epsilon\]


\item A function $G()$ is a pseudo-random generator if there exists a probabilistic polynomial time algorithm $\A$ that can't distinguish between random bits and pseudorandom bits.  Or:  it can only distinguish between them with a probability $\epsilon$ which is negligible.

\item A function $f : \{0,1\}^* \rightarrow \{0,1\}^*$ is a one-way function if: 

$\forall\ \text{ppt}\ \A\ \exists\ v()$ such that $v()$ is negligible and  $Pr[ x \gets \{0,1\}^*; x' \gets \A(f(x)) : f(x') = f(x)] = v(k)$

\item A function $f : \{0,1\}^* \rightarrow \{0,1\}^*$ is a one-way function if there exists a negligible function $v(k)$ and a probabilistic polynomial time algorithm $\A$ such that if $x' = A(f(x))$, the probability that $f(x)$ equals $f(x')$ is equal to $v(k)$ (i.e., negligible)

\item A one-way function is a function that is hard to invert (that is, given $f(x)$, it is hard to figure out $x$.  A one-way permutation is a permutation that is also hard to invert.  A permutation is bijective (that is, for sets $X$ and $Y$, there is exactly one $x \in X$ for every $y \in Y$ such that $f(x) = y$, while a function is not bijective (it is only surjective or injective).  

\item 

\begin{itemize}
 \item If $f()$ is a one-way function and $G()$ is a pseudo-random number generator, then $h(x) = f(G(x))$ is also one-way.  The contrapositive is:
If $h()$ is not one-way, then $f()$ is not one-way or $G()$ is not a pseudo-random number generator.

\item We suppose we are given an algorithm $\A$ that can invert $h()$, that is on input $y$, $\A$ will output $x$ such that $h(x) = y$

\item We want to show that given such an $\A$, either we can build $\B$ which can  invert $f()$ (that is, given input $y$, it will output $x$ such that $y = f(x)$), or we can build $\B$ which can distinguish the output of $G()$ from random bits.

\item $c \gets \A(f(x))$.  If $\A$ succeeds, then we can build a $\B$ which will use $\A$ to obtain $x'$ such that $f(x') = f(x)$.

$\B$ will take as input $x$:\\
$c \gets \A(x)$\\
So: $x = f(G(c))$\\
If $x = f(a)$, then: $f(a) = f(G(c))$\\
$a = g(c)$ \\
Output $a$

\item If $\A$ fails (or rather, succeeds with a negligible probability), then we can build a $\B$ which will use $\A$ to show that $G$ is not a pseudorandom generator.  That is, $\B$ can distinguish between $_D{PR}$ and $D_{Random}$.

$\B$ will take as input $x = f(a)$ (where $a$ is $2k$ random bits):\\
$c \gets A(x)$\\
$f(G(c)) \neq x$\\
$f(G(c)) \neq f(a)$\\
$a \neq G(c)$\\
we know that $a$ is random, and we have just shown that $a$ is distinguishable from $G(c)$.
(note, here $\neq$ means `distinguishable')

\item We have shown that if we assume that there exists an $\A$ which tries to invert $h$, we can construct a $\B$ which can either invert $f$, or show that the output of $G$ is not random.  Because we know that $f$ is one-way and we know that $G$ is pseudo-random, then our assumption that an $\A$ exists is false, and $h$ must be one-way.

\end{itemize}


\end{alphabetize}


\end{document}
