Learning parity with noise (LPN)

The learning parity with noise (LPN) assumptions is a post-quantum candidate assumption that is related to the Learning with errors assumption.

Assumption

For parameters $k\in \mathbb{N}$ and $0<\epsilon <1$, we say the $(k,\epsilon ,m)$-LPN advantage of an adversary $\mathcal{A}$ as ${\text{Adv}}_{\mathcal{A}}^{(k,\epsilon )\text{-lpn}}(\lambda )=\mathrm{Pr}[\mathcal{A}(1^{\lambda },\mathbf{A},{\mathbf{v}}_b)=b],$ where $\mathbf{A}\leftarrow {\mathbb{F}}_2^{m\times k}$, ${\mathbf{v}}_0\leftarrow {\mathbb{F}}_2^m$, and $v_1:=\mathbf{A}\cdot \mathbf{s}+\mathbf{r}$, where $\mathbf{s}\leftarrow {\mathbb{F}}_2^k$ and $\mathbf{r}=(\text{Ber}(\epsilon ){)}_{i\in [m]}$.

Then, we say that $(k,\epsilon )$-LPN is hard if there exists a negligible function $\nu$ such that for all efficient adversaries $\mathcal{A}$ and all polynomials $m:=m(\lambda )$, ${\text{Adv}}_{\mathcal{A}}^{(k,\epsilon )\text{-lpn}}(\lambda )\le \nu (\lambda ).$

Noise Level

Depending on the setting of $\epsilon$ relative to $k$, the $(k,\epsilon )$-LPN problem has different regimes which are generally known to imply different results.

• Constant-noise: $0<\epsilon <1/2$ (weakest assumption)
• High-noise: $\epsilon =1/k^{\gamma }$ for $0<\gamma <1/2$
• Mid-noise: $\epsilon =1/k^{\gamma }$ for every $\gamma <1$
• Low-noise: $\epsilon ={\log }^c(k)/k$ for some $c>1$. (strongest assumption)

Subexponential LPN

Some applications require assuming subexponential LPN, which means that they assume any algorithm which achieve non-negligible advantage in the LPN game requires running in time $2^{\omega (k^{\epsilon })}$ for some $\epsilon >0$ (often $\epsilon =1/2$).

In other words, any algorithm which runs in $2^{O(k^{\epsilon })}$ time has negligible advantage. Whereas, the normal LPN assumption only makes an assumption about polynomial time adversaries. Typically, this assumption is made only in the constant-noise regime, making it incomparable to more standard lower-noise normal LPN assumptions.

Related results

• Mid-noise (and hence low-noise) LPN implies Public key encryption — Ale03
• Some works show that Low-noise LPN with $\epsilon ={\log }^{2}k/k$ implies Collision-resistant hash function — BLVW19, YZW+19
• Low-noise LPN with $\epsilon ={\log }^{1+\beta }k/k$, where $0<\beta <1$, is known to imply PIR with slightly sublinear communication $N/2^{\Theta ({\log }^{1-\beta }N)}$ (through the use of Trapdoor hash functions)— AMR25
  • Fully sublinear PIR from any flavor of LPN is open.
• SK-DEPIR can be built from mid and high-noise LPN — CIMR25 - Secret-Key PIR from Random Linear Codes
• CCA-PKE and OT can be built from subexponential LPN— YZ16
• Public-key PRCs can be built from subexponential LPN — CG24 

Attacks

TODO