Subexponential LPN ⇒ OT

Standard model · YZ16 · security loss: requires $2^{\omega (n^{1/2})}$ hardness of constant-noise LPN

Statement

Constant-noise LPN that is $2^{\omega (n^{1/2})}$-hard — every adversary of time $T=2^{\omega (n^{1/2})}$ has advantage at most $1/T$, for secret length $n$ — implies OT, via a variant of LPN that remains hard on secrets of poly-logarithmic entropy — YZ16.