\documentclass[10pt]{article}
\newtheorem{define}{Definition}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\usepackage{enumerate}
\usepackage{mathrsfs}
\newcommand{\scr}{\mathscr}
\newcommand{\cequiv}{\stackrel{\mathrm{c}}{\equiv}}
\newcommand{\mr}{\mathrm}
\newcommand{\tu}{\textup}
\newcommand{\ds}{\displaystyle}

\usepackage{amsmath}
\usepackage{amssymb}
\begin{document}
\input{preamble.tex}

\lecture{21}{May 3, 2006}{Ronitt Rubinfeld}{Benjamin Rossman}

\begin{definition}[Computational indistinguishability]
Let $X = (X_n)$ and $Y = (Y_n)$ be sequences of random variables on
$\{0,1\}^n$. We say $X$ and $Y$ are {\em
$\epsilon(n)$-indistinguishable for time $t(n)$} if for every
probabilistic algorithm $T$ running in time $t(n)$,
\[
    \left|\Pr[T(X_n) = 1] - \Pr[T(Y_n) = 1]\right|
    \le \epsilon(n)
\]
for all large enough $n$. The quantity $\left|\Pr[T(X_n) = 1] -
\Pr[T(Y_n) = 1]\right|$ is called the {\em advantage of $T$}; it is
a measure of how much better $T$ is than random guessing at
distinguishing $X_n$ from $Y_n$. We write $X \cequiv Y$ if $X$ and
$Y$ are $\frac{1}{n^c}$-indistinguishable for time $n^c$, for all $c
> 0$. $T$'s advantage is said to be {\em negligible} if it is $<
\frac{1}{n^c}$ for all $c$.
\end{definition}

The following definition is due to Blum, Micali and Yao.

\begin{definition}[Pseudorandom generator, or PRG]
A function $G : \{0,1\}^{\ell(n)} \longrightarrow \{0,1\}^n$ is a
{\em PRG} if
\begin{enumerate}[\normalfont\qquad(1)\ ]
  \item
    $\ell(n) < n$
  \item
    $G(\scr U_{\ell(n)}) \cequiv \scr U_n$
\end{enumerate}
where $\scr U_n$ is the uniform distribution on $\{0,1\}^n$ and
$G(\scr U_{\ell(n)})$ is the distribution on $\{0,1\}^n$ induced as
the image under $G$ of the uniform distribution $\scr U_{\ell(n)}$
on $\{0,1\}^{\ell(n)}$.

    The function $\ell(n)$ is called the {\em seed length} of $G$.

    $G$ is {\em efficient} if it is computable in time $\mr{poly}(n)$ (not
    $\mr{poly}(\ell(n))$).

    It is {\em pseudorandom against nonuniform time $t(n)$} if
    $G(\scr U_{\ell(n)})$ and $\scr U_n$ are computationally
    indistinguishable with respect to probabilistic algorithms $T$
    that run in nonuniform polynomial time (i.e., $T$ is computable
    by a non-uniform family of polynomial-size circuits).
\end{definition}

\begin{definition}[$\mr{BPP}$ complexity class]
$L \in \mr{BPP}$ if there is a p.p.t.\ (probabilistic polynomial
time) algorithm $A$ such that for all inputs $x$,
\begin{itemize}
  \item
    if $x \in L$ then $\Pr[A$ accepts $x] \ge \frac 2 3$;
  \item
    if $x \notin L$ then $\Pr[A$ accepts $x] \le \frac 1 3$.
\end{itemize}
That is, $A$ outputs the correct answer with probability $\ge \frac
2 3$. ($A$ tolerates two-sided errors.)
\end{definition}

\begin{theorem}\label{thm1}
If there exists an efficient PRG against nonuniform time $n$ with
seed length $\ell(n)$, then $\mr{BPP} \subseteq \ds\bigcup_{c > 0}
\mr{DTIME}(2^{\ell(n^c)}n^c)$ and in particular
\[\begin{aligned}
  \ell(n) = O(\log n) &\Longrightarrow \mr{BPP} \subseteq \mr{P}\\
  \ell(n) = O(\log^c n) &\Longrightarrow \mr{BPP} \subseteq
  \mr{DTIME}(n^{\mr{polylog}(n)})\\
  \ell(n) = O(n^\epsilon) &\Longrightarrow \mr{BPP} \subseteq
  \mr{Subexponential\ Time}.
\end{aligned}\]
\end{theorem}

