
\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{latexsym}
\input{texdefs}

\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 CS195-7: Introduction to Cryptography} \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{\ho}[4]{\handout{#1}{#2}{Instructor:
#3}{}{Handout #1: #4}}

\newcommand{\solution}[1]{#1}
\newcommand{\set}[1]{\{#1\}}
\def\prf{{\sf PRF}}

\begin{document}
\handout{PS7}{DUE: November 12, 2002}{Instructor: Anna Lysyanskaya}
{\solution{*** Your name here *** }}{Problem Set 7}

\section*{PRF Candidates}
Suppose that $\set{F_S:\bit^{k}\mapsto\bit^{k}~|~s\in\bit^{k}}$ is a
pseudo-random family of functions from $k$-bit input to $k$-bit
output, indexed by a $k$-bit key (``seed'').  We would like to
construct a new \prf\ family. Consider the following constructions,
and for each show whether it is good or bad (namely whether the
specified family is pseudo-random or not, for the appropriate domain
and range).  If your answer is
``yes,'' give an outline of a reduction.  If your answer is 
``no,'' give an example $F$, some convincing evidence that $F$ is a 
PRF, and an attack on the construction of $F^i$ when it is based
on your $F$.

Below, ``$\circ$'' denotes concatenation, and $\bar{x}$ denotes the
bitwise negation of $x$.
\begin{itemize}
\item[(a)] $F^1_S(x) = F_S(x) \circ F_S(\bar{x})$.

\item[(b)] $F^2_S(x) = F_{0^k}(x) \circ F_S(x)$.

\item[(c)] $F^3_S(x) = F_{S_1}(x) \circ F_{S_2}(x)$, where
$S_1=F_S(0^k)$ and $S_2=F_S(1^k)$.

\item[(d)] $F^4_S(x) = F_S(x)\oplus x$.

\item[(e)] $F^5_S(x) = F_S(x)\oplus S$.
\end{itemize}

\end{document}
