|M.Sc Student||Haramaty Krasne Naama|
|Subject||Low-Complexity Cryptographic Hash Functions|
|Department||Department of Computer Science||Supervisors||Professor Eyal Kushilevitz|
|Professor Yuval Ishai|
|Full Thesis text|
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: