Subexponential LPN with exponent above 1/2 ⇒ Subexponential LPN

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

Statement

If there are constants and such that -LPN is -hard (2), then subexponential LPN holds with the same and — standard.