Learning parity with noise

The learning parity with noise (LPN) assumption is a post-quantum hardness assumption equivalent to the hardness of decoding a random linear code over ${\mathbb{F}}_2$. It can be viewed as LWE specialized to the binary field.

Assumption

For parameters $k\in \mathbb{N}$, noise rate $0<\epsilon <1$, and sample count $m\in \mathrm{poly}(\lambda )$, the LPN game asks an adversary to distinguish a noisy linear system $(\mathbf{A},\mathbf{As}+\mathbf{e})$ from a uniformly random pair.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{lpn}}_{k,\varepsilon,m,\calA}(\secpar)$}
\begin{algorithmic}
\State $\mathbf{A} \getsr \FF_2^{m \times k}$
\State $\mathbf{s} \getsr \FF_2^k$; $\mathbf{e} \getsr \mathrm{Ber}(\varepsilon)^m$
\State $b \getsr \{0,1\}$
\State $\mathbf{v}_0 := \mathbf{A} \cdot \mathbf{s} + \mathbf{e}$
\State $\mathbf{v}_1 \getsr \FF_2^m$
\State $b' \gets \calA(1^\secpar, \mathbf{A}, \mathbf{v}_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

$(k,\epsilon )$-LPN is hard if for all efficient $\mathcal{A}$ and all polynomials $m=m(\lambda )$,

$${\mathbf{Adv}}_{k,\epsilon ,m,\mathcal{A}}^{\mathrm{lpn}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{k,\epsilon ,m,\mathcal{A}}^{\mathrm{lpn}}(\lambda )=1\right]-1\right|$$

is negligible.

LPN is naturally stated over ${\mathbb{F}}_2$. However, it generalizes to any finite field ${\mathbb{F}}_q$: replace ${\mathbb{F}}_2$ with ${\mathbb{F}}_q$ throughout, and let each noise coordinate $e_i$ be zero with probability $1-\epsilon$ and uniformly random in ${\mathbb{F}}_q\setminus \{0\}$ with probability $\epsilon$.

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)

If noise drops to $O(\log (k)/k)$, then there are folklore attacks which run in polynomial time and achieve constant advantage.

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.

Known results

• Mid-noise (and hence low-noise) LPN implies PKE — Ale03
• Some works show that Low-noise LPN with $\epsilon ={\log }^{2}k/k$ implies OWF — 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 TDH)— 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

Variations

Sparse Learning Parity with Noise

Sparse LPN replaces the uniformly random matrix $\mathbf{A}$ with one whose rows are $d$-sparse: each row is sampled uniformly from all binary vectors of Hamming weight exactly $d$. The secret and noise distributions are unchanged. For $d=O(\log k)$, the matrix can be stored and multiplied far more efficiently, making Sparse LPN particularly attractive for pseudorandom correlation generator (PCG) constructions.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{slpn}}_{k,\varepsilon,m,d,\calA}(\secpar)$}
\begin{algorithmic}
\State $\mathbf{A} \getsr \FF_2^{m \times k}$ with each row sampled uniformly from weight-$d$ vectors
\State $\mathbf{s} \getsr \FF_2^k$; $\mathbf{e} \getsr \mathrm{Ber}(\varepsilon)^m$
\State $b \getsr \{0,1\}$
\State $\mathbf{v}_0 := \mathbf{A} \cdot \mathbf{s} + \mathbf{e}$
\State $\mathbf{v}_1 \getsr \FF_2^m$
\State $b' \gets \calA(1^\secpar, \mathbf{A}, \mathbf{v}_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

$(k,\epsilon ,d)$-Sparse LPN is hard if for all efficient $\mathcal{A}$ and all polynomials $m=m(\lambda )$,

$${\mathbf{Adv}}_{k,\epsilon ,m,d,\mathcal{A}}^{\mathrm{slpn}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{k,\epsilon ,m,d,\mathcal{A}}^{\mathrm{slpn}}(\lambda )=1\right]-1\right|$$

is negligible. Note that Sparse LPN with $d=k$ reduces to standard LPN, so sparse hardness is a stronger assumption for smaller $d$.

Known results

• Sparse LPN combined with any linearly homomorphic PKE (e.g., based on DDH or DCR) yields Somewhat Homomorphic Encryption — CHKV25

Ring-LPN

Ring-LPN replaces the matrix $\mathbf{A}\in {\mathbb{F}}_2^{m\times k}$ with multiplication by a random polynomial $a\in {\mathbb{F}}_2[x]/(f(x))$ for a fixed polynomial $f$ of degree $k$. The secret is $s\in {\mathbb{F}}_2[x]/(f(x))$ and the LPN sample is $(a,a\cdot s+e)$ for small noise $e$. The ring structure reduces the public key from $O(mk)$ bits to $O(k)$ bits and enables faster computation via polynomial multiplication.

Ring-LPN underlies practical authentication protocols (e.g., Lapin) and efficient pseudorandom correlation generator constructions.