\documentclass[a4paper]{article}

\usepackage[english]{babel}
\usepackage[utf8x]{inputenc}
\usepackage{amsmath}
\usepackage{enumerate}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{xspace}

        \newtheorem{theorem}{Theorem}
        \newtheorem{lemma}{Lemma}
        \newtheorem{proposition}{Proposition}
        \newtheorem{corollary}{Corollary}
        \newtheorem{definition}{Definition}
        \newtheorem{assumption}{Assumption}
        \newtheorem{claim}{Claim}
        \newtheorem{problem}{Problem}
        \newtheorem{construction}{Construction}
\DeclareMathOperator*{\expe}{\mathbb{E}}

\newcommand{\class}[1]{{\ensuremath{\mathsf{#1}}}}
\newcommand{\enc}{\ensuremath{\class{Enc}}\xspace}
\newcommand{\dec}{\ensuremath{\class{Dec}}\xspace}
\newcommand{\zo}{\ensuremath{\{0,1\}}\xspace}
\newcommand{\poly}{\ensuremath{\class{poly}}\xspace}
\newcommand{\negl}{\ensuremath{\class{ngl}}\xspace}
\newcommand{\mac}{\ensuremath{\class{Mac}}\xspace}
\newcommand{\ver}{\ensuremath{\class{Vfy}}\xspace}
\newcommand{\gen}{\ensuremath{\class{Gen}}\xspace}


\usepackage{graphicx}
\usepackage[colorinlistoftodos]{todonotes}

\title{CSE 5852: Problem Set 5}
\date{Due: October 31, 2016}
%\author{You}

\begin{document}
\maketitle

This homework combines ideas from pseudorandom generators, pseudorandom functions and message authentication codes.  Please be clear what definitions are used in your proofs.  Also since there are many definitions feel free to copy and paste from the problem set latex source.

\section{Pseudorandom Number Generators}
Recall the second definition we gave of a pseudorandom generator. 
\paragraph{All efficient tests}
That is consider two experiments: $\mathtt{exp-pr}$ and $\mathtt{exp-r}$.  
Let $T$ be some PPT test that outputs either $1$ or $0$.
\begin{center}
\begin{tabular}{c|c}
\begin{minipage}{3in}
\begin{tabbing}
123\=123\=123\=123\=123\=\kill
\textbf{Experiment} $\mathtt{exp-pr}^{G, T}$: \\
Select random $s$ of length $n$.\\
Compute $y = G(s)$\\
Run $T(y)$ and output whatever it does.
\end{tabbing} \end{minipage} &
\begin{minipage}{3in}
\begin{tabbing}
123\=123\=123\=123\=123\=\kill
\textbf{Experiment} $\mathtt{exp-r}^T$: \\
Select random $y$ of length $m$\\
Run $T(y)$ and output whatever it does.
\end{tabbing} 
\vspace{.05in}
\end{minipage} 
\end{tabular}
\end{center}

\begin{definition}
$G$ passes all statistical tests if for all PPT $T$, there exists negligible function $\epsilon(n)$ such that for all $n$, 
\[
\left| \Pr[\mathtt{exp-pr}^{G,T} =1] - \Pr[\mathtt{exp-r}^T =1] \right| \le \epsilon(n).
\]
\end{definition}


Let $G_1: \zo^n\rightarrow \zo^{2n}, G_2:\{0,1\}^{2n} \rightarrow \{0,1\}^{4n}$ be pseudorandom generators.  

Answer the following questions using a proof by reduction.  The following proofs require the use of a hybrid argument. 
\paragraph{Hybrid Argument} Introduce an intermediate experiment and show that if the two end experiments are distinguishable by an inverse polynomial then the distance between some end experiment and the intermediate experiment is distinguishable by an inverse polynomial.  (See Lecture 13 notes, page 3).  Then use show a distinguisher for some other problem based on each of these intermediate problems.

\begin{enumerate}[a)]
\item \textbf{35 pts} If $G_1, G_2$ are pseudorandom generators then the function $G_3:\zo^n\rightarrow \zo^{4n}$ defined as $G_3(s) = G_2(G_1(s))$ is a pseudorandom generator.

\textbf{Hint:} Your intermediate experiment should consider when the input to $G_2$ is replaced by a truly random string.
\begin{enumerate}
\item \textbf{5 pts} State, using mathematics, what it means for $G_3$ to not be a pseudorandom generator.
\item \textbf{5 pts} State in your own words the two parts of any hybrid argument.  Feel free to assign names to experiments.  What is the largest number of experiments that can be introduced safely?
\item \textbf{5 pts} Describe a hybrid experiment between  $\mathtt{exp-pr}$ and $\mathtt{exp-r}$.
\item \textbf{5 pts} Show what must be true about one of the hybrids if the distance between $\mathtt{exp-pr}$ and $\mathtt{exp-r}$ is an inverse polynomial.
\item \textbf{5 pts} Build a distinguisher for $G_1$ in one setting of the hybrid.
\item \textbf{5 pts} Build a distinguisher for $G_2$ in the other setting of the hybrid.
\item \textbf{5 pts} Describe how you have reached a contradiction overall.
\end{enumerate} 
\item \textbf{20 pts} If $G_1$ is a pseudorandom generator then the function $G_3:\zo^{2n}\rightarrow \zo^{4n}$ defined as $G_3(s_1 || s_2 ) = G_1(s_1) || G_1(s_2)$ is a pseudorandom generator.

\textbf{Hint:} Your intermediate experiment should consider when one of the outputs of $G_1$ is replaced by a truly random string.  
\begin{enumerate}
\item \textbf{5 pts} State, using mathematics, what it means for $G_3$ to not be a pseudorandom generator.
\item \textbf{5 pts} Describe a hybrid experiment between  $\mathtt{exp-pr}$ and $\mathtt{exp-r}$ and show what must be true about the distinguisher in one of the two settings.
\item \textbf{5 pts} Build a distinguisher for $G_1$ in either setting of the hybrid.
\item \textbf{5 pts} Describe how you have reached a contradiction overall.
\end{enumerate}
\end{enumerate}

\section{Pseudorandom Functions are good MACs}

In this question we will show that pseudorandom functions work as a good MAC function (under the appropriate definition).  \textbf{Read the entire question before beginning!}

\paragraph{Pseudorandom Functions}
First, the definition of a pseudorandom function considers two experiments: $\mathtt{exp-prf}^f$ and $\mathtt{exp-r}$.  
Let $\mathcal{A}$ be some PPT algorithm that outputs either $1$ or $0$.
\begin{center}
\begin{tabular}{c|c}
\begin{minipage}{3in}
\begin{tabbing}
123\=123\=123\=123\=123\=\kill
\textbf{Experiment} $\mathtt{exp-prf}^{f, \mathcal{A}}$: \\
Select random $s$ of length $\kappa$.\\
Repeat an arbitrary number of times:\\
\,\,Receive $x_i$ from $\mathcal{A}$.\\
\,\,Give $y_i = f_s(x_i) = f(s, x_i)$ to $\mathcal{A}$.\\
When $\mathcal{A}$ outputs ``finished'' and \\
a bit $b$, output $b$.
\vspace{1in}
\end{tabbing} \end{minipage} &
\begin{minipage}{3in}
\begin{tabbing}
123\=123\=123\=123\=123\=\kill
\textbf{Experiment} $\mathtt{exp-r}^{\mathcal{A}}$: \\
Initialize an empty table of values.\\
Repeat an arbitrary number of times:\\
\,\,Receive $x_i$ from $\mathcal{A}$.\\
\,\,Lookup $x_i$ in the table of values\\
\,\,\,\,if it exists return $y_i$ the stored value.\\
\,\,\,\,else randomly select $y_i$ and\\
\,\,\,\,store $(x_i, y_i)$ in the table.\\
When $\mathcal{A}$ outputs ``finished'' and \\
a bit $b$, output $b$.
\end{tabbing} 
\end{minipage} 
\end{tabular}
\end{center}

\begin{definition}
A family of functions $f:\zo^\kappa\times \zo^n\rightarrow \zo^n$ is called a pseudorandom function if for all PPT $\mathcal{A}$ there exists a negligible function $\epsilon(n)$ such that 
\[
|\Pr[\mathtt{exp-prf}^{f,\mathcal{A}} =1] - \Pr[\mathtt{exp-r}^{\mathcal{A}} =1 ]| <\epsilon(n).
\]
\end{definition}

\paragraph{Information-theoretic MAC} Furthermore, recall the definition of a good information-theoretic MAC function.  
Consider the following experiment:
$\mathtt{Mac-forge}^{\mathcal{A}, \mac}$:
\begin{enumerate}
\item Key $k\leftarrow \gen()$.
\item The adversary, $\mathcal{A}$ outputs $m$ and is given $t \leftarrow \mac(k, m)$.
\item The adversary outputs $(m', t')$.
\item The output of the experiment is $1$ if $m'=m$ and $\ver(k, m', t')=1$.  Otherwise the output is $0$.
\end{enumerate}
\noindent
We say a $\mac$ scheme is secure if no adversary can win this game:
\begin{definition}
A scheme $(\mac, \ver)$ is $\epsilon$-unforgeable under chosen message attack if
\[
\forall \mathcal{A}, \Pr_K[\mathtt{Mac-forge}^{\mathcal{A}, \mac}=1]<\epsilon.
\]
\end{definition}

\begin{enumerate}[a)]
\item \textbf{10 pts} Adapt the above definition of unforgeability to consider only computationally bounded adversaries.  If necessary, provide a new experiment and definition.
\item \textbf{10 pts} Adapt your definition from part a to additionally consider multiple messages.  If necessary, provide a new experiment and definition.   State what you are assuming about how the adversary receives messages in your definition.  That is, provide an informal definition of what you are protecting and a mathematical experiment.

\textbf{Hint:} You may want to refer to the solution to Problem Set 2.
\item \textbf{25 pts} Consider the following $(\gen, \mac, \ver)$ scheme for messages:
\begin{itemize}
\item $\gen:$ sample random $k$ of length $\kappa$.
\item $\mac(k, m) = f(k, m) = t$.
\item $\ver(k, m, t)$ if $f(k, m) \overset{?}= t$ output $1$, otherwise output $0$.
\end{itemize}

\emph{Show} if $f$ is a good PRF then $(\gen, \mac,\ver)$ is a good MAC scheme for multiple messages against computational adversaries as defined in part b).

\begin{enumerate}
\item \textbf{5 pts} State the contrapositive of the above statement.
\item \textbf{10 pts} Describe an algorithm $\mathcal{A}'$ that is able to distinguish the function $f$ from a truly random function (this algorithm may use an $\mathcal{A}$ breaks security as defined in part b)).  Be clear about what $\mathcal{A}'$ may receive as input and how it prepares inputs to $\mathcal{A}$.
\item \textbf{10 pts} Show that $\mathcal{A}'$ distinguishes $f$ from a truly random function.  
\end{enumerate}
\end{enumerate}

\end{document}