TY - GEN
T1 - Collision Resistant Hashing from Sub-exponential Learning Parity with Noise
AU - Yu, Yu
AU - Zhang, Jiang
AU - Weng, Jian
AU - Guo, Chun
AU - Li, Xiangxue
N1 - Publisher Copyright:
© 2019, International Association for Cryptologic Research.
PY - 2019
Y1 - 2019
N2 - 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 (formula presented)-hard for any constant (formula presented);2.constant-noise LPN is (formula presented)-hard given (formula presented) samples;3.low-noise LPN (of noise rate (formula presented) is (formula presented)-hard given (formula presented) 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 (formula presented) CRH is reminiscent of the known reductions for the large-modulus analogue, i.e., LWE (formula presented) SIS (formula presented) 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 (formula presented)-hard constant-noise LPN or (formula presented)-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.
AB - 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 (formula presented)-hard for any constant (formula presented);2.constant-noise LPN is (formula presented)-hard given (formula presented) samples;3.low-noise LPN (of noise rate (formula presented) is (formula presented)-hard given (formula presented) 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 (formula presented) CRH is reminiscent of the known reductions for the large-modulus analogue, i.e., LWE (formula presented) SIS (formula presented) 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 (formula presented)-hard constant-noise LPN or (formula presented)-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.
UR - https://www.scopus.com/pages/publications/85076969910
U2 - 10.1007/978-3-030-34621-8_1
DO - 10.1007/978-3-030-34621-8_1
M3 - 会议稿件
AN - SCOPUS:85076969910
SN - 9783030346201
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 3
EP - 24
BT - Advances in Cryptology – ASIACRYPT 2019 - 25th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
A2 - Galbraith, Steven D.
A2 - Moriai, Shiho
PB - Springer Science and Business Media Deutschland GmbH
T2 - 25th Annual International Conference on the Theory and Applications of Cryptology and Information Security, ASIACRYPT 2019
Y2 - 8 December 2019 through 12 December 2019
ER -