Lecture 13

Pseudorandom Generator (PRG)

$G:\{0,1\}^n\to\{0,1\}^{l(n)}$ is a pseudorandom generator if the following is true:

1. $G$ is efficiently computable.
2. $l(n)> n$ (expansion)
3. $\{x\gets \{0,1\}^n:G(x)\}_n\approx \{u\gets \{0,1\}^{l(n)}\}$

Hard-core bit (predicate) (HCB)

Hard-core bit (predicate) (HCB): $h:\{0,1\}^n\to \{0,1\}$ is a hard-core bit of $f:\{0,1\}^n\to \{0,1\}^*$ if for every adversary $A$,

Idea: $f:\{0,1\}^n\to \{0,1\}^*$ is a one-way function.

Given $y=f(x)$, it is hard to recover $x$. A cannot produce all of $x$ but can know some bits of $x$.

$h(x)$ is just a yes/no question regarding $x$.

Example:

In RSA function, we pick $p,q\in \Pi^n$ as primes and $N=pq$. $e\gets \mathbb{Z}_N^*$ and $f(x)=x^e\mod N$.

$h(x)=x_n$ is a HCB of $f$. Given RSA assumption.

h(x) is not necessarily one of the bits of $x=x_1x_2\cdots x_n$.

Theorem Any one-way function has a HCB.

A HCB can be produced for any one-way function.

Let $f:\{0,1\}^n\to \{0,1\}^*$ be a strong one-way function.

Define $g:\{0,1\}^{2n}\to \{0,1\}^*$ as $g(x,r)=(f(x), r),x\in \{0,1\}^n,r\in \{0,1\}^n$. $g$ is a strong one-way function. (proved in homework)

$\langle x,1^n\rangle=x_1+x_2+\cdots +x_n\mod 2$

$\langle x,0^{n-1}1\rangle=x_ n$

Idea of proof:

If A could reliably find $\langle x,1^n\rangle$, with $r$ being completely random, then it could find $x$ too often.

Pseudorandom Generator from HCB

1. $G(x)=\{0,1\}^n\to \{0,1\}^{n+1}$
2. $G(x)=\{0,1\}^n\to \{0,1\}^{l(n)}$

For (1),

Theorem HCB generates PRG

Let $f:\{0,1\}^n\to \{0,1\}^n$ be a one-way permutation (bijective) with a HCB $h$. Then $G(x)=f(x)|| h(x)$ is a PRG.

Proof:

Efficiently computable: $f$ is one-way so $h$ is efficiently computable.

Expansion: $n<n+1$

Pseudorandomness:

We proceed by contradiction.

Suppose $\{G(U_n)\}\cancel{\approx} \{U_{n+1}\}$. Then there would be a next-bit predictor $A$ such that for some bit $i$.

Since $f$ is a bijection, $x\gets U_n$ and $f(x)\gets U_n$.

$G(x)=f(x)|| h(x)$

So $A$ could not predict $t_i$ with advantage $\frac{1}{2}+\epsilon(n)$ given any first $n$ bits.

So $i=n+1$ the last bit, $A$ could predict.

This contradicts the HCB definition of $h$.

Construction of PRG

$G'=\{0,1\}^n\to \{0,1\}^{l(n)}$

using PRG $G:\{0,1\}^n\to \{0,1\}^{n+1}$

Let $s\gets \{0,1\}^n$ be a random string.

We proceed by the following construction:

$G(s)=X_1||b_1$

$G(X_1)=X_2||b_2$

$G(X_2)=X_3||b_3$

$\cdots$

$G(X_{l(n)-1})=X_{l(n)}||b_{l(n)}$

$G'(s)=b_1b_2b_3\cdots b_{l(n)}$

We claim $G':\{0,1\}^n\to \{0,1\}^{l(n)}$ is a PRG.

Corollary: Combining constructions

$f:\{0,1\}^n\to \{0,1\}^n$ is a one-way permutation with a HCB $h: \{0,1\}^n\to \{0,1\}$.

$G(s)=h(x)||h(f(x))||h(f^2(x))\cdots h(f^{l(n)-1}(x))$ is a PRG. Where $f^a(x)=f(f^{a-1}(x))$.

Proof:

$G'$ is a PRG:

1. Efficiently computable: since we are computing $G'$ by applying $G$ multiple times (polynomial of $l(n)$ times).
2. Expansion: $n<l(n)$.
3. Pseudorandomness: We proceed by contradiction. Suppose the output is not pseudorandom. Then there exists a distinguisher $D$ that can distinguish $G'$ from $U_{l(n)}$ with advantage $\frac{1}{2}+\epsilon(n)$.

Strategy: use hybrid argument to construct distributions.

By the hybrid argument, there exists an $i$ such that $D$ can distinguish $H^i$ and $H^{i+1}$ $0\leq i\leq l(n)-1$ by $\frac{1}{p(n)l(n)}$

Show that there exists $D$ for

with advantage $\frac{1}{2}+\epsilon(n)$. (contradiction)