Factoring with known factor structure ⇒ PRG

Fully-black-box reduction · standard model · VV84 · security loss: polynomial: a factor $m$ from Yao’s next-bit hybrid, and a polynomial loss in turning a low-order-bit predictor into a factoring algorithm

Statement

If factoring Blum integers is hard, the Blum–Blum–Shub generator is a PRG: for a Blum integer $N=pq$ with $p\equiv q\equiv 3(\mathrm{mod}4)$ and a seed $x\stackrel{\$}{\leftarrow }{\mathbb{Z}}_N^{\ast }$, it sets $x_0=x^2\mathrm{mod}N$ and $x_{i+1}=x_i^2\mathrm{mod}N$, and outputs $\mathrm{lsb}(x_1),\dots ,\mathrm{lsb}(x_m)$ — VV84. Its security under the stronger quadratic residuosity assumption for Blum integers is QR ⇒ PRG — BBS86.

Sketch

Squaring permutes the quadratic residues modulo a Blum integer, so each $x_i$ is a uniform residue and the bits after $\mathrm{lsb}(x_i)$ are computable from $x_{i+1}$; Yao’s equivalence of indistinguishability and unpredictability, applied right to left, turns a distinguisher into a predictor of the low-order bit of the principal square root of a random residue. For $x$ of Jacobi symbol $+1$ exactly one of $x,N-x$ is a residue and the two have opposite parity, so the predictor decides quadratic residuosity (BBS86). VV84 show that it also extracts square roots and hence factors $N$.

Notes

• The generator may output the $O(\log \log N)$ low-order bits of each state — VV84.