\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsthm,url}
\usepackage{graphicx}
\newif\ifpdf
\ifx\pdfoutput\undefined \else
\ifx\pdfoutput\relax
\else
\ifcase\pdfoutput
\else
\pdftrue
\fi
\fi
\fi
%uncomment to get hyperlinks
%\usepackage{hyperref}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Some macros (you can ignore everything until "end of macros")
\def\class{0}
\topmargin 0pt \advance \topmargin by -\headheight \advance
\topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt \evensidemargin \oddsidemargin \marginparwidth
0.5in
\textwidth 6.5in
%%%%%%
\newcommand{\getsr}{\gets_{\mbox{\tiny R}}}
\newcommand{\bits}{\{0,1\}}
\newcommand{\Ex}{\mathbb{E}}
\newcommand{\To}{\rightarrow}
\newcommand{\e}{\epsilon}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\GF}{\mathsf{GF}}
\newcommand{\maxpr}{\text{\rm max-pr}}
\newcommand{\cclass}[1]{\mathbf{#1}}
\renewcommand{\P}{\cclass{P}}
\newcommand{\NP}{\cclass{NP}}
\newcommand{\PH}{\cclass{PH}}
\newcommand{\coNP}{\cclass{coNP}}
\newcommand{\AvgP}{\cclass{AvgP}}
\newcommand{\DTIME}{\cclass{DTIME}}
\newcommand{\BPP}{\cclass{BPP}}
\newcommand{\BQP}{\cclass{BQP}}
\newcommand{\NTIME}{\cclass{NTIME}}
\newcommand{\SIZE}{\cclass{SIZE}}
\newcommand{\Ppoly}{\cclass{P_{/poly}}}
\newcommand{\SPACE}{\cclass{SPACE}}
\newcommand{\PSPACE}{\cclass{PSPACE}}
\newcommand{\BPL}{\cclass{BPL}}
\newenvironment{summary}{\begin{quote}\textbf{Summary.}}{\end{quote}}
\newtheorem{theorem}{Theorem}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}{Claim}[theorem]
\theoremstyle{definition}
\newtheorem{exercise}{Exercise}
\newtheorem{definition}{Definition}
\newcommand{\sstart}{\triangleright}
\newcommand{\send}{\triangleleft}
\newcommand{\CSAT}{\ensuremath{\mathsf{CSAT}}}
\newcommand{\SAT}{\ensuremath{\mathsf{3SAT}}}
\newcommand{\IS}{\mathsf{INDSET}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\inp}{\mathsf{in}}
\newcommand{\outp}{\mathsf{out}}
\newcommand{\Adv}{\mathsf{Adv}}
\newcommand{\Supp}{\mathsf{Supp}}
\newcommand{\dist}{\Delta}
\newcommand{\indist}{\approx}
\newcommand{\PRG}{\mathsf{G}}
\newcommand{\Enc}{\mathsf{E}}
\newcommand{\Dec}{\mathsf{D}}
\newcommand{\Fcal}{\mathcal{F}}
\newcommand{\Gen}{\mathsf{Gen}}
\newcommand{\Sign}{\mathsf{Sign}}
\newcommand{\Ver}{\mathsf{Ver}}
\newcommand{\Com}{\mathsf{Com}}
\newcommand{\angles}[1]{\langle #1 \rangle}
\newcommand{\eqdef}{\stackrel{\vartriangle}{=}}
\newcommand{\view}{\mathsf{view}}
\newcommand{\trans}{\mathsf{trans}}
\newcommand{\qstart}{q_{\text{\tiny start}}}
\newcommand{\qacc}{q_{\text{\tiny acc}}}
\newcommand{\qrej}{q_{\text{\tiny rej}}}
\newcommand{\csp}{\mathsf{CSP}}
\newcommand{\ared}{\text{\tt alph-red}}
\newcommand{\qred}{\text{\tt q-red}}
\newcommand{\dred}{\text{\tt deg-red}}
\newcommand{\amp}{\text{\tt gap-amp}}
\newcommand{\LC}{\mathcal{LC}}
\renewcommand{\H}{\mathcal{H}}
\newcommand{\iprod}[1]{\langle #1 \rangle}
\newcommand{\pmo}{\{\pm 1\}}
\newcommand{\set}[1]{\{ #1 \}}
% end of macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{COS 433 --- Cryptography --- Homework 3.}
\author{Boaz Barak}
\date{Total of 130 points. Due February 24, 2010.}
\begin{document}
\maketitle
\setcounter{exercise}{-1}
\begin{exercise}[0 points]
\begin{enumerate}
\item Read the analysis of the length extension theorem for PRG's in Katz-Lindell (pages
215--220 excerpt on web and handed out in class) and compare it to the proof given in
class, you can also compare it to the proof in the Boneh-Shoup book in Section 3.4.2
\item Read the analysis of the constructions of PRF's from PRG's in Boneh-Shoup book (Section
4.6, pages 113--117) and compare it to the proof given in class.
\end{enumerate}
\end{exercise}
\begin{exercise}[25 points, impossibility of statistically testing randomness]
Let $T_1,\ldots,T_M:\bits^n\To\bits$ be a collection of function that are supposed to be
statistical tests for randomness. Prove that if $M<2^{2^{n/30}}$ there exists a distribution $X$
that passes all these tests but is very far from the uniform distribution. Concretely, show that
there exists a random variable $X$ over $\bits^n$ such that:
\begin{itemize}
\item For every $i \in [M]$, $\bigl| \Pr[ T_i(U_n)=1] - \Pr[ T_i(X)=1] \bigr| < 2^{-n/50}$
\item $\Delta(X,U_n) \geq 1-2^{-n/50}$ (where $\Delta$ denotes the statistical distance).
\end{itemize}
(The constants above are fairly arbitrary and are set to allow a lot of slackness.) See footnote
for hint.\footnote{{\bf Hint:} \tiny Define $X$ as the uniform distribution over some set $S = \{
s_1,\ldots,s_m \}$ where $m=2^{n/15}$. Show that for every such set $S$, just because of $S$'s
small size it will have very large statistical distance from the uniform distribution. Now, $\Pr[
T_i(X)=1] = \tfrac{1}{m}\sum_{j=1}^m T_i(s_j)$ (*). Now use the Chernoff bound from probability to
argue that if you chose the elements $s_1,\ldots,s_m$ at random, then for every $i$, the
probability that the RHS deviates from $\Ex[T_i(U_n)]$ is very small, and in fact small enough that
you can do a union bound over all $i\in \{1..M\}$.}
Based on this exercise, what do you believe can we say about a distribution $X$ if it passes the
FIPS 140-2 testing suite for randomness?
\end{exercise}
\begin{exercise}[25 points] \begin{enumerate}
\item Prove the \emph{polynomial hybrid principle}. That is prove that for every
$m$ distributions $X_1,\ldots,X_m$ over $\bits^n$ such that $\Delta_T(X_i,X_{i+1}) \leq \e$ for every $i \in \{1..m-1\}$,
$\Delta_T(X_1,X_m) \leq m\e$.
The above claim is used to show that if $X_i \indist X_{i+1}$ for all $i$, then $X_1
\indist X_m$.
\item Show that there is no \emph{exponential} hybrid principle in the following sense: show that
there exist $2^n$ distributions $X_1,\ldots,X_{2^n}$ over $\bits^n$ such that (a) for every $i$, $X_i$ and $X_{i+1}$
are computationally (or even statistically!) indistinguishable, i.e. $\Delta(X_i,X_{i+1}) <
2^{-n/10}$ but (b) $X_1$ and $X_{2^n}$ are easy to distinguish - there is a linear time algorithm
$T$ such that $\Ex[T(X_1)] > 0.9$ but $\Ex[T(X_{2^n})] < 0.6$.
\end{enumerate}
\end{exercise}
\begin{exercise}[25 points] In these two questions you'll show that if we have
a pseudorandom function family with particular input and output sizes, we can easily obtain a
family that handles larger inputs and outputs. (It's easy to handle smaller outputs and inputs by
truncation and padding.)
\begin{enumerate}
\item \emph{(Changing PRFs output size)} Prove that if there exists a collection $\{ f_s \}$ of
pseudorandom functions with $f_s:\bits^{|s|} \To \bits$ (i.e., one-bit output) then there
exists a collection $\{ f'_s \}$ with $f'_s:\bits^{|s|}\To\bits^{|s|}$. See footnote for
hint.\footnote{\textbf{Hint:} \tiny First come up with a pseudorandom family with output
longer than $1$ but shorter than $|s|$. For example, if $s \in \bits^{n^2}$ then the output
can be $n$. Then show that existence of PRF implies existence of pseudorandom generators
and use that to expand your output.}
\item \emph{(Changing PRFs input size)} Prove that if there exists a collection $\{ f_s \}$ of
pseudorandom functions with $f_s:\bits^{|s|}\To\bits^{|s|}$ then there exists a collection
$\{ f'_s \}$ with $f'_s:\bits^{*}\To\bits^{|s|}$ (i.e., $f'_s$ for a random $s\in\bits^n$
is indistinguishable from a random function from $\bits^*$ to $\bits^n$. See footnote for
hint\footnote{\textbf{Hint:} \tiny (This is definitely not the only approach to do this.)
First note that such a PRF family implies immediately a family where $f_s:\bits^{|s|} \To
\bits^{|s|/2}$. Then try to use this to get a function $f'_s$ that works only for inputs
whose size is a multiple of $|s|/2$. Then try to get a function that works for every finite
length string.}
\end{enumerate}
\end{exercise}
\ifpdf
\begin{figure}[t]
\begin{center}
\includegraphics*[scale=0.8]{secureid.jpg}
\end{center}
\vspace{-10ex}\caption{RSA SecurID Device.} \label{fig:secureid}
\end{figure}
\fi
\begin{exercise}[25+30 points] The RSA SecurID card \ifpdf (see Figure~\ref{fig:secureid}) \fi
is a credit-card sized device that displays $6$ digits that
change every minute. The idea is that when you log into your
account remotely (say when you want to log into your UNIX
account in Princeton from an Internet Cafe) then you have to
type the numbers that appear in the card in addition to your PIN
or password.
\begin{enumerate}
\item What is the security advantage of such a card over
traditional password? That is, what sort of attack can
this card resist which cannot be resisted using a
standard password mechanism? (When making this
comparison, assume that it's possible for users to
remember a $6$-digits PIN or a password with similar
security.)
\item Describe how you would implement such a scheme using
pseudorandom functions.
Assume that the PRF family takes a seed of size $n$ to map
$n$ bits to $n$ bits, and that the number of possible
devices is $M$ (for $M<2^n$). How many bits of storage does
your implementation use at the server and each of the
devices? (there is an implementation that uses at most
$O(n)$ bits in each place).
\item (15 extra points) \emph{Define} what it means that such a scheme is \emph{secure}. That
is, write down a list of desired security properties that any such identification scheme
should satisfy. Then, make a formal definition of security based on a game in which the
scheme is secure if the probability that the adversary ``wins'' is small. Any scheme that
satisfies the formal definition should have the desired security properties.
\item (15 extra points) \emph{Prove} that your construction above satisfies the definition
you made. Say how the security depends on $n$ - the number of bits that the device stores
in memory (where its running time is polynomial in $n$) and on $k$ - the number of digits
that it displays to the user. You'll get partial credit for a proof sketch or proof idea,
as long as it's clearly written, even if you don't have a full formal proof.
\end{enumerate}
\end{exercise}
%
%\paragraph{Pseudorandom permutations.} Recall that we define a
%collection of permutations $\{ p_k \}_{k \in \bits^*}$ where for
%$k\in\bits^n$, $p_k$ is a permutation over $\bits^{m(n)}$ to be
%a \emph{pseudorandom-permutation collection} if it
%satisfies:\footnote{We assume that $m$ and $n$ are polynomially
%related. That is, $n^{1/c} < m(n) < n^c$ for some constant $c$.}
%%for some polynomially bounded $m(\cdot)$ (i.e.,
%%$n^{1/c} < m(n) < m^c$ for some constant $c$ and large enough $n$)
%\vspace{-2ex}
%\begin{itemize}
%
%\item \emph{(Efficient computation)} The functions $(k,x)
% \mapsto p_k(x)$ and $(k,y) \mapsto p_k^{-1}(y)$ are
% efficiently computable (i.e., in polynomial time).
%
%\vspace{-1ex}
%\item \emph{(Pseudorandomness)} There are super polynomial
% functions $T,\e$ such that for every $T(n)$ time
% adversary $\Adv$,
%\[
%\left| \Pr_{k \getsr \bits^n}\left[
%\Adv^{p_k(\cdot),p_k^{-1}(\cdot)}(1^m)=1 \right] - \Pr_{P \getsr
%\bits^m \stackrel{\text{\tiny 1-1}}{\To} \bits^m}\left[
%\Adv^{P(\cdot),P^{-1}(\cdot)}(1^m)=1 \right] \right| < \e(n)
%\]
%(The notation $\Adv^{f,g}$ means that the adversary is given
%oracle access to the functions $f(\cdot)$ , $g(\cdot)$ which
%naturally it can query for at most $T$ times. If an event
%happens with probability at most $1/n^{\omega(1)}$ then we
%say it happens with \emph{negligible} probability.)
%\end{itemize}
%
\iffalse
\noindent The following exercises use the definition of \emph{pseudorandom permutations} as in
given in class; see also Section 3.6.3 (page 94) of Katz-Lindell.
\begin{exercise}[20 points] Recall that in class we gave a construction of a \emph{probabilistic}
CPA-secure encryption scheme (i.e., the function $\Enc$ used extra randomness in computing the
encryption).
\begin{enumerate}
\item Show that there is no \emph{deterministic} encryption scheme satisfying the CPA security
definition we gave in class.
\item Give a variant of the CPA security definition for \emph{stateful} encryption schemes,
where $\Enc$ and $\Dec$ can keep state between each encryption and decryption they perform.
Prove that there exists a deterministic stateful encryption scheme that is CPA secure under
your definition.
\end{enumerate}
\end{exercise}
\begin{exercise}[25 points] Let $\{ p_k \}_{k\in\bits^*}$ be a pseudorandom permutation
collection, where for $k \in \bits^n$, $p_k$ is a permutation over $\bits^m$.
\begin{enumerate}
\item Consider the following encryption scheme $(\Enc,\Dec)$: $\Enc_k(x) = p_k(x)$ ,
$\Dec_k(y)=p_k^{-1}(y)$. Prove that this scheme is \emph{not} a CPA-secure encryption.
\item Consider the following scheme $(\Enc,\Dec)$ that encrypts $m/2$-bit messages in the
following way: on input $x\in\bits^{m/2}$, $\Enc_k$ chooses $r \getsr\bits^{m/2}$ and
outputs $p_k(x,r)$ (where comma denotes concatenation), on input $y\in\bits^{m/2}$,
$\Dec_k$ computes $(x,r) = p^{-1}_k(y)$ and outputs $x$. Prove that $(\Enc,\Dec)$ \emph{is}
a CPA-secure encryption scheme. See footnote for hint\footnote{\textbf{Hint:} \tiny Try
proving first for partial credit that this scheme satisfies the weaker notion of
\emph{multiple message security}. That is, for every polynomial $p=p(n)$ and
$x_1,\ldots,x_p,x'_1,\ldots,x'_p \in \bits^{m/2}$ the two sequences of random variables
$\angles{ Enc_K(x_1) ,\ldots, \Enc_K(x_p) }$ and $\angles{ \Enc_K'(x'_1) , \ldots,
\Enc_K'(x'_p)}$ are computationally indistinguishable (where $K$ and $K'$ are two
independent random variables distributed uniformly over $\bits^n$).}
\end{enumerate}
\end{exercise}
\newcommand{\CBC}[2]{\mathsf{CBC}_{#1}\angles{#2}}
\begin{exercise}[20 points] The CBC construction is often used to get
an encryption for larger message size. If $p:\bits^m\To\bits^m$ is a permutation, then
$\CBC{\ell}{p}$ is a permutation from $\bits^{\ell\cdot m}$ to $\bits^{\ell\cdot m}$ defined in the
following way: for $x_1,\ldots,x_{\ell} \in \bits^m$, let $y_0 = 0^n$ and define $y_i = p(y_{i-1}
\oplus x_i)$. Then, $\CBC{\ell}{p}(x_1,\ldots,x_{\ell}) = (y_1,\ldots,y_{\ell})$.\footnote{The
string $y_0$ is called the initialization vector or IV, and in practice is often chosen to be
different than $0^m$. However, as long as it's a fixed public value this doesn't make any security
difference. Note that the KL book considers a different variant of CBC where the IV is chosen
independently at random for each encryption.} Note that the inverse of $\CBC{\ell}{p}$ can be
computed in a similar way using the inverse of $p(\cdot)$.
Let $\{ p_k \}$ be a pseudorandom permutation collection. Determine the CPA-security of the
following two encryption schemes which are based on the CBC construction. That is, for each scheme
either prove that it is CPA-secure or give an attack showing that it is not. For simplicity, we
consider only the 3-block variant of the scheme (i.e. $\ell=3$).
\begin{enumerate}
\item\emph{(Padding in the end)} Given $p_k:\bits^m \To \bits^m$ and a message $x=x_1,x_2
\in\bits^{2m}$, $\Enc_k$ chooses $r \getsr \bits^m$ and outputs $\CBC{3}{p_k}(x_1,x_2,r)$.
Decrypting done in the obvious way.
\item\emph{(Padding in the start)} Given $p_k:\bits^m \To \bits^m$ and a message $x=x_1,x_2
\in\bits^{2m}$, $\Enc_k$ chooses $r \getsr \bits^m$ and outputs $\CBC{3}{p_k}(r,x_1,x_2)$.
Decrypting done in the obvious way.
\end{enumerate}
\end{exercise}
\begin{exercise}[0 points] Consider the following scenario:
Alice is a customer and Bob is an online merchant, and Alice wants to send her credit card number
to Bob over the web, at which point Bob will verify the number against some database and decide
whether to continue with the transaction. Assume that they are able to share a random secret key.
Think whether you can implement a way to do this using a CPA secure encryption scheme.
Think whether your protocol is secure against an eavesdropper Eve that listens on the line of
communication. Then, think whether it's secure even if Eve can be \emph{active}--- modify the
messages sent between Alice and Bob.
\end{exercise}
\fi
\end{document}