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 \bits$
\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. The regimes below are ordered from weakest to strongest assumption: hardness at lower noise implies hardness at higher noise — folklore.

• Low-noise LPN ⇒ Mid-noise LPN
• Mid-noise LPN ⇒ High-noise LPN
• High-noise LPN ⇒ Constant-noise LPN

Constant-noise LPN

The noise rate is a constant $\epsilon \in (0,1/2)$.

High-noise LPN

The noise rate is $\epsilon =k^{-\gamma }$ for a constant $0<\gamma <1/2$.

Mid-noise LPN

The noise rate is $\epsilon =k^{-\gamma }$ for a constant $1/2\le \gamma <1$.

Low-noise LPN

The noise rate is $\epsilon ={\log }^c(k)/k$ for a constant $c>1$.

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 achieves 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 LPN ⇒ PKE
• Low-noise LPN ⇒ CRHF
• Low-noise LPN ⇒ TDH
• TDH ⇒ cPIR
• High-noise LPN ⇒ SK-DEPIR
• High-noise LPN ⇒ Secret-Key PIR (SK-PIR)
• Subexponential LPN ⇒ IND-CCA PKE
• Subexponential LPN ⇒ OT
• Subexponential LPN ⇒ CRHF
• Subexponential LPN ⇒ PRC
• Subexponential LPN ⇒ Zero-bit PRC

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 \bits$
\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.

Known results

• Additively homomorphic encryption + Sparse LPN ⇒ SHE
• DDH + Sparse Learning Parity with Noise ⇒ Somewhat homomorphic encryption (SHE)
• Noisy k-LIN + PC ⇒ PKE

Ring-LPN

Ring-LPN replaces the matrix $\mathbf{A}\in {\mathbb{F}}_2^{m\times k}$ with multiplication by a random element of $R={\mathbb{F}}_2[x]/(f(x))$ for a fixed polynomial $f$ of degree $k$. For a secret $s\stackrel{\$}{\leftarrow }R$, it asks to distinguish samples $(a,a\cdot s+e)$, with fresh $a\stackrel{\$}{\leftarrow }R$ and noise $e\in R$ whose coefficients are drawn independently from $\mathrm{Ber}(\epsilon )$, from uniform samples over $R^2$ — HKLPP12. The ring structure reduces the public key from $O(mk)$ bits to $O(k)$ bits and enables faster computation via polynomial multiplication.

Ring-LPN over ${\mathbb{F}}_2[x]/(f(x))$ yields Lapin, a two-round symmetric-key authentication protocol secure against active attacks — HKLPP12.

Sparse Ring-LPN

For a prime $p$, a polynomial $F\in {\mathbb{Z}}_p[X]$, $R_p={\mathbb{Z}}_p[X]/(F(X))$, and a weight $t$, Sparse Ring-LPN asks to distinguish $(a,ae+f)$ from $(a,u)$ for uniform $a,u\in R_p$ and $t$-sparse $e,f\in R_p$ — BCG+20.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{srlpn}}_{p,F,t,\calA}(\secpar)$}
\begin{algorithmic}
\State $a \getsr R_p$; $b \getsr \bits$
\State $e, f \gets$ $t$-sparse elements of $R_p$
\State $v_0 := a e + f$
\State $v_1 \getsr R_p$
\State $b' \gets \calA(1^\secpar, a, v_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

$(p,F,t)$-Sparse Ring-LPN is hard if for all efficient $\mathcal{A}$,

$${\mathbf{Adv}}_{p,F,t,\mathcal{A}}^{\mathrm{srlpn}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{p,F,t,\mathcal{A}}^{\mathrm{srlpn}}(\lambda )=1\right]-1\right|$$

is negligible.

Sparse Ring-LPN yields pseudorandom correlation generators for OLE and authenticated multiplication triples over large fields — BCG+20.

• Sparse Ring-LPN ⇒ PCG

Participates in

Builds on Learning parity with noise

• SXDH + LWE + LPN + NC0-PRG ⇒ iO
• DDH + Sparse Learning Parity with Noise ⇒ Somewhat homomorphic encryption (SHE) (via Sparse Learning Parity with Noise)
• High-noise LPN ⇒ Constant-noise LPN (via High-noise LPN)
• Mid-noise LPN ⇒ High-noise LPN (via Mid-noise LPN)
• High-noise LPN ⇒ Secret-Key PIR (SK-PIR) (via High-noise LPN)
• Subexponential LPN ⇒ Zero-bit PRC (via Subexponential LPN)
• High-noise LPN ⇒ SK-DEPIR (via High-noise LPN)
• Low-noise LPN ⇒ CRHF (via Low-noise LPN)
• Low-noise LPN ⇒ Mid-noise LPN (via Low-noise LPN)
• Mid-noise LPN ⇒ PKE (via Mid-noise LPN)
• Low-noise LPN ⇒ TDH (via Low-noise LPN)
• Additively homomorphic encryption + Sparse LPN ⇒ SHE (via Sparse Learning Parity with Noise)
• Sparse Ring-LPN ⇒ PCG (via Sparse Ring-LPN)
• Sparse Learning Parity with Noise ⇒ Pseudorandom correlation generators (PCG) (via Sparse Learning Parity with Noise)
• Subexponential LPN ⇒ CRHF (via Subexponential LPN)
• Subexponential LPN ⇒ OT (via Subexponential LPN)
• Subexponential LPN ⇒ IND-CCA PKE (via Subexponential LPN)
• Subexponential LPN ⇒ PRC (via Subexponential LPN)

Produces Learning parity with noise

• High-noise LPN ⇒ Constant-noise LPN (via Constant-noise LPN)
• Mid-noise LPN ⇒ High-noise LPN (via High-noise LPN)
• LSN ⇒ LPN
• Low-noise LPN ⇒ Mid-noise LPN (via Mid-noise LPN)