%N999424
\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsthm,url}
\usepackage{graphicx}
%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 2.}
\author{Boaz Barak}
\date{Total of 120 points. Due February 17th, 2010.}
\begin{document}
\maketitle
\begin{exercise}[20 points] Prove that if $(\Enc,\Dec)$ is a computationally
secure encryption with $\ell(n)$-long messages then for every
polynomial-time algorithm Eve and large enough $n$, the
probability that Eve wins in the following game is smaller than
$0.34$:
\begin{enumerate}
\item Eve gets as input $1^n$, and gives Alice three strings
$x_0,x_1,x_2 \in \bits^{\ell(n)}$.
\item Alice chooses a random key $k \getsr \bits^n$ and $i
\getsr \set{0,1,2}$ and computes $y = \Enc_k(x_i)$.
\item Eve gets $y$ as input, and outputs an index
$j\in\set{0,1,2}$.
\item Eve \emph{wins} if $j=i$.
\end{enumerate}
\noindent \emph{Note:} This proof can be generalized to show
that the probability Eve guesses which one of $c$ messages was
encrypted is at most $1/c + \mu(n)$ where $\mu$ is a negligible
function (see also Exercise~6). It can also be shown that
computational security implies many other reasonable conditions
of security. For example, the KL book shows that if a message
$x$ is chosen at random, then the probability that a
polynomial-time adversary can compute the $i^{th}$ bit of $x$
from an encryption of $x$ is at most $1/2+\mu(n)$ for a
negligible $\mu$ (of course, she can always compute that bit
with probability half by randomly guessing). This can also be
generalized to show that for example that the probability that
an adversary guesses the first $c$ bits of $x$ from an
encryption of $x$ is at most $2^{-c}+\mu(n)$ for a negligible
$\mu$.
\end{exercise}
% decided to drop this question - hope you guys appreciate it :)
\iffalse
\begin{exercise}[20 points] Prove the equivalence of the two definition of
computational security we gave in class. That is, prove that an
encryption scheme $(\Enc,\Dec)$ with $\ell(n)$-long messages is
C/S1 iff it is C/S2, where these two notions are defined as
follows:
\begin{description}
\item[C/S1] $(\Enc,\Dec)$ is C/S1 if for every
polynomial-time $\Adv$ and polynomially bounded
$\e:\N\To [0,1]$, large enough $n$, and $x_0,x_1 \in
\bits^{\ell(n)}$,
\[
\bigl| \Pr[ \Adv(\Enc_{U_n}(x_0))=1 ] - \Pr[ \Adv(\Enc_{U_n}(x_1))=1 ] \bigr|
\]
\item[C/S2] $(\Enc,\Dec)$ is C/S1 if for every
polynomial-time Eve and polynomially bounded $\e:\N\To
[0,1]$, large enough $n$, the probability that Eve wins
the following game is at most $1/2+\e(n)$: \textbf{1.}
Eve gets as input $1^n$, and gives Alice two strings
$x_0,x_1 \in \bits^{\ell(n)}$ \textbf{2.} Alice chooses
a random key $k \getsr \bits^n$ and $i \getsr
\set{0,1,2}$ and computes $y = \Enc_k(x_i)$, \textbf{3.}
Eve gets $y$ as input, and outputs an index
$j\in\set{0,1}$, \textbf{4.} Eve \emph{wins} if $j=i$.
\end{description}
\end{exercise}
\fi
\begin{exercise}[20 points] For each of the following
statements decide whether it's true or false, and prove it or give a counterexample: (you can use
the conjecture made in class as an ``axiom'' for your proofs or counterexamples)
\begin{enumerate}
\item If $(\Enc,\Dec)$ is a perfectly secure encryption then
it is also computationally secure.
\item If $(\Enc,\Dec)$ is a computationally secure
encryption then it is also perfectly secure.
\item If $(\Enc,\Dec)$ is a computationally secure encryption with $n$-sized key and
$\ell(n)$-sized messages then the following encryption scheme $(\Enc',\Dec')$ with
$n$-sized key and $2\ell(n)$-sized messages is also computationally secure: To encrypt the
string $x=x_1\ldots x_{2\ell(n)}$ with key $k\in\bits^n$, $\Enc'_k(x) = \Enc_k(x_1\ldots
x_{\ell(n)}) \circ \Enc_k(x_{\ell(n)+1}\ldots x_{2\ell(n)})$, where $\circ$ denotes string
concatenation. (Decryption is done in the obvious way.)
\item If $(\Enc,\Dec)$ is a computationally secure
encryption with $n$-sized key and $\ell(n)$-sized
messages then the following encryption scheme
$(\Enc',\Dec')$ with $2n$-sized key and $2\ell(n)$-sized
messages is also computationally secure: To encrypt the
string $x=x_1\ldots x_{2\ell(n)}$ with key
$k\in\bits^{2n}$, $\Enc'_k(x) = \Enc_{k_1\ldots
k_{\ell(n)}}(x_1\ldots x_{\ell(n)}) \circ
\Enc_{k_{\ell(n)+1}\ldots
k_{\ell(n)}}(x_{\ell(n)+1}\ldots x_{2\ell(n)}$, where
$\circ$ denotes string concatenation. (Decryption is
done in the obvious way.)
\end{enumerate}
\end{exercise}
Recall that we defined the \emph{statistical distance} between two distributions $X$ and $Y$ over
say $\bits^n$ to be
\[
\Delta(X,Y) = \max_{f:\bits^n\To\bits} \left| \Pr[ f(X)=1] - \Pr[ f(Y)=1 ] \right|
\]
and the $T$-computational distance to be
\[
\Delta_T(X,Y) = \max_{\substack{f:\bits^n\To\bits \\ f \text{ computable by circuit of size $\leq T$}}} \left| \Pr[ f(X)=1] - \Pr[ f(Y)=1 ] \right|
\]
We'll say that two sequences $\{ X_n \}_{n\in\N}$ and $\{ Y_n \}_{n\in\N}$ of distributions are
\emph{computationally indistinguishable}, denoted by $\{ X_n \} \indist \{
Y_n\}$, if there is some super-polynomial function $T:\N\To\N$ and negligible function
$\e:\N\To [0,1]$ such that $\Delta_{T(n)}(X_n,Y_n) \leq \e(n)$ for every $n$.
\begin{exercise}[20 points] We call a sequence $\{ X_n \}_{n\in\N}$
of distributions \emph{pseudorandom} if it's computationally indistinguishable from the sequence
$\{ U_n \}$ where $U_n$ is the uniform distribution over $\bits^n$. Are the following sequences
pseudorandom? prove or refute.
\begin{enumerate}
\item $\{ X_n \}$ where $X_n$ be the following distribution: we pick $x_1,\ldots,x_{n-1}$
uniformly at random in $\bits^{n-1}$, and let $x_n$ be the parity (i.e. XOR) of
$x_1,\ldots,x_{n-1}$, we output $x_1,\ldots, x_n$.
\item $\{Z_n \}$ where for $n$ large enough, with probability $2^{-n/10}$ we output an $n$ bit
string encoding the text \texttt{''This is not a pseudorandom distribution''} (say encode
in ASCII and pad with zeros), and with probability $1-2^{-n/10}$ pick a random string. For
$n$ that is not large enough to encode the text, $Z_n$ always outputs the all zeroes
string.
\end{enumerate}
\end{exercise}
\begin{exercise}[20 points] Prove the following properties of
computational indistinguishability:
\begin{enumerate}
\item It's weaker than statistical indistinguishability:
if for every $n$, $\dist(X_n,Y_n) \leq \e(n)$ for
some negligible function $\e:\N\To\N$ (i.e., $\e(n)
= n^{-\omega(1)}$) then $\{ X_n \} \indist \{
Y_n\}$. (Recall that $\dist$ denotes statistical
distance.)
\item If $\set{ X_n } \indist \set{ Y_n}$ and
$f:\bits^*\To\bits^*$ is a function computable in
polynomial time, then $\set{ f(X_n) } \indist \set{
f(Y_n) }$.
\end{enumerate}
\end{exercise}
\begin{exercise}[20 points]
\begin{enumerate}
\item Let $X,Y,X',Y'$ be four distributions over $\bits^n$
such that $\dist(X,Y) \leq \e$ and $\dist(X',Y') \leq
\e$. Prove that $\dist(X \circ X',Y \circ Y') \leq
10\e$, $X \circ X'$ denotes the distribution obtained by
concatenating two independent samples from $X$ and $X'$,
and $Y \circ Y'$ is defined analogously. See footnote
for hint\footnote{\textbf{Hint:} \tiny Use the
definition of statistical distance based on functions,
and the following simple fact: if $f$ is a function
mapping $\bits^{2n}$ to $\bits$ and $Z$ and $W$ are two
independent distributions over $\bits^n$ such that $\Pr[
f(Z,W) =1 ] \geq p$, then there exists a fixed string
$z$ in the support of $Z$ such that $\Pr[ f(z,W) = 1]
\geq p$.}
\item Let $\set {X_n},\set{X'_n} , \set{Y_n},\set{Y'_n}$ be
four sequences of distributions such that $\set{X_n}
\indist \set{Y_n}$ and $\set{X'_n} \indist \set{Y'_n}$,
prove that $\set{ X_n \circ X'_n } \indist \set{ Y_n
\circ Y'_n}$. See footnote for
hint\footnote{\textbf{Hint:} \tiny use the fact that
``hardwiring'' of advice to the adversary/distinguisher
is allowed.}
\end{enumerate}
\end{exercise}
\begin{exercise}[20 points] Recall that we defined a function $\e:\N\To
[0,1]$ to be \emph{polynomially bounded} if $\e(n) = n^{-O(1)}$
(equivalently, $\log (1/e(n)) = O(\log n)$) and
\emph{negligible} if $\e(n) = n^{-\omega(1)}$ (equivalently,
$\log(1/\e(n)) = \omega(\log n)$). Let $\set{ A_n }$ be a
sequence of probabilistic events. Prove that the following two
conditions are equivalent:
\begin{itemize}
\item For every polynomially bounded $\e:\N\To[0,1]$ and
large enough $n$, $\Pr[A_n] \leq \e(n)$.
\item There exists a negligible function $\mu:\N\To[0,1]$
such that $\Pr[ A_n ] \leq \mu(n)$ for every $n$.
\end{itemize}
\noindent \emph{Note:} This exercise may not be the most exciting, but it gives a useful result,
since it means that in making various game-type definitions, instead of saying ``for every constant
$c$ and large enough $n$, the probability that Eve wins is at most $1/2+1/n^c$'', we can
equivalently say ``for every $n$, the probability that Eve wins is at most $1/2+\e(n)$ where $\e$
is some negligible function''
\end{exercise}
\end{document}