\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 120 points. Due October 11th, 2007.}
\begin{document}
\maketitle
\setcounter{exercise}{-1}
\begin{exercise}[0 points]
\begin{enumerate}
\item Read the analysis of the construction of CPA-secure
encryption from PRFs in the Katz-Lindell book (proof of
Theorem 3.25, pages 90--93) and compare it to the proof
sketch given in class.
\item Read the analysis of the constructions of PRF's from
PRG's in Goldreich's book (see excerpt on the web page
under Lecture 5) and compare it to the proof given in
class.
\end{enumerate}
\end{exercise}
\ifpdf
\begin{figure}[t]
\begin{center}
\includegraphics*{secureid.jpg}
\end{center}
\caption{RSA SecurID Device.} \label{fig:secureid}
\end{figure}
\fi
\begin{exercise}[20 points] The RSA SecureID 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 Try to \emph{define} what it means that such a scheme
is \emph{secure} and sketch a proof that your
construction satisfies it (you don't have to formally
define and prove if you don't want to--- you can use
English but try to be precise). 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 \textbf{10 extra
points} for a fully rigorous definition and proof.
(Remember that rigorous does \emph{not} equal formal and
tedious--- it just means precise and without logical
gaps.)
\end{enumerate}
\end{exercise}
\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] 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}
%
%\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}
%
\vspace{2ex}
\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}[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}
\end{document}