Low-noise LPN ⇒ CRHF

Standard model · BLVW19 · security loss: a factor $k^{O(1)}$: a collision finder with success $\delta$ gives an LPN distinguisher with advantage at least $\frac{\delta }{2}(1-2\epsilon {)}^{2w}=\delta \cdot k^{-O(1)}$

Statement

If low-noise LPN is hard at noise rate $\epsilon ={\log }^2(k)/k$, then collision-resistant hash functions exist — BLVW19.

Sketch

The key is a uniform $\mathbf{A}\in {\mathbb{F}}_2^{m\times k}$ with $m=\mathrm{poly}(k)$, and $h_{\mathbf{A}}(\mathbf{x})={\mathbf{A}}^{\top }\mathbf{x}\in {\mathbb{F}}_2^k$ on inputs $\mathbf{x}\in {\mathbb{F}}_2^m$ of Hamming weight at most $w=O(k/\log k)$, which compresses once $w\log (m/w)>k$. A collision $\mathbf{x}\ne {\mathbf{x}}^{\prime }$ gives a nonzero $\mathbf{z}=\mathbf{x}+{\mathbf{x}}^{\prime }$ of weight at most $2w$ with ${\mathbf{A}}^{\top }\mathbf{z}=0$, so for $\mathbf{v}=\mathbf{As}+\mathbf{e}$ the bit $⟨\mathbf{z},\mathbf{v}⟩=⟨\mathbf{z},\mathbf{e}⟩$ is $0$ with probability $\frac{1}{2}+\frac{1}{2}(1-2\epsilon {)}^{|\mathbf{z}|}\ge \frac{1}{2}+k^{-O(1)}$ at $\epsilon ={\log }^2(k)/k$, while for uniform $\mathbf{v}$ it is uniform.

Notes

• LPN at this noise rate lies in ${\mathbf{BPP}}^{\mathbf{SZK}}$ — BLVW19.
• Sub-exponentially hard constant-noise LPN also gives collision-resistant hash functions (Subexponential LPN ⇒ CRHF) — YZW+19.