
\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}

\begin{document}
\handout{PS5/6}{DUE: October 31, 2002}{Instructor: Anna Lysyanskaya}
{\solution{*** Your name here *** }}{Problem Set 5-6}

\section*{Problem 1: Indistinguishability and the hybrid argument}

There are five parts to this problem.  There are also a few exercises in 
parentheses.  You do not have to turn in the answers to the exercises, but
it is a good idea to do them nevertheless.

Recall the notion of indistinguishability.  We say that two
polynomial-time samplable distributions, $\A$ and $\B$ are
indistinguishable if for all probabilistic polynomial-time
adversaries $\{A_k\}$ there exists a negligible function
$\nu(k)$ such that

$$\Pr[x_0 \leftarrow \A(1^k); x_1 \leftarrow \B(1^k); b \leftarrow \bit;
b' \leftarrow A_k(x_b) : b=b'] = 1/2 + \nu(k)$$

Similarly, we can define indistinguishability if $\A$ and
$\B$ are {\em families} of distributions indexed by some
public parameter generated by the key generation procedure $G$.  
In that case $(G,\A,\B)$ is a family of indistinguishable
distributions if for all probabilistic polynomial-time
adversaries $\{A_k\}$ there exists a negligible function
$\nu(k)$ such that

$$\Pr[\pk \leftarrow G(1^k); x_0 \leftarrow \A(\pk); x_1 \leftarrow \B(\pk); 
b \leftarrow \bit;
b' \leftarrow A_k(\pk,x_b) : b=b'] = 1/2 + \nu(k)$$

Notation: Let $\A \approx \B$ denote that
the distributions (or families of distributions) $\A$ and $\B$ are 
indistinguishable.  
(Exercise: why is it that $\A\approx\B \Leftrightarrow \B\approx\A$?)

\begin{description}
\item[(a)]  Let $(G,\A,\B)$ be families of distributions.
Prove that the following statements are equivalent:
\begin{enumerate}
\item $\A \approx \B$.
\item For all probabilistic poly-time algorithms 
$\{A_k\}$, there exists a negligible function $\nu(k)$ such that 
$|p^{\{A_k\}}_{\A}(k) - p^{\{A_k\}}_{\B}(k)| = \nu(k)$, where by $p_X(k)$, $X= \A,\B$, we mean:
$$p_X(k) = \Pr[\pk\leftarrow G(1^k); x\leftarrow X(\pk); 
b'\leftarrow A_k(\pk,x)~:~b'=0]$$
\end{enumerate}
In other words, two (families of) distributions are indistinguishable iff
no matter what algorithm $A_k$ 
you run on $x$ drawn from one of the distributions,
it will, with all but negligible probability,  
behave the same as if $x$ was drawn from the other distribution.
\end{description}

\medskip 
\solution{
{\bf Solution:} \newline \bigskip 


***************** INSERT SOLUTION HERE ***************


\bigskip
}

In lecture, we have seen the so-called {\em hybrid argument} for 
proving that two distributions $\A$ and $\B$ are computationally
indistinguishable.  The main tool that we used was the following lemma:

\medskip
\noindent {\bf Lemma 1}  For all polynomial-time samplable
(families of) distributions $\A$ and $\B$, if there exists a polynomial-time
samplable (family of) distribution(s) 
$\C$ such that $\A\approx \C$ and $\B \approx \C$,
then $\A \approx \B$.

\medskip 
\noindent {\bf Proof:}
Let $\{D_k\}$ be an adversary.  Using part (a), it is sufficient 
to show that there exists a 
negligible function $\nu(k)$ such that 
$|p^{\{D_k\}}_{\A}(k)-p^{\{D_k\}}_{\B}(k)|=\nu(k)$.
Since $\A \approx \C$, and $\C \approx \B$, 
we know that there exist negligible functions $\nu_1(k)$ and $\nu_2(k)$
such that 
$|p^{\{D_k\}}_{\A}-p^{\{D_k\}}_{\C}|=\nu_1(k)$ and
$|p^{\{D_k\}}_{\B}-p^{\{D_k\}}_{\C}|=\nu_2(k)$.
Then $$|p^{\{D_k\}}_{\A}-p^{\{D_k\}}_{\B}| = 
|p^{\{D_k\}}_{\A}-p^{\{D_k\}}_{\C} + p^{\{D_k\}}_{\C}-p^{\{D_k\}}_{\B}|
\leq |p^{\{D_k\}}_{\A}-p^{\{D_k\}}_{\C}| + |p^{\{D_k\}}_{\C}-p^{\{D_k\}}_{\B}|
= \nu_1(k)+\nu_2(k)$$
and we are done since the sum of two negligible functions is
negligible.

