Paper 2017/1260
Collision Resistant Hashing from Subexponential Learning Parity with Noise
Yu Yu, Jiang Zhang, Jian Weng, 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 asymmetric tasks including publickey encryption (PKE) schemes and oblivious transfer (OT) protocols. It however remains a longstanding open problem whether LPN implies collision resistant hash (CRH) functions. Based on the recent work of Applebaum et al. (ITCS 2017), we introduce a general framework for constructing CRH from LPN for various parameter choices. We show that, just to mention a few notable ones, under any of the following hardness assumptions (for the two most common variants of LPN) 1) constantnoise LPN is $2^{n^{0.5+\epsilon}}$hard for any constant $\epsilon>0$; 2) constantnoise LPN is $2^{\Omega(n/\log n)}$hard given $q=poly(n)$ samples; 3) lownoise LPN (of noise rate $1/\sqrt{n}$) is $2^{\Omega(\sqrt{n}/\log n)}$hard given $q=poly(n)$ samples. there exists CRH functions with constant (or even polylogarithmic) shrinkage, which can be implemented using polynomialsize depth3 circuits with NOT, (unbounded fanin) AND and XOR gates. Our technical route LPN$\rightarrow$bSVP$\rightarrow$CRH is reminiscent of the known reductions for the largemodulus 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. Furthermore, under additional (arguably minimal) idealized assumptions such as smalldomain random functions or random permutations (that trivially imply collision resistance), we still salvage a simple and elegant collisionresistancepreserving domain extender that is (asymptotically) more parallel and efficient than previously known. In particular, assume $2^{n^{0.5+\epsilon}}$hard constantnoise LPN or $2^{n^{0.25+\epsilon}}$hard lownoise LPN, we obtain a polynomially shrinking collision resistant hash function that evaluates in parallel only a single layer of smalldomain random functions (or random permutations) and produces their XOR sum as output.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A minor revision of an IACR publication in ASIACRYPT 2019
 Keywords
 Learning Parity with NoiseCollision Resistant Hashingbinary Shortest Vector Problem
 Contact author(s)
 yuyuathk @ gmail com
 History
 20190908: last of 7 revisions
 20171231: received
 See all versions
 Short URL
 https://ia.cr/2017/1260
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/1260, author = {Yu Yu and Jiang Zhang and Jian Weng and Chun Guo and Xiangxue Li}, title = {Collision Resistant Hashing from Subexponential Learning Parity with Noise}, howpublished = {Cryptology {ePrint} Archive, Paper 2017/1260}, year = {2017}, url = {https://eprint.iacr.org/2017/1260} }