## CryptoDB

### Paper: Collision Resistant Hashing from Sub-exponential Learning Parity with Noise

Authors: Yu Yu Jiang Zhang Jian Weng Chun Guo Xiangxue Li DOI: 10.1007/978-3-030-34621-8_1 Search ePrint Search Google 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. Inspired by the recent work of Applebaum et al. (ITCS 2017), we introduce a general construction of 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+\varepsilon }}$-hard for any constant $\varepsilon >0$;2.constant-noise LPN is $2^{\varOmega (n/\log n)}$-hard given $q=\mathsf {poly}(n)$ samples;3.low-noise LPN (of noise rate $1/\sqrt{n}$) is $2^{\varOmega (\sqrt{n}/\log n)}$-hard given $q=\mathsf {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 combining the best of the two worlds, namely, maximized (depth one) parallelizability and polynomial shrinkage. In particular, assume $2^{n^{0.5+\varepsilon }}$-hard constant-noise LPN or $2^{n^{0.25+\varepsilon }}$-hard low-noise LPN, we obtain a collision resistant hash function that evaluates in parallel only a single layer of small-domain random functions (or random permutations) and shrinks polynomially.
##### BibTeX
@article{asiacrypt-2019-30032,
title={Collision Resistant Hashing from Sub-exponential Learning Parity with Noise},
booktitle={Advances in Cryptology – ASIACRYPT 2019},
series={Advances in Cryptology – ASIACRYPT 2019},
publisher={Springer},
volume={11922},
pages={3-24},
doi={10.1007/978-3-030-34621-8_1},
author={Yu Yu and Jiang Zhang and Jian Weng and Chun Guo and Xiangxue Li},
year=2019
}