\begin{description}
\item[(b)] The claim proved below is false. (Exercise: why?)  However,
below is a proof of this claim.  Find the error in this proof.

\medskip 
\noindent {\bf Claim:}
Let $\A(1^k)$ be the uniform distribution on integers
in the interval $[1,2^k]$.
Let $\B(1^k)$ be the
uniform distribution
on integers in the interval $[2^k+1, 2^{k+1}]$.
Then $\A\approx\B$.

\medskip 
\noindent {\bf Proof:}
For $i \geq 0$, let $C_i(1^k)$ be the uniform distribution on the
integers in the interval $[i, 2^k+i]$.  It is clear that $C_0 = \A$,
and $C_{2^k}=\B$.  Also, note that for all $i$, $C_i \approx C_{i+1}$.
(Exercise: why?)  

Let us prove that for all $j$, $C_i \approx C_{i+j}$,
by induction on $j$.  The base case, $j=1$, is given.  The inductive step:
Suppose 
$C_i \approx C_{i+j-1}$.  We also know that
$C_{i+j-1}\approx C_{i+j}$.  Therefore, the conditions of 
Lemma~1 are satisfied, and $C_i \approx C_{i+j}$.

Therefore, in particular, $\A= C_{0} \approx C_{2^k}=\B$.
\end{description}

\medskip 
\solution{
{\bf Solution:} \newline \bigskip 


***************** INSERT SOLUTION HERE ***************


\bigskip
}

Part (b) shows that care must be taken when applying Lemma~1 to
proving indistinguishability of distributions.  Let us develop
some notation that will allow us to be more careful.
Instead of simply talking about two distributions as being 
indistinguishable, let us specify exactly what the maximum
advantage of a distinguisher would be in telling the two distributions
apart, as a function of the running time of this distinguisher.

\medskip \noindent {\bf Notation:}  
Let $\A$ and $\B$ be efficiently samplable families of distributions with
key generation algorithm $G$.
Let the notation ``$\A\approx \B$
with advantage at most 
$\epsilon(\cdot)$''  mean that for all probabilistic
polynomial-time adversaries $\{A_{k}\}$
$|p_{\A}^{\{A_{k}\}}(k) -p_{\B}^{\{A_{k}\}}(k)|\leq \epsilon(k)$.
\bigskip

The following lemma is a more precise version of Lemma 1:

\medskip
\noindent {\bf Lemma 2}  For all polynomial-time samplable
(families of) distributions $\A$ and $\B$, if there exists a polynomial-time
samplable (family of) distribution(s) 
$\C$ such that $\A\approx \C$ with advantage at most $\epsilon_1(k)$
and $\B \approx \C$ with advantage at most $\epsilon_2(k)$,
then $\A \approx \B$ with advantage at most $\epsilon_1(k) + \epsilon_2(k)$.

\medskip 
\noindent {\bf Proof idea:}  Same as the proof of Lemma~1.
\bigskip

Further, we can now consider the meat of the hybrid argument:

\medskip {\bf Lemma 3} 
For any integer $i \geq 0$, let 
$\A_i$ be a family of polynomial-time samplable
distributions.
Suppose that for all $1\leq i \leq n$, $\A_{i-1} \approx \A_{i}$
with advantage at most $\epsilon_i$.  Then $\A_0\approx \A_n$
with advantage at most $\sum_{i=1}^{n}\epsilon_i$.

\begin{description}
\item[(c)]  Prove Lemma~3.
\end{description}

\medskip 
\solution{
{\bf Solution:} \newline \bigskip 


***************** INSERT SOLUTION HERE ***************


\bigskip
}

Lemma~4 is the converse of Lemma~3.  Namely, it says that if we can
distinguish between $\A_0$ and $\A_n$, then we can distinguish between
$\A_{i-1}$ and $\A_i$ for some $i$.

