Time-Space Trade-Offs in Cryptographic Primitives

The research in complexity theory, for a long time now, has been conscious of memory as a resource in building algorithms with improved asymptotic complexity. There is an understanding to compare time-memory trade-offs as opposed to only running times while choosing between algorithms to solve any problem. While cryptographers have recognized memory to be a resource, there has been little effort to analyze cryptographic primitives in a memory-conscious manner until recently.\\ This work contributes towards the recent efforts of understanding the role of memory in the security of cryptographic primitives. Our study is two-fold: 1) How much better can any adversary that is capable of performing pre-computation and storing a bounded amount of information about the cryptographic primitive (under attack) do?2) Are there cryptographic applications which are provably more secure against adversaries with lesser memory? This work focuses on cryptographic hash functions for the first part of the study. The study analyzes properties of collision resistance and multi-way collision resistance for these functions.\\ For the second part of the study, the aim is to analyze double encryption against the memory-bounded non-adaptive adversaries. It is known that meet-in-the-middle (MITM) adversary against double encryption runs in aboutthe time required to brute force a single key, leading to the common-knowledge that double encryption is no more secure than the original block cipher. However, this is when the adversary is allowed to use as much memory as it would like. However, this is when the adversary is allowed to use as much memory as it would like