Subexponential LPN ⇒ Polylogarithmic-dimension LPN

Fully-black-box reduction · standard model · folklore · security loss: none

Statement

If subexponential LPN holds with noise rate , then polylogarithmic-dimension LPN holds with : for every function , every polynomial-time adversary distinguishes from , for , , and , with advantage negligible in — standard.

Sketch

Take with for all large , and set , so that and . For , a distinguisher running in time on the samples is then within the time and sample bound for all large , so its advantage is at most .