\medskip {\bf Lemma 4} 
Let $\A$ and $\B$ be polynomial-time samplable families of distributions.
with setup algorithm $G$.
Let a distinguisher $\{D_k\}$ such that 
$p_{\A}^{\{D_k\}} - p_{\B}^{\{D_k\}} \geq \epsilon(k)$ be
given.  Let $n$ be any integer.
Let $\A_0=\A$, $\A_n=\B$, and $\A_i$, $1\leq i<n$, be any 
families of distributions with setup algorithm $G$.  Then
for some $1\leq i \leq n$, 
$p_{\A_{i-1}}^{\{D_k\}} - p_{\A_i}^{\{D_k\}} \geq \epsilon(k)/n$.

\medskip 
\noindent {\bf Proof:}
Simple averaging argument that we saw in class.

\bigskip
Finally, Lemma~5 states that if we can distinguish between
$\A$ and $\B$ using algorithm $\{D_k\}$ with advantage $\epsilon$,
then for a random $i$, $\{D_k\}$ is a good distinguisher 
with good probability.

\medskip {\bf Lemma 5} 
Let $\A_i$ be as in Lemma~4.
Let $P$ be a random variable, as follows:
$P = p_{\A_i}^{\{D_k\}} - p_{\A_{i-1}}^{\{D_k\}}$ 
for $1\leq i \leq n$ chosen uniformly at random.
Then $E[P] \geq \epsilon(k)/n$.

\begin{description}
\item[(d)] Prove Lemma~5.
\end{description}

\medskip 
\solution{
{\bf Solution:} \newline \bigskip 


***************** INSERT SOLUTION HERE ***************


\bigskip
}

\begin{description}
\item[(e)] Apply the Markov inequality to derive a lower bound on
the probability that,
for a randomly chosen $i$, the distinguisher will have advantage at least
$\epsilon/2n$.  Make your bound as tight as you can.
\end{description}

\medskip 
\solution{
{\bf Solution:} \newline \bigskip 


***************** INSERT SOLUTION HERE ***************


\bigskip
}


\section*{Problem 2: RM-security}
Let $\mathcal{M}$ be a set of messages.  This set may
consist of infinitely many messages, for example, of all
binary strings.  Let ${\mathcal{M}}_\ell$ denote the 
set of all 
$\ell$-bit strings in $\mathcal{M}$.  I.e., 
$${\mathcal{M}}_\ell = \{m~\mid~m\in \mathcal{M}, |m| = \ell\}$$

Recall GM security,
where the adversary chooses two messages of the same
length whose encryptions he intends to tell apart.   More precisely:

\medskip
\noindent
{\bf Definition (GM-Security)}
A
cryptosystem $(G, E, D)$ on a set of messages $\mathcal{M}$
is GM-secure if

\begin{eqnarray*}
\forall \{A_k\}~\exists \nu(k) \in \negl \mbox{ s.t. }&&\\
\Pr[&(\pk,\sk)\leftarrow G(1^k);(\alpha,m_0,m_1) \leftarrow A_k(\pk);& \\
&
c_0 \leftarrow E(\pk, m_0); c_1 \leftarrow E(\pk, m_1); &\\
&b \leftarrow \{0,1\}; b' \leftarrow A_k(\alpha, c_b):& b'=b] \leq 1/2 + \nu(k)
\end{eqnarray*}


Consider the following definition of security, which we
call random message security (RM security).  
Here, the
adversary chooses just one message.  The adversary's goal
is to tell an encryption of this message apart from an
encryption of a random message of the same length.  A cryptosystem
is RM-secure if any polynomial-time adversary fails.  More precisely:

\medskip
\noindent
{\bf Definition (RM-Security)}
A
cryptosystem $(G, E, D)$ on a set of messages $\mathcal{M}$
is random-message (RM) secure if

\begin{eqnarray*}
\forall \{A_k\}~\exists \nu(k) \in \negl \mbox{ s.t. }&&\\
\Pr[&(\pk,\sk)\leftarrow G(1^k);(\alpha,m) \leftarrow A_k(\pk);& \\
&r \leftarrow {\mathcal{M}}_{|m|}; 
c_0 \leftarrow E(\pk, m); c_1 \leftarrow E(\pk, r); &\\
&b \leftarrow \{0,1\}; b' \leftarrow A_k(\alpha, c_b):& b'=b] \leq 1/2 + \nu(k)
\end{eqnarray*}

Prove or disprove that for all sets of messages $\mathcal{M}$,
RM security is equivalent to GM security.  (The hybrid argument from
Problem~1 may be relevant.)

