Subexponential LPN ⇒ CRHF

Standard model · YZW+19

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.

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.