\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{epsfig}

\def\handoutdate{August 3, 1998}
\def\handoutname{Problem Session 1 Solutions}
\def\handoutnumber{7S}
\input{defs}


% ========================================================================

\begin{document}

\courseheader

\bigskip
\begin{center}
{\Large{\bf Problem Session 1 Solutions}}
\end{center}

\bigskip

\newcommand{\mmod}[1]{\,\,(mod\,\,#1)}

\def\cycle{{\sc Cycle}}

{\bf Problem 1.1: One-way functions can't have a small range}

Prove that a one-way function cannot have a polynomial sized range.
Namely show that if $f$ is a one-way function then for every
polynomial $p$ there exists an infinite set $N_p$ such that 
$|\set{f(x)}{x\in\bits^n}|> p(n)$ for all $n\in N_p$.

\bigskip
{\bf Solution}

\begin{center}
\epsfig{file=sol-1-1.eps}
\end{center}
Assume that it is {\bf not} the case that
\[ \left| \left\{ f(x) | x \in \{0,1\}^n \right\} \right| > p(n) \quad \text{   for infinitely many n's} \]
Then $\exists$ polynomial $p()$ s.t.
\[ \left| \left\{ f(x) | x \in \{0,1\}^n \right\} \right| \leq p(n) \quad \text{   for sufficiently large n} \]

We design an inverting algorithm $A(1^n, y)$ which chooses a $z$ at random: $z \stackrel{R}\leftarrow \{0,1\}^n.$

We claim that $A()$ inverts with non-negligible probability:
\[ \exists y_0 \text{  s.t. } \quad |f^{-1}(y_0)| = |\{x | f(x) = y_0\}| \geq \frac{1}{p(n)} \{0,1\}^n \]
This $y_0$ is an element with a large pre-image.
\begin{equation} 
\begin{split}
\Pr \left[ f(z) = y | x \stackrel{R}{\leftarrow}\{0,1\}^n, y \leftarrow f(x), z\leftarrow A(1^n, y) \right] 
	& \geq \Pr [ y = y_0 ] \cdot \Pr [f(z) = y | y = y_0 ] \\
 	& \geq \frac{1}{p(n)} \cdot  \frac{1}{p(n)} = \frac{1}{p^2(n)}
\end{split}
\end{equation}
This is a contradiction.

We have therefore shown that for a non-negligible set of numbers, we
can invert $f(x)$, which of course implies that $f(x)$ is not a one-way-function.

\clearpage
{\bf Problem 1.2: One-way functions can't have small cycles}

Prove that one-way functions cannot have polynomially bounded cycles.
Namely for any $f$ define $\cycle_{f(x)}$ to be the smallest positive
integer $i$ such that $f^i(x)=x$. Prove that if $f$ is one-way then
for every polynomial $p$ there exists an infinite set $X_p$ such
that $\cycle_{f(x)}>p(|x|)$ for all $x\in X_p$.

\bigskip
{\bf Solution}

Assume the above is not the case, then we know $\exists$ a polynomial
$p()$ such that $\cycle_{f(x)} \leq p(|x|)$ for sufficiently large
number of $x\in X_p$. We can therefore try to design an inverting
algorithm.

{\bf  $A(1^n,y)$: }
\begin {itemize}
\item let $z \leftarrow y$.
\item while $f(z) \neq y$, $z \leftarrow f(z)$
\item output $z$.
\end{itemize}

This algorithm will run until the length of the cycle, and must stop
after at most $p(|y|)$ iterations. The output is $z$ such that $f(z) =
y$, or alternatively, the output is $f^{-1}(y)$. This runs in
polynomial time.

Therefore, $A()$ succeeds in finding an inverse with probability 1,
which goes against the assumption that $f()$ is a one way function, so
we have a contradiction. Therefore, such a cycle cannot exist.

\clearpage
{\bf Problem 1.3: DES and PRFs}

Let $\bar{m}$ be the bitwise complement of the string $m$. 
Let $\DES_K(m)$ denote the encryption of $m$ under DES using key $K$. 
It is not hard to see that if 
\[ c = \DES_K(m) \]
then 
\[ \bar{c} = \DES_{\bar{K}}(\bar{m}) \]
We know that a brute--force attack on DES requires searching a space of 
$2^{56}$ keys. This means that we have to perform that many DES 
encryptions in order to find the key, in the worst case.  
\begin{enumerate}
\item  Under {\em known plaintext attack} (i.e., you are given a 
single pair $(m,c)$ where $c=\DES_K(m)$) do the equations above 
change the number of DES encryption you perform in a brute--force attack
to recover $K$?

{\bf Solution}
We presumably have $(c,m)$ and want $K$.  While this implies that we
also know $(\bar{c}, \bar{m})$ under $\bar{K}$, there is not an
obvious way to use it in a brute force attack. We still need to go
over all possible keys. We can halve the number of keys we try by
trying $m$ and then $\bar{m}$ and comparing to $c$ and $\bar{c}$
respectively, but this doubles the number of texts we check (so not an
improvement).

$\rightarrow 2^{56}$.

\item What is the answer to the above question in the case of 
{\em chosen plaintext attack} (i.e., when you
are allowed to choose many $m$'s for which you get the pair $(m,c)$ 
with $c=\DES_K(m)$)? 

{\bf Solution}
This time, we can use it to our advantage. We ask for $(m,c_1)$ and
$(\bar{m},c_2)$, Where the $c_x$ are encryptions under $K$ of the
respective messages.

Now we can, with each brute-force encryption we try, check two keys at
once:
\begin{itemize}
\item For every key that starts with $0$, encrypt $m$.
\item If the result is $c_1$, the key we brute forced was correct.
\item If the result is $c_2$, the key we brute forced was the
complement of the right key.
\end{itemize}

$\rightarrow 2^{55}$

\item Suppose we think of DES as a family of pseudorandom functions, each
function in the family being specified by a 56 bit key, and mapping 64
bits to 64 bits. We would like to get a new pseudorandom function
family $F$ in which each function maps $64$ bits to $128$ bits.
Consider the following constructions. Do you think they are good or
bad? Ie.~is the specified $F$ a pseudorandom function family or not?

Below, ``$\Concat$'' denotes concatenation of strings and $[y]_{56}$
means take the first 56 bits of the 64 bit string $y$.

{\bf Solution}
A function is pseudorandom if we cannot construct a distinguisher $D$
that can decide if it is being handed a truly random function or our
function.

\begin{enumerate}
\item $F_K(x)=\DES_K(0^{64})\Concat \DES_K(x)$

{\bf Solution}
We can construct a distinguisher fairly easily: If we query for
$f(0)$, we will discover that the output is repeated.  Alternatively,
we can query for two distinct inputs, and simply compare the first 64
bits. If they are equal, we are using $f(x)$, otherwise, we were given
a truly random function.  SO this is NOT a good PRF.

\item $F_K(x)=\DES_K(x)\Concat \DES_K(\bar{x})$

{\bf Solution}
We ask for both $m$ and $\bar m$. If we
find that the first half of one equals the second half of the other
(and vice versa), we know we are looking at $f()$.

\item $F_K(x)=\DES_K(x)\Concat \DES_{\bar{K}}(x)$

{\bf Solution}
Since we know that $DES_K(x) = \overline{DES_{\bar{K}}(\bar x)}$, we
can use it to our advantage.  We again ask for $m, \bar m$. If the
second half of one encryption is the same as the first half of the
other, and vice-versa, then we know that we are using $f(x)$.

\item $F_K(x)=\DES_{0^{56}}(x)\Concat \DES_K(x)$

{\bf Solution}
This is no good, because we know how DES works, and can ourselves
compute the first half of the encryption. Therefore, to distinguish,
submit any $m$ desired, and check if the first half of the response
corresponds to the DES encryption of $m$ with a key set to $0^{56}$.

\item $F_K(x)=\DES_{K_1}(x)\Concat \DES_{K_2}(x)$ where
$K_1= [\DES_K(0^{64})]_{56}$ and $K_2=[\DES_K(1^{64})]_{56}$

{\bf Solution} This appears to be a good pseudo-random scheme: This
can be viewed as a two-part system. The first creates the two keys,
and the second part uses the keys to encrypt the message.  Since we
had already assumed DES to be a good pseudo-random permutation,
finding K from $K_1,K_2$ should be hard, and there should be no
distinguishable relationship between the two keys. Since there isn't a
poly-time distinguishable relationship between the two keys, there
isn't going to be any way to tell anything about the two halves of the
message (as opposed to two random strings).  This can be formalized
into a proof by showing that if there was a way, then there would have
been a way to distinguish $K_1$ from $K_2$, which goes against the
assumption that DES is a good PRF.
\end{enumerate}
\end{enumerate}

\clearpage
{\bf Problem 1.4: Square roots}
\begin{enumerate}
\item Let $p$ be a Blum-prime, namely $p$ is a prime such that
$p = 3 \mmod{4}$. 
Describe a polynomial time algorithm for taking square root modulo
$p$. That is, given $a$ which is a square mod $p$, find an $x$ such that
$x^2=a \mmod{p}$.  
{\em Hint:} Show that $a^{\frac {p-1} 2 +1} = a \mmod{p}$, and
then write $p$ as $p=4m+3$.

{\bf Solution}

Since $p$ is prime, $\exists g$ generator for ${\mathbb Z}_p^*$. 

Given $a \in {\mathbb Z}_p^*$, which is a square ($a \equiv x^2 \pmod
p$). We know that
\[ a^{\frac{p-1}{2}} \equiv (x^2)^{\frac{p-1}{2}} \equiv x^{p-1}
\equiv 1 \pmod p \]
\[ a^{\frac{p-1}2 + 1} \equiv a \pmod p \]

Now, we know that $p$ is a Blum-prime, which means that $p \equiv 3
\bmod 4$, or otherwise stated: $p = 4m + 3$ for some integer $m$.

\begin{equation*}
\begin{split}
a^ {\frac{p-1}2 +1} \equiv a ^{\frac{4m+2}2 + 1} & \equiv a ^{2m + 2}
\equiv a \pmod p \\
& {(a ^ {m+1})}^2 \equiv a \pmod p
\end{split}
\end{equation*}

Therefore, we have found the square root, and it is $a^{m+1}$.

\bigskip

\item Does 20 have a square root modulo 77? 
How about 23 modulo 77?  

{\bf Solution}

A number is a QR in a field iff it is a quadratic residue in all the
prime factors of the field. In this case, 7 and 11.

\begin {equation*}
\begin{split}
77 = 7 \cdot 11 \quad \text{:} \quad & 20 \bmod 11 = 9 \bmod 11 = 3^2 \bmod 11 \quad
 \Longrightarrow QR \\
 & 20 \bmod 7 = 6 \bmod 7 = -1 \bmod 7 \quad \Longrightarrow QNR \\
\end{split}
\end{equation*}

Therefore, 20 is not a quadratic residue mod 7.

\begin {equation*}
\begin{split}
77 = 7 \cdot 11 \quad \text{:} \quad & 23 \bmod 11 = 1 \bmod 11 = 1^2 \bmod 11 \quad
 \Longrightarrow QR \\
 & 23 \bmod 7 = 2 \bmod 7 = 4^2 \bmod 7 \quad \Longrightarrow QR \\
\end{split}
\end{equation*}

Therefore, 23 is a quadratic residue mod 7.

\end{enumerate}

\clearpage
{\bf Problem 1.5: Relationship between number theory problems} 

Let $n$ be the product of two primes $n=pq$.  Describe reducibilities
between the following problems (e.g. if we can factor we can invert
RSA.) Don't prove anything formally, just state the result.

\begin{enumerate}

\item computing $\phi(n)$

\item factoring $n$

\item computing $QR_n(a)$ for some $a \in Z_n^*$

\item computing square roots modulo $n$

\item computing $k$-th roots modulo $n$, where $gcd(k,\phi(n))=1$

\end{enumerate}

{\bf Solution}

We know that (2), (1), and (4) are equivalent:  Given $(p,q)$ from the
factoring algorithm we can compute $\phi(n) = (p-1)(q-1)$. We can also
compute, for any $a$, $sqrt(a)$, although this can get fairly
hairy (the algorithm can be found in books on the subject).

Going backwards from sqrt, if we have a way to find square roots, we can
factor $n$ with the fact that given two non-inverse square roots, $x
\neq -y ; x^2 = y^2 \pmod n$, we know that $gcd((x+y),n)$ is a
prime factor of $n$, so we can factor. In order to get those pairs,
simply take a random number and square it. Then, submit it to the
square-root box. Half the time, it will respond with a useful answer,
which you can use to factor. Repeat until it does.

Going backwards from $\phi(n)$, If you have $n$ and $\phi(n)$, then
$n - \phi(n) + 1 = pq - (p-1)(q-1) + 1 = pq - pq + p + q - 1 + 1 = p +
q$. Going from $p+q$ to $p,q$ such that $pq = n$ is fairly fast.

We also know that if we can factor (2), then we can easily compute QR
(3), and in a manner similar to computing sqrts, compute (5).

It is not known whether (3) or (5) are enough to get (1), (2), or (4).


\end{document}
