The Taub Faculty of Computer Science Events and Talks

Cryptographic hash functions are the basis of many important and far reaching results in cryptography, complexity theory, and beyond. In particular, hash functions are the primary building block of fundamental applications like digital signatures and verifiable computation, and they are the tool underlying the proofs-of-work which drive blockchains. Because of the central role of cryptographic hash functions in both theory and practice, it is crucial to understand their security guarantees, toward basing applications on the minimal possible notion of security. Indeed, there are many ways to formalize the security requirement of a hash function; each way is sufficient for different applications. Also, there are many candidate hash functions, offering various trade-offs between security, efficiency, and other desirable properties. In this talk, I will present an application [Komargodski-Naor-Yogev, FOCS 2017] of a relatively weak notion of hashing (collision resistance) that goes well beyond cryptography into a fundamental problem in the intersection of complexity theory and combinatorics -- the Ramsey problem. This will lead us to new emerging aspects of hash functions, including relaxed security notions and their applications, addressing a recent attack on SHA-1. I will conclude with several exciting open problems and challenges.