Paper 2017/036
LowComplexity Cryptographic Hash Functions
Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz, and Vinod Vaikuntanathan
Abstract
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 {\em 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: (1) Lowcomplexity CRH. Assuming the intractability of finding short codewords in natural families of linear errorcorrecting codes, there are CRH that shrink the input by a constant factor and have a {\em constant algebraic degree} over $Z_2$ (as low as 3), or even {\em constant output locality and input locality}. Alternatively, CRH with an arbitrary polynomial shrinkage can be computed by {\em linearsize} circuits. (2) Winwin results. If lowdegree CRH with good shrinkage {\em do not} exist, this has useful consequences for learning algorithms and data structures. (3) Degree2 hash functions. Assuming the conjectured intractability of solving a random system of quadratic equations over $Z_2$, a uniformly random degree2 mapping is a {\em universal oneway 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 degree2 mapping is {\em not} a CRH. We leave the existence of degree2 CRH open, and relate it to open questions on the existence of degree2 randomized encodings of functions.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Minor revision. The 8th Innovations in Theoretical Computer Science (ITCS)
 Keywords
 collision resistant hashingcryptography with low complexity
 Contact author(s)
 benny applebaum @ gmail com
 History
 20170114: received
 Short URL
 https://ia.cr/2017/036
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/036, author = {Benny Applebaum and Naama Haramaty and Yuval Ishai and Eyal Kushilevitz and Vinod Vaikuntanathan}, title = {LowComplexity Cryptographic Hash Functions}, howpublished = {Cryptology ePrint Archive, Paper 2017/036}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/036}}, url = {https://eprint.iacr.org/2017/036} }