Subexponential LPN ⇒ CRHF

Standard model · YZW+19 · security loss: a factor $2^{O(w)}$ for input weight $w$: a collision finder with success $\delta$ gives an LPN distinguisher with advantage at least $\frac{\delta }{2}(1-2\epsilon {)}^{2w}$

Statement

If constant-noise LPN is $2^{k^{1/2+\delta }}$-hard for a constant $\delta >0$ (subexponential LPN with exponent above $1/2$) or $2^{\Omega (k/\log k)}$-hard given $\mathrm{poly}(k)$ samples, then collision-resistant hash functions exist, via the binary shortest-vector problem — YZW+19.

Sketch

The hash is $h_{\mathbf{A}}(\mathbf{x})={\mathbf{A}}^{\top }\mathbf{x}$ for a uniform $\mathbf{A}\in {\mathbb{F}}_2^{m\times k}$, on regular inputs $\mathbf{x}\in {\mathbb{F}}_2^m$ with a single one in each of $w$ blocks of length $m/w$, described by $w\log (m/w)$ bits and so compressing once that exceeds $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$, a binary-SVP solution, and then ${\mathbf{z}}^{\top }(\mathbf{As}+\mathbf{e})={\mathbf{z}}^{\top }\mathbf{e}$ is $0$ with probability at least $\frac{1}{2}\left(1+(1-2\epsilon {)}^{2w}\right)$ on LPN samples of noise rate $\epsilon$, against $\frac{1}{2}$ on uniform ones.

Notes

• LPN at noise rate $1/\sqrt{k}$ that is $2^{\Omega (\sqrt{k}/\log k)}$-hard given $\mathrm{poly}(k)$ samples also implies collision-resistant hash functions — YZW+19.
• The hash functions have constant, or even polylogarithmic, shrinkage and are computed by polynomial-size depth-3 circuits of NOT, unbounded fan-in AND and XOR gates — YZW+19.