\medskip 
\solution{
{\bf Solution:} \newline \bigskip 


***************** INSERT SOLUTION HERE ***************


\bigskip
}

\section*{Problem 3:  Pseudorandomness vs. unpredictability}
In lecture, we assumed that if a bit is hardcore, i.e., hard to predict,
then it is pseudorandom, i.e., hard to distinguish from random.  Here, we
will prove it and further consider preudorandomness vs. unpredictability.

\begin{description}
\item[(a)]  Prove that a bit is hard to predict if and only if
it is pseudorandom.
More formally: Let $\{D_{\pk}\}$ be an efficiently samplable
family of distributions with setup procedure $G$.
Let $f(\pk,x)$ be any Boolean function.  
(For example, $\{D_{\pk}\}$ can be the distribution of GM ciphertexts for one 
bit, and $f(\pk,x)$ is the decryption of the ciphertext $x$ under public
key $\pk$.  Or, $\{D_{\pk}\}$ may be a family of one-way permutation, and 
$f(\pk,x)$ may be its hardcore bit.)  Prove that 
the 
following two conditions are equivalent:

Condition 1 (unpredictability): 
For all probabilistic polynomial-time adversaries $\{A_k\}$,
there exists a negligible function $\nu(k)$, such that
\begin{eqnarray*}
\Pr[\pk \leftarrow G(1^k); x \leftarrow D_{\pk}; &&\\
b'\leftarrow A_k(\pk,x) &:& f(\pk,x)=b'] \leq 1/2+\nu(k)
\end{eqnarray*}

More generally, for any (not necessarily boolean) function $f$,
let $p_{max}(D)$ be the probability of the most likely element
of $D_{\pk}$.  Then $f$ is unpredictable if 
for all probabilistic polynomial-time adversaries $\{A_k\}$,
there exists a negligible function $\nu(k)$, such that
\begin{eqnarray*}
\Pr[\pk \leftarrow G(1^k); x \leftarrow D_{\pk}; &&\\
y'\leftarrow A_k(\pk,x) &:& f(\pk,x)=y'] \leq p_{max}+\nu(k)
\end{eqnarray*}



Condition 2 (pseudorandomness):
For all probabilistic polynomial-time adversaries $\{A_k\}$,
there exists a negligible function $\nu(k)$, such that
\begin{eqnarray*}
\Pr[&a_0 \leftarrow \bit;&\\
&\pk \leftarrow G(1^k); x \leftarrow D_{\pk}; 
a_1 = f(\pk,x);&\\ 
&b\leftarrow \bit;
b' \leftarrow A_k(\pk,x,a_b)&~:~b=b'] \leq 1/2+\nu(k)
\end{eqnarray*}

For non-boolean $f$, the definition of pseudorandomness is essentially
the same.  Let $\{R_k\}$ denote some polynomial-time samplable 
family of distributions.
For example, $\{R_k\}$ can be the uniform distribution on $k$-bit
strings.  Function $f$ is pseudorandom if there exists a polynomial-time
samplable family of distributions $\{R_k\}$ such that
for all probabilistic polynomial-time adversaries $\{A_k\}$,
there exists a negligible function $\nu(k)$, such that
\begin{eqnarray*}
\Pr[&a_0 \leftarrow R_k;&\\
&\pk \leftarrow G(1^k); x \leftarrow D_{\pk}; 
a_1 = f(\pk,x);&\\ 
&b\leftarrow \bit;
b' \leftarrow A_k(\pk,x,a_b)&~:~b=b'] \leq 1/2+\nu(k)
\end{eqnarray*}
\end{description}


\medskip 
\solution{
{\bf Solution:} \newline \bigskip 


***************** INSERT SOLUTION HERE ***************


\bigskip
}

\begin{description}
\item[(b)]  Suppose that $f(\pk,x)$ is not a boolean function, but rather
a function with the range $\{0,1\}^k$.  Will $f(\pk, x)$ be unpredictable if it
is pseudorandom?  Will it be pseudorandom if it is unpredictable?
What if the range of the function is $\{0,1\}^{\log k}$?  
(You don't have to 
write the proofs in detail for this part of the problem,
it is sufficient to just sketch them.)
\end{description}

\medskip 
\solution{
{\bf Solution:} \newline \bigskip 


***************** INSERT SOLUTION HERE ***************


\bigskip
}
\end{document}