Note that $\mr{BPP} \subseteq \mr{ExpTime}$ since an exponential
time algorithm can enumerate all seeds to a PRG and output the
majority answer.\bigskip

\begin{proof}
Suppose $G : \{0,1\}^{\ell(n)} \longrightarrow \{0,1\}^n$ is a PRG
against nonuniform time $n$ whose runtime is $O(n^{c_1})$. Let $A$
be a p.p.t.\ algorithm in $\mr{BPP}$ whose runtime is $O(n^{c_2})$.
We define a deterministic algorithm $A' \in
\mr{DTIME}(2^{\ell(n^{c_2})}(n^{c_1}+n^{c_2}))$ equivalent to $A$ as
follows: run $A$ on input $x$ with random bits $G(s)$ for all seeds
$s \in \{0,1\}^{\ell(n)}$, and output the majority answer.

Toward a contradiction, assume $A'$ gives the wrong answer on input
$x$. That is, $\ds\Pr_{s \in \scr U_{\ell(n^{c_2})}}[A(x,G(s))$ is
correct$] \le \frac 1 2$. Since $A \in \mr{BPP}$, we know $\ds\Pr_{y
\in \scr U_{n^{c_2}}}[A(x,y)$ is correct$] \ge \frac 2 3$. But now
we have an efficiently computable test $T_{A,x}(\ast) := A(x,\ast)$
with advantage $\frac 1 6$. This contradicts the fact that $G$ is a
PRG. Therefore, $A'$ is equivalent to $A$. We conclude that
$\ds\mr{BPP} = \bigcup_{c > 0}
\mr{DTIME}(2^{\ell(n^{c_2})}(n^{c_1}+n^{c_2}))$.
\end{proof}

\begin{remark}
In the proof of Theorem~\ref{thm1}, it is enough to assume we have a
PRG $G$ such that $G(U_{\ell(n)})$ is computationally
indistinguishable from $\scr U_n$ for {\em linear time algorithms}
$T$. Note that the runtime of $G$ has to be $\mr{poly}(n^c)$, but
isn't required to match the runtime of $A$.
\end{remark}

It can be shown, via a probabilistic proof, that:

\begin{theorem}\label{prg-theorem}
There exists a PRG against nonuniform time $t(n)$ with seed length
$O(\log t(n))$
\end{theorem}

Note that Theorem~\ref{prg-theorem} says nothing about the
efficiency of the PRG. The existence of an efficient PRG satisfying
the condition of Theorem~\ref{prg-theorem} implies $\mr{BPP} \ne
\mr{P}$, by Theorem~\ref{thm1}.\bigskip

