DLOG ⇒ PRG

Fully-black-box reduction · standard model · BM84 · security loss: polynomial: a factor $m$ for $m$ output bits from the next-bit hybrid, composed with the polynomial loss of recovering the discrete logarithm from a predictor for the half-interval bit

Statement

If DLOG is hard in ${\mathbb{Z}}_p^{\ast }$ ($p$ prime, $g$ a generator), the Blum–Micali generator is a PRG: from a uniform seed $x_0$, it iterates $x_{i+1}=g^{x_i}\mathrm{mod}p$ and outputs at each step the bit $[x_i\ge (p-1)/2]$, the most significant bit of the discrete logarithm of $x_{i+1}$ — BM84.

Sketch

The half-interval predicate is hard-core for $x\mapsto g^x$: given $y=g^x$, Euler’s criterion gives the parity of $x$, and the predicate identifies which square root of $y{g}^{-(x\mathrm{mod}2)}$ has index $\lfloor x/2\rfloor$, so recursing recovers $x$ bit by bit; a predictor with only noticeable advantage is first amplified by random self-reduction. A distinguisher for the generator yields such a predictor by the next-bit test — Yao82a.

Notes

• The next-bit test characterizes pseudorandomness, and the construction generalizes to a PRG from any one-way permutation — Yao82a.
• Efficiency: each output bit costs one exponentiation modulo $p$ — standard.