Subexponential LPN ⇒ IND-CCA PKE

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

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 IND-CCA-secure PKE, via a variant of LPN that remains hard on secrets of poly-logarithmic entropy — YZ16.