\iffalse

NOTE:  If you do not collaborate with anyone, simply remove the '****
INSERT COLLABORATORS HERE****' and replace it with 'nobody.' Don't erase
the collaboration statement!  Thanks.


INSTRUCTIONS: (if this is not ps1, use the right file name)

  Clip out the ********* INSERT HERE ********* bits below and insert
appropriate TeX code.  Once you are done with your file, run

  ``latex ps1.tex''

from the Athena shell.  If your TeX code is clean, the latex will exit
back to a prompt.  Once this is done, run

  ``dvips ps1.dvi''

which should print your file to the nearest printer.  There will be
residual files called ps1.log, ps1.aux, and ps1.dvi.  All these can be
deleted, but do not delete ps1.tex.

\fi
\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{latexsym}
\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 6.875J/18.425J Cryptography and
  Cryptanalysis} \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{\al}{\alpha}
\newcommand{\Z}{\mathbb Z}
\newcommand{\N}{\mathbb N}

\begin{document}
\handout{P5}{DUE: October 24, 2001}{Instructor: Anna Lysyanskaya}
{Teaching Assistant: Moses Liskov}
{*********** INSERT YOUR NAME HERE ***********: PS 5}

I collaborated with ******** INSERT COLLABORATORS OR `nobody' HERE **********.

\bigskip

\section*{Problem 1: Fun with primitives}

(35 points) Let $F: \{0, 1\}^* \rightarrow \{0, 1\}^*$ be a one-way
function.  Let $G: \{0, 1\}^* \rightarrow \{0, 1\}^*$ be a
pseudorandom generator.  Finally, let $P: \{0, 1\}^* \rightarrow \{0,
1\}^*$ be a one-way permutation.  (Refer to lecture notes from lecture
10 for rigorous definitions of these primitives.)  For each of the
following, answer either ``yes'' or ``no.''  If you answer ``yes''
give an intuitive argument to support your answer.  If you answer
``no'' give a counterexample.\footnote{To give a counterexample, you
may need to assume the existence of some other $F'$, $G'$, or $P'$,
and then describe how $F$, $G$, or $P$ could be constructed from them
such that $F$, $G$, or $P$ is still a OWF (or PRG or OWP) but the
answer to the question is no for that $F$, $G$, and $P$.}  For at
least {\em one} of your ``yes'' answers, if you give any, give an
actual proof (5 points) of your answer.

\bigskip
{\bf (a)} Is $G \circ G$ a PRG?

\bigskip{\bf Solution:}
***************** INSERT PROBLEM 1a SOLUTION HERE ***************

\bigskip
{\bf (b)}  Is $F \circ F$ a OWF?

\bigskip{\bf Solution:}
***************** INSERT PROBLEM 1b SOLUTION HERE ***************

\bigskip
{\bf (c)}  Is $P \circ P$ a OWP?

\bigskip{\bf Solution:}
***************** INSERT PROBLEM 1c SOLUTION HERE ***************

\bigskip
{\bf (d)}  Is $P \circ F$ a OWP?

\bigskip{\bf Solution:}
***************** INSERT PROBLEM 1d SOLUTION HERE ***************

\bigskip
{\bf (e)}  Is $G \circ P$ a PRG?

\bigskip{\bf Solution:}
***************** INSERT PROBLEM 1e SOLUTION HERE ***************

\bigskip
{\bf (f)}  Is $G \circ F$ a PRG?


\bigskip{\bf Solution:}
***************** INSERT PROBLEM 1f SOLUTION HERE ***************

\section*{Problem 2: Hard-core bits}

(20 points) Let $b: \{0, 1\}^* \rightarrow \{0, 1\}$ be an efficiently
computable, nontrivial predicate (with respect to sampling with the
uniform distribution).

\bigskip
{\bf (a)} Prove that if OWP's exist, there is a OWP $P: \{0, 1\}^*
\rightarrow \{0, 1\}^*$ such that $b$ is a hard-core predicate of $P$.
Here you may assume that $b$ is of the form $b_r(x) = r \cdot x \bmod
2$, where $|r| = |x|$.

\bigskip{\bf Solution:}
***************** INSERT PROBLEM 2a SOLUTION HERE ***************

\bigskip
{\bf (b)} Prove that if $P: \{0, 1\}^* \rightarrow \{0, 1\}^*$ is an
efficiently computable permutation, and $b$ is a hard-core predicate
of $P$, then $P$ is a OWP.  Also, prove that if $F: \{0, 1\}^*
\rightarrow \{0, 1\}^*$ and $b(x)$ is hard to compute given only
access to $F(x)$, then $F$ is not necessarily a OWF.

\bigskip{\bf Solution:}
***************** INSERT PROBLEM 2b SOLUTION HERE ***************

\section*{Problem 3: OWP $\Rightarrow$ PRG}

(20 points) Let $P: \{0, 1\}^* \rightarrow \{0, 1\}^*$ be a OWP,
and let $b$ be a hard-core predicate of $P$.  Consider the following
construction, due to Blum, Blum and Shubb, of a PRG.  To generate
a key $PK$, just use the key generation algorithm for $P$.  Let $s$
denote the input, where $|s| = k$.

Let $x_0 = s$, and let $x_i = P(x_{i-1})$ for all $i > 0$.  Define

$$G(s) = b(s = x_0) \circ b(x_1) \circ \ldots \circ b(x_k)$$

\bigskip
{\bf (a)}  Prove that $G$ is {\em next-bit unpredictable}.  That is, 
that 

\begin{tabbing}
$\forall \{A\}_n~\exists f \in neg~\forall k$\\
$\Pr[$\=$(\alpha, j) \leftarrow A_k; s \leftarrow \{0, 1\}^k;$\\
\>$r \leftarrow G(s); b \leftarrow A_k(\alpha, r_1 \circ \ldots
\circ r_j): b = r_{j+1}] \leq 1/2 + f(k)$
\end{tabbing}

where $r = r_1 \circ r_2 \circ \ldots \circ r_{k+1}$.

\bigskip{\bf Solution:}
***************** INSERT PROBLEM 3a SOLUTION HERE ***************


\bigskip
{\bf (b)} Prove that for {\em any} $G$, if $G$ is next-bit
unpredictable then it is a pseudorandom generator (in the sense we
used in lecture - that $G$ is indistinguishable from random).

\bigskip{\bf Solution:}
***************** INSERT PROBLEM 3b SOLUTION HERE ***************

\section*{Problem 4: Pumping Pseudorandomness}

(20 points) Suppose you are given a PRG $G$ such that $|G(x)| = |x| +
1$, and a polynomial $p$.  Construct a $G'$ such that $|G'(x)| =
p(|x|)$, and prove that $G'$ is also a PRG.  Your proof should be
along similar lines to the proof you use in problem 3. 

\bigskip{\bf Solution:}
***************** INSERT PROBLEM 4 SOLUTION HERE ***************

\section*{Problem 5: Predictable OWFs}

(5 points)\footnote{Consider this a challenge problem.  At only 5
points it should not seriously impact your grade whether you do this
problem or not.}  Let $F: \{0, 1\}^* \rightarrow \{0, 1\}^*$ be a
length-preserving one-way function.  Let $b_i(x)$ be a predicate which
returns the $i^{th}$ bit of $x$.  Construct a length preserving
function $F'$, and prove that $F'$ is (1) a one-way function, and (2)
for any $1 \leq i \leq k$, it is easy for random $x$ of length $k$ to
compute $b_i(x)$, given only $F'(x)$ as input.

\bigskip{\bf Solution:}
***************** INSERT PROBLEM 5 SOLUTION HERE ***************


\end{document}