Mid-noise LPN ⇒ IND-CCA PKE

Fully-black-box reduction · standard model · KMP14

Statement

If decisional LPN is hard at noise rate $\Theta (1/\sqrt{k})$, the $\gamma =1/2$ case of mid-noise LPN, with polynomially many samples, then IND-CCA-secure PKE exists — KMP14. The scheme adapts the gadget trapdoor of MP12 to LPN with a double-trapdoor mechanism, and its proof switches trapdoors by a computational variant of the leftover hash lemma — KMP14. Hardness at any lower noise rate, including the low-noise regime, suffices (Low-noise LPN ⇒ Mid-noise LPN) — folklore.

Notes

• The first IND-CCA-secure PKE from LPN is DMN12, under a variant of the LPN problem; KMP14’s scheme is simpler and more efficient — KMP14.
• At the same noise rate, IND-CPA-secure PKE goes back to Alekhnovich — Ale03; from constant-noise LPN, IND-CCA PKE is known under sub-exponential hardness (Subexponential LPN ⇒ IND-CCA PKE) — YZ16.