Lecture 12

Continue on pseudo-randomness

$\{X_n\}$ and $\{Y_n\}$ are distinguishable by $\mu(n)$ if $\exists$ distinguisher $D$

• If $\mu(n)\geq \frac{1}{p(n)}\gets poly(n)$ for infinitely many n, then $\{X_n\}$ and $\{Y_n\}$ are distinguishable.
• Otherwise, indistinguishable ($|diff|<\varepsilon(n)$)

Property: Closed under efficient procedures.

If $M$ is any n.u.p.p.t. which can take a ample from $t$ from $X_n,Y_n$ as input $M(X_n)$

If $\{X_n\}\approx\{Y_n\}$, then so are $\{M(X_n)\}\approx\{M(Y_n)\}$

Proof:

If $D$ distinguishes $M(X_n)$ and $M(Y_n)$ by $\mu(n)$ then $D(M(\cdot))$ is also a polynomial-time distinguisher of $X_n,Y_n$.

Hybrid Lemma

Let $X^0_n,X^1_n$ are ensembles indexed from $1,..,m$

If $D$ distinguishes $X_n^0$ and $X_n^m$ by $\mu(n)$, then $\exists i,1\leq i\leq m$ where $X_{n}^{i-1}$ and $X_n^i$ are distinguished by $D$ by $\frac{\mu(n)}{m}$

Proof: (we use triangle inequality.) Let $p_i=P[t\gets X_n^i:D(t)=1],0\leq i\leq m$. We have $|p_0-p_m|\geq m(n)$

Using telescoping tricks:

If all $|p_{i-1}-p_i|<\frac{\mu(n)}{m},|p_0-p_m|<\mu_n$ contradiction.

In applications, only useful if $m\leq q(n)$ polynomial

If $X_0$ and $X^m$ are distinguishable by $\frac{1}{p(n)}$, then $2$ inner "hybrids" are distinguishable $\frac{1}{p(n)q(n)}=\frac{1}{poly(n)}$

Example:

For some Brian in Week 1 and Week 50, a distinguisher $D$ outputs 1 if hair is considered "long".

There is some week $i,1\leq i\leq 50$ $|p_{i-1}-p_i|\geq 0.02$

By prediction lemma, there is a machine that could

Next bit test (NBT)

We say $\{X_n\}$ passes the next bit test if $\forall i\in\{0,1,...,l(n)-1\}$ on $\{0,1\}^{l(n)}$ and for all adversaries $\mathcal{A}:P[t\gets X_n:\mathcal{A}(t_1,t_2,...,t_i)=t_{i+1}]\leq \frac{1}{2}+\varepsilon(n)$ (given first $i$ bit, the probability of successfully predicts $i+1$ th bit is almost random $\frac{1}{2}$)

Note that for any $\mathcal{A}$, and any $i$,

If $\{X_n\}\approx\{U_{l(n)}\}$ (pseudorandom), then $X_n$ must pass NBT for all $i$.

Otherwise $\exists \mathcal{A},i$ where for infinitely many $n$,

We can build a distinguisher $D$ from $\mathcal{A}$.

The converse if True!

The NBT(Next bit test) is complete.

If $\{X_n\}$ on $\{0,1\}^{l(n)}$ passes NBT, then it's pseudorandom.

Idea of proof: full proof is on the text.

Our idea is that we want to create $H^{l(n)}_n=\{X_n\}$ and $H^0_n=\{U_{l(n)}\}$

We construct "random" bit stream:

If $\{X_n\}$ were not pseudorandom, there is a $D$

By hybrid lemma, there is $i,1\leq i\leq l(n)$ where:

$l(n)$ is the step we need to take transform $X$ to $X^n$

Let,

notice that only two bits are distinguished in the procedure.

D can distinguish $x_{i+1}$ from a truly random $U_{i+1}$, knowing the first $i$ bits $x_i\dots x_i$ came from $x\gets x_n$

So $D$ can predict $x_{i+1}$ from $x_1\dots x_i$ (contradicting with that $X$ passes NBT)

EOP

Pseudorandom Generator

Suppose $G:\{0,1\}^*\to\{0,1\}^*$ is a pseudorandom generator if the following is true:

1. $G$ is efficiently computable.
2. $|G(x)|\geq |x|\forall x$ (expansion)
3. $\{x\gets U_n:G(x)\}_n$ is pseudorandom

$n$ truly random bits $\to$ $n^2$ pseudorandom bits

PRG exists if and only if one-way function exists

The other part of proof will be your homework, damn.

If one-way function exists, then Pseudorandom Generator exists.

Idea of proof:

Let $f:\{0,1\}^n\to \{0,1\}^n$ be a strong one-way permutation (bijection).

$x\gets U_n$

$f(x)||x$

Not all bits of $x$ would be hard to predict.

Hard-core bit: One bit of information about $x$ which is hard to determine from $f(x)$. $P[$ success $]\leq \frac{1}{2}+\varepsilon(n)$

Depends on $f(x)$