Constant-noise LPN ⇒ PRG

Fully-black-box reduction · standard model · BFKL93 · security loss: a distinguisher for the generator is an LPN distinguisher, up to the statistical distance of the error sampling

Statement

If LPN with constant noise $\epsilon \in (0,1/2)$ is hard, then pseudorandom generators exist — BFKL93.

Sketch

Decisional LPN makes $(\mathbf{A},\mathbf{As}+\mathbf{e})$ indistinguishable from uniform. The error vector has entropy about $H(\epsilon )m<m$ for $\epsilon <1/2$, so with $m$ large relative to $k$ it can be sampled from fewer random bits than the $m$ output bits it masks, and the map from the seed $(\mathbf{A},\mathbf{s},\text{coins for }\mathbf{e})$ to $(\mathbf{A},\mathbf{As}+\mathbf{e})$ stretches — BFKL93.

Notes

• Hardness at any lower noise rate implies hardness at constant noise: High-noise LPN ⇒ Constant-noise LPN — folklore.