Paper 2017/1260

Learning Parity with Noise Implies Collision Resistant Hashing

Yu Yu and Jiang Zhang and Jian Weng and Chun Guo and Xiangxue Li

Abstract

The Learning Parity with Noise (LPN) problem has recently found many cryptographic applications such as authentication protocols, pseudorandom generators/functions and even cryptomania tasks including public-key encryption (PKE) schemes and oblivious transfer (OT) protocols. It however remains a long-standing open problem whether LPN implies collision resistant hash (CRH) functions. In this paper, we answer this question affirmatively by showing that CRH is implied by (the two most common variants of) LPN. More specifically, for any constant $\epsilon>0$, assume that (1) the low-noise LPN problem (i.e., at noise rate $1/\sqrt{n}$) is $2^{4\sqrt{n}/\log n}$-hard given $q=n^{3+\epsilon}$ samples; (2) or that the constant-noise LPN problem is $2^{n^{0.5+\epsilon}}$-hard; then there exists CRH functions with constant (resp., poly-logarithmic) shrinkage, which can be implemented using polynomial-size depth-3 circuits with NOT, (unbounded fan-in) AND and XOR gates. Our technical route LPN$\rightarrow$bSVP$\rightarrow$CRH is reminiscent of the known reductions for the large-modulus analogue, i.e., LWE$\rightarrow$SIS$\rightarrow$CRH, where the binary Shortest Vector Problem (bSVP) was recently introduced by Applebaum et al. (ITCS 2017) that enables CRH in a similar manner to Ajtai's CRH functions based on the Short Integer Solution (SIS) problem. In addition to the feasibility established, we discuss also the practical relevance of the CRH functions constructed (from the hardness of LPN). Interestingly, the SHA-3 proposal Fast Syndrome Based (FSB) hash resembles a concrete (but aggressive) instantiation of the LPN-based CRH construction. Furthermore, we show how to implement the polynomially shrinking CRH functions more efficiently using idealized heuristics such as a block cipher (keyed by a public random string) behaves like a random permutation.