TY - GEN

T1 - Low-complexity cryptographic hash functions

AU - Applebaum, Benny

AU - Haramaty-Krasne, Naama

AU - Ishai, Yuval

AU - Kushilevitz, Eyal

AU - Vaikuntanathan, Vinod

N1 - Funding Information: ∗ This work was done in part while the authors were visiting the Simons Institute for the Theory of Computing, supported by the Simons Foundation and by the DIMACS/Simons Collaboration in Cryptography through NSF grant CNS-1523467. † The first author was partially supported by the European Union’s Horizon 2020 Programme (ERC-StG-2014-2020) under grant agreement no. 639813 ERC-CLC, by an ICRC grant and by the Check Point Institute for Information Security. The second author was partially supported by a Melvin R. Berlin Fellowship in the Cyber Security Research Program. The second and third authors were partially supported by ERC starting grant 259426. The second, third and fourth authors were partially supported by ISF grant 1709/14, BSF grant 2012378, and NSF-BSF grant 2015782. The third author was additionally supported by a DARPA/ARL SAFEWARE award, NSF Frontier Award 1413955, NSF grants 1228984, 1136174, 1118096, and 1065276, and DARPA through the ARL under Contract W911NF-15-C-0205. The fifth author was partially supported by NSF Grants CNS-1350619 and CNS-1414119, Alfred P. Sloan Research Fellowship, Microsoft Faculty Fellowship, the NEC Corporation, a Steven and Renee Finn Career Development Chair from MIT, and DARPA and U.S. Army Research Office under contracts W911NF-15-C-0226. The views expressed are those of the authors and do not reflect the official policy or position of the Department of Defense, the National Science Foundation, or the U.S. Government.

PY - 2017/11/1

Y1 - 2017/11/1

N2 - Cryptographic hash functions are efficiently computable functions that shrink a long input into a shorter output while achieving some of the useful security properties of a random function. The most common type of such hash functions is collision resistant hash functions (CRH), which prevent an efficient attacker from finding a pair of inputs on which the function has the same output. Despite the ubiquitous role of hash functions in cryptography, several of the most basic questions regarding their computational and algebraic complexity remained open. In this work we settle most of these questions under new, but arguably quite conservative, cryptographic assumptions, whose study may be of independent interest. Concretely, we obtain the following results: Low-complexity CRH. Assuming the intractability of finding short codewords in natural families of linear error-correcting codes, there are CRH that shrink the input by a constant factor and have a constant algebraic degree over Z2 (as low as 3), or even constant output locality and input locality. Alternatively, CRH with an arbitrary polynomial shrinkage can be computed by linear-size circuits. Win-win results. If low-degree CRH with good shrinkage do not exist, this has useful consequences for learning algorithms and data structures. Degree-2 hash functions. Assuming the conjectured intractability of solving a random system of quadratic equations over ℤ2, a uniformly random degree-2 mapping is a universal one-way hash function (UOWHF). UOWHF relaxes CRH by forcing the attacker to find a collision with a random input picked by a challenger. On the other hand, a uniformly random degree-2 mapping is not a CRH. We leave the existence of degree-2 CRH open, and relate it to open questions on the existence of degree-2 randomized encodings of functions.

AB - Cryptographic hash functions are efficiently computable functions that shrink a long input into a shorter output while achieving some of the useful security properties of a random function. The most common type of such hash functions is collision resistant hash functions (CRH), which prevent an efficient attacker from finding a pair of inputs on which the function has the same output. Despite the ubiquitous role of hash functions in cryptography, several of the most basic questions regarding their computational and algebraic complexity remained open. In this work we settle most of these questions under new, but arguably quite conservative, cryptographic assumptions, whose study may be of independent interest. Concretely, we obtain the following results: Low-complexity CRH. Assuming the intractability of finding short codewords in natural families of linear error-correcting codes, there are CRH that shrink the input by a constant factor and have a constant algebraic degree over Z2 (as low as 3), or even constant output locality and input locality. Alternatively, CRH with an arbitrary polynomial shrinkage can be computed by linear-size circuits. Win-win results. If low-degree CRH with good shrinkage do not exist, this has useful consequences for learning algorithms and data structures. Degree-2 hash functions. Assuming the conjectured intractability of solving a random system of quadratic equations over ℤ2, a uniformly random degree-2 mapping is a universal one-way hash function (UOWHF). UOWHF relaxes CRH by forcing the attacker to find a collision with a random input picked by a challenger. On the other hand, a uniformly random degree-2 mapping is not a CRH. We leave the existence of degree-2 CRH open, and relate it to open questions on the existence of degree-2 randomized encodings of functions.

KW - Coding theory

KW - Complexity theory

KW - Cryptography

KW - Hash functions

UR - http://www.scopus.com/inward/record.url?scp=85038584493&partnerID=8YFLogxK

U2 - https://doi.org/10.4230/LIPIcs.ITCS.2017.7

DO - https://doi.org/10.4230/LIPIcs.ITCS.2017.7

M3 - منشور من مؤتمر

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 8th Innovations in Theoretical Computer Science Conference, ITCS 2017

A2 - Papadimitriou, Christos H.

T2 - 8th Innovations in Theoretical Computer Science Conference, ITCS 2017

Y2 - 9 January 2017 through 11 January 2017

ER -