Mid-noise LPN ⇒ PKE

Fully-black-box reduction · standard model · Ale03 · security loss: polynomial: decisional-LPN hybrids for the public key and for each encryption of $0$

Statement

If decisional mid-noise LPN is hard at noise rate $\epsilon =\Theta (1/\sqrt{k})$, the $\gamma =1/2$ case of $\epsilon =k^{-\gamma }$, then IND-CPA-secure PKE exists — Ale03. Hardness at any lower noise rate, including the low-noise regime $\epsilon ={\log }^c(k)/k$, suffices, since adding independent noise maps its samples to rate-$\Theta (1/\sqrt{k})$ samples (noise monotonicity) — folklore.

Sketch

The public key is a random linear code $C\subseteq {\mathbb{F}}_2^m$ and a noisy codeword $\mathbf{c}+\mathbf{e}$, $\mathbf{c}\in C$, whose noise $\mathbf{e}$ of weight $\Theta (\sqrt{m})$ is the secret key; $0$ encrypts to ${\mathbf{c}}^{\perp }+\tilde{\mathbf{e}}$ for a random ${\mathbf{c}}^{\perp }$ in the dual of the code spanned by $C$ and $\mathbf{c}+\mathbf{e}$ and a fresh $\tilde{\mathbf{e}}$ of weight $\Theta (\sqrt{m})$, and $1$ encrypts to a uniform vector. Since $\mathbf{e}$ lies in that code, an encryption of $0$ has inner product $⟨\mathbf{e},\tilde{\mathbf{e}}⟩$ with $\mathbf{e}$, biased toward $0$ because two independent weight-$\Theta (\sqrt{m})$ vectors in ${\mathbb{F}}_2^m$ overlap in $O(1)$ positions in expectation, while an encryption of $1$ has a uniform one, so the bit is recovered with constant advantage, which standard amplification boosts. Security is two decisional-LPN hybrids, replacing the noisy codeword and then the encryption of $0$ by uniform vectors.