Subexponential LPN ⇒ Polylogarithmic-dimension LPN
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 .