\documentstyle[11pt,twoside]{article}

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


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

\begin{document}

\courseheader

\bigskip
\begin{center}
{\Large{\bf Problem Session 1}}
\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 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 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$?

\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)$)? 

\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$.

\begin{enumerate}
\item $F_K(x)=\DES_K(0^{64})\Concat \DES_K(x)$
\item $F_K(x)=\DES_K(x)\Concat \DES_K(\bar{x})$
\item $F_K(x)=\DES_K(x)\Concat \DES_{\bar{K}}(x)$
\item $F_K(x)=\DES_{0^{56}}(x)\Concat \DES_K(x)$
\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}$
\end{enumerate}

\end{enumerate}

\bigskip
{\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$.
\item Does 20 have a square root modulo 77? 
How about 23 modulo 77?  
\end{enumerate}

\bigskip
{\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{itemize}

\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{itemize}


\end{document}