%\begin{proof-sketch}
%We show that such a PRG exists by a probabilistic argument. Let $G :
%\{0,1\}^{\ell(n)} \longrightarrow \{0,1\}$ be a random function with
%$\ell(n) = \log(t(n))$. In order for an algorithm $T$ to distinguish
%$G(\scr U_{\ell(n)})$ from $\scr U_n$ any better than random
%guessing, $T$ must observe collisions among the sequence of outputs
%produced by $G(\scr U_{\ell(n)})$. Using this observation, one can
%work out that, in time $t(n)$, $T$ will $\epsilon$-distinguish
%$G(\scr U_{\ell(n)})$ from $\scr U_n$ with probability no better
%than $2^{-\Omega(\log(t(n))\epsilon^2}$. As $T$ is nonuniform and
%the number of circuits of size $n$ is $2^{\mr{poly}(n)}$, by the
%union bound we get that the probability that any $T$
%$\epsilon$-distinguishes $G(\scr U_{\ell(n)})$ from $\scr U_n$ is
%$\le 2^{\mr{poly}(n)-\Omega(\log(t(n))\epsilon^2} < 1$.
%\end{proof-sketch}

\begin{theorem}
If there exists an efficient PRG, then $\mr{P} \ne \mr{NP}$.
\end{theorem}

\begin{proof}
Toward a contradiction, suppose $G : \{0,1\}^{\ell(n)}
\longrightarrow \{0,1\}^n$ is an efficient PRG and assume $\mr{P} =
\mr{NP}$. Define test $T(x)$ by
\[
    T(x) =
    \begin{cases}
      0 &\text{if $\exists y$ s.t.\ $G(y) = 1$},\\
      1 &\text{otherwise.}
    \end{cases}
\]
$T$ distinguishes distributions $G(\scr U_{\ell(n)})$ and $\scr U_n$
with advantage $\ge \frac 1 2$, as
\begin{align*}
  &\Pr[T(G(\scr U_{\ell(n)})) = 1] = 1,\\
  &\Pr[T(\scr U_n) = 1] \le \frac{2^{\ell(n)}}{2^n} \le
  \frac 1 2 \text{ since }\ell(n) < n.
\end{align*}
Notice that $T$ is computable in $\mr{NP}$, since a nondeterministic
algorithm can guess $y$ and then verify that $G(y) = 1$ in
polynomial time. Since we are assuming $\mr{P} = \mr{NP}$, it
follows that $T$ is efficient. But this contradicts the assumption
that $G$ is a PRG, since $T$ distinguishes $G(\scr U_{\ell(n)})$
from the uniform distribution $\scr U_n$.
\end{proof}

In the previous lecture, we discussed three different notions of
randomness. We now add a fourth: unpredictability.

\begin{definition}[Next-bit unpredictability]
Let $\scr X = (X_1,\dots,X_n)$ be a distribution on $\{0,1\}^n$.
$\scr X$ is {\em next-bit unpredictable} if for every p.p.t.\
``predictor'' algorithm $P$, there exists a negligible function
$\epsilon(n)$ \tu(where negligible means $\epsilon(n) = O(\frac 1
{n^c})$ for all $c > 0$\tu) such that
\[
    \Pr_{\substack{i \in_{\mr R} [n]\\ \text{coins of
    }P}}[P(X_1,\dots,X_{i-1}) = X_i] \le \frac 1 2 + \epsilon(n)
\]
\end{definition}

Surprisingly, next-bit unpredictability turns out to be an
equivalent notion to pseudorandomness.

\begin{theorem}
$\scr X$ is pseudorandom if, and only if, it is next-bit
unpredictable.
\end{theorem}

\begin{proof}
($\Longrightarrow$) Suppose $P$ is not next-bit unpredictable. Then
for some $c > 0$,
\[
    \Pr_{i \in_{\mr R} [n]}[P(X_1,\dots,X_{i-1}) = X_i] >
    \frac 1 2 + \frac 1 {n^c}.
\]
In particular, there exists $i \in [n]$ such that
\[
    \Pr[P(X_1,\dots,X_{i-1}) = X_i] >
    \frac 1 2 + \frac 1 {n^c}.
\]
We now define an efficient test $T(y_1,\dots,y_n)$ by
\[
    T(y_1,\dots,y_n) =
    \begin{cases}
        0 &\text{if }P(y_1,\dots,y_{i-1}) \ne y_i,\\
        1 &\text{if }P(y_1,\dots,y_{i-1}) = y_i.
    \end{cases}
\]
We have
\begin{align*}
    \Pr_{y \in \scr U_n}[T(y) = 1] &= \frac 1 2\\
    \Pr_{y \in \scr X}[T(y) = 1] &> \frac 1 2 + \frac 1
    {n^c}.
\end{align*}
So $T$ distinguishes between distributions $\scr X$ and $\scr U_n$
with advantage $> \frac 1 {n^c}$. Therefore, $X$ is not
pseudorandom.\bigskip

($\Longleftarrow$) Suppose $\scr X$ is not pseudorandom. Then there
is a p.p.t.\ algorithm $T$ such that
\[
    \mr{advantage}(T) = |\Pr[T(\scr X) = 1] - \Pr[T(\scr U_n) = 1]| >
    \frac 1 {n^c}.
\]
Without loss of generality, we assume that $\Pr[T(\scr X) = 1] >
\Pr[T(\scr U_n) = 1]$; for if the inequality goes the other way,
then we substitute $T$ with its complement.

We use a ``hybrid argument'' to construct a next-bit predictor
algorithm. Let $U_1,\dots,U_n$ be uniform independent random
variables on $\{0,1\}$, so that $\scr U_n = (U_1,\dots,U_n)$. We
define a sequence of distributions:
\begin{align*}
    \scr D_0 &= (U_1,\dots,U_n) = \scr U_n\\
    \scr D_1 &= (X_1,U_2,\dots,U_n)\\
    \scr D_2 &= (X_1,X_2,U_3,\dots,U_n)\\
    &\vdots\\
    \scr D_i &= (X_1,\dots,X_i,U_{i+1},\dots,U_n)\\
    &\vdots\\
    \scr D_n &= (X_1,\dots,X_n) = \scr X.
\end{align*}
Notice that
\begin{equation}\tag{$\star$}
    T(\scr D_{i-1}) = \frac 1 2 \Big( T(\scr D_i) +
    T(X_1,\dots,X_{i-1},1-X_i,U_{i+1},\dots,U_n)\Big)
\end{equation}
Now, we have
\[
    \frac 1{n^c} < \Pr[T(\scr D_n) = 1] - \Pr[T(\scr D_0) = 1] =
    \sum_{i \in [n]}\Pr[T(\scr D_i) = 1] - \Pr[T(\scr D_{i-1}) = 1].
\]
Therefore, there exists $i \in [n]$ such that $\Pr[T(\scr D_i) = 1]
- \Pr[T(\scr D_{i-1}) = 1] > \frac 1{n^{c+1}}$.

We define p.p.t.\ ``predictor'' algorithm
$P(x_1,\dots,x_{i-1},y_i,\dots,y_n)$ with input bits
$x_1,\dots,x_{i-1}$ and random bits (coins) $y_i,\dots,y_n
\in_{\mr{R}} \{0,1\}$ by
\[
    P(x_1,\dots,x_{i-1},y_i,\dots,y_n) =
    \begin{cases}
      y_i &\text{if } T(x_1,\dots,x_{i-1},y_i,\dots,y_n) = 1\\
      1-y_i &\text{otherwise.}
    \end{cases}
\]
\begin{align*}
    &\Pr[P(X_1,\dots,X_{i-1},U_i,\dots,U_n) = X_i]\\
    &= \frac 1 2\Big(\Pr[P(X_1,\dots,X_{i-1},U_i,\dots,U_n) = X_i \mid U_i =
    X_i] + \Pr[P(X_1,\dots,X_{i-1},U_i,\dots,U_n) = X_i
    \mid U_i \ne X_i]\Big)\\
    &= \frac 1 2\Big(\Pr[P(X_1,\dots,X_i,U_{i+1},\dots,U_n) = X_i] +
    \Pr[P(X_1,\dots,X_{i-1},1-X_i,U_{i+1}\dots,U_n) = X_i]\Big)\\
    &= \frac 1 2\Big(\Pr[T(X_1,\dots,X_i,U_{i+1}\dots,U_n)=1] +
    \Pr[T(X_1,\dots,X_{i-1},1-X_i,U_{i+1}\dots,U_n)=0]\Big)\\
    &= \frac 1 2\Big(\Pr[T(\scr D_i)=1] + \Big(1-
    \Pr[T(X_1,\dots,X_{i-1},1-X_i,U_{i+1}\dots,U_n)=1]\Big)\Big)\\
    &= \frac 1 2 + \frac 1 2\Big(\Pr[T(\scr D_i)=1]-
    \underbrace{\Pr[T(X_1,\dots,X_{i-1},1-X_i,U_{i+1}\dots,U_n)=1]}_
    {\textstyle = 2\Pr[T(\scr D_{i-1})=1] -
    \Pr[T(\scr D_i)=1]\text{ by ($\star$)}}\Big)\\
    &= \frac 1 2 + \Big(\Pr[T(\scr D_i)=1] - \Pr[T(\scr
    D_{i-1}=1)]\Big)\\
    &> \frac 1 2 + \frac 1 {n^{c+1}}.
\end{align*}
By defining $P(x_1,\dots,x_j) \in_{\mr{R}} \{0,1\}$ for values of $j
\in [n]-\{i\}$, we get
\begin{align*}
    &\Pr_{j \in_{\mr R} [n]}[P(X_1,\dots,X_{j-1}) = X_j]\\
    &=
    \frac{1}{n}\Big(\Pr[P(X_1,\dots,X_{i-1}) = X_i] +
    \sum_{\!\!\!\!j \in_{\mr R} [n]-\{i\}\!\!\!\!}
    \Pr[P(X_1,\dots,X_{j-1}) = X_j]\Big)
    >
    \frac{1}{n}\Big(\frac{n}{2} + \frac{1}{n^{c+1}}\Big) =
    \frac{1}{2} + \frac{1}{n^{c+2}}.
\end{align*}
Thus, we have shown that $\scr X$ is not next-bit unpredictable.
\end{proof}


\end{document}