Low-Complexity Cryptographic Hash Functions
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 effi...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137816 |
| _version_ | 1811073942456107008 |
|---|---|
| author | Applebaum, Benny Haramaty-Krasne, Naama Ishai, Yuval Kushilevitz, Eyal Vaikuntananthan, Vinod |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Applebaum, Benny Haramaty-Krasne, Naama Ishai, Yuval Kushilevitz, Eyal Vaikuntananthan, Vinod |
| author_sort | Applebaum, Benny |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T09:40:35Z |
| format | Article |
| id | mit-1721.1/137816 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T09:40:35Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1378162023-07-19T16:02:01Z Low-Complexity Cryptographic Hash Functions Applebaum, Benny Haramaty-Krasne, Naama Ishai, Yuval Kushilevitz, Eyal Vaikuntananthan, Vinod Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory 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. 2021-11-08T20:21:32Z 2021-11-08T20:21:32Z 2017 2019-07-09T16:36:41Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137816 Applebaum, Benny, Haramaty-Krasne, Naama, Ishai, Yuval, Kushilevitz, Eyal and Vaikuntananthan, Vinod. 2017. "Low-Complexity Cryptographic Hash Functions." en 10.4230/LIPIcs.ITCS.2017.7 Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf DROPS |
| spellingShingle | Applebaum, Benny Haramaty-Krasne, Naama Ishai, Yuval Kushilevitz, Eyal Vaikuntananthan, Vinod Low-Complexity Cryptographic Hash Functions |
| title | Low-Complexity Cryptographic Hash Functions |
| title_full | Low-Complexity Cryptographic Hash Functions |
| title_fullStr | Low-Complexity Cryptographic Hash Functions |
| title_full_unstemmed | Low-Complexity Cryptographic Hash Functions |
| title_short | Low-Complexity Cryptographic Hash Functions |
| title_sort | low complexity cryptographic hash functions |
| url | https://hdl.handle.net/1721.1/137816 |
| work_keys_str_mv | AT applebaumbenny lowcomplexitycryptographichashfunctions AT haramatykrasnenaama lowcomplexitycryptographichashfunctions AT ishaiyuval lowcomplexitycryptographichashfunctions AT kushilevitzeyal lowcomplexitycryptographichashfunctions AT vaikuntananthanvinod lowcomplexitycryptographichashfunctions |