Time-Space Tradeoffs for Collisions in Hash Functions
Cryptographic hash functions are functions that take arbitrary length inputs and output fixed length digest. They are one of the most important cryptographic primitives and widely used in applications today. Apart from the compression requirement, the applications using these functions could need additional properties to be provably secure. One such, perhaps the most important property is collision resistance.
This property has been well studied for uniform adversaries. However, uniform adversaries fail to capture many real-world adversaries. Hence, several recent works have studied the collision resistance property for non-uniform adversaries. Analyzing non-uniform adversaries presents several challenges. That is why Dodis et al in their EUROCRYPT 18 paper presented a reduction to another (easier to analyze) model named Bit-fixing model.
In our CRYPTO 20 paper, we showed that adversaries in this Bit-fixing model are too strong when the length of the collisions are bounded. We also showed a reduction to the Multi-instance model, which helped us obtain better results for restricted parameter ranges. In our recent CRYPTO 22 paper, we further explored the relation between the Bit-fixing model and the Multi-instance model and further improved the results with our new findings.
The talk will include some preliminary definitions, detailed description of these models, results and a high level idea of the techniques from all the relevant works.
Speaker Biography
Dr. Akshima is currently a Postdoctoral fellow at NYU Shanghai. She has completed her PhD from University of Chicago in 2022. Prior to this, she was a researcher at Rutgers university from 2016 to 2018. She completed her bachelors degree from IIIT Delhi in 2016.
Her homepage is: https://sites.google.com/view/akshima-
Her research primarily focuses on studying the security of cryptographic primitives. More precisely, her work focuses on understanding the role of memory in the security of cryptographic primitives. As part of her thesis, she has studied non-uniform algorithms against popular security properties of hash functions. The objective was to understand how much better can any algorithm that is capable of performing pre-computation and storing a bounded amount of information about the cryptographic primitive (under attack) do? On the flip side, she is interested in the question whether some cryptographic applications can be provably more secure against adversaries with lesser memory? Apart from that she has been interested in Searchable encryption. In addition, she is also working on automation of formal verification techniques for compression based proofs.
