Cryptology ePrint Archive: Report 2017/1260

Collision Resistant Hashing from Learning Parity with Noise

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 asymmetric 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. 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) constant-noise LPN is $2^{n^{0.5+\epsilon}}$-hard for any constant $\epsilon>0$;

2) constant-noise LPN is $2^{\Omega(n/\log n)}$-hard given $q=poly(n)$ samples;

3) low-noise 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 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.

Furthermore, under additional (arguably minimal) idealized assumptions such as small-domain random functions or random permutations (that trivially imply collision resistance), we still salvage a simple and elegant collision-resistance-preserving domain extender that is (asymptotically) more parallel and efficient than previously known. In particular, assume $2^{n^{0.5+\epsilon}}$-hard constant-noise LPN or $2^{n^{0.25+\epsilon}}$-hard low-noise LPN, we obtain a polynomially shrinking collision resistant hash function that evaluates in parallel only a single layer of small-domain random functions (or random permutations) and produces their XOR sum as output.

Category / Keywords: foundations / Learning Parity with Noise, Collision Resistant Hashing, binary Shortest Vector Problem

Date: received 27 Dec 2017, last revised 17 May 2018

Contact author: yuyuathk at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20180517:132057 (All versions of this report)

Short URL: ia.cr/2017/1260


[ Cryptology ePrint archive ]