Hash Functions and Their Many Uses in Cryptography

Hash functions have many uses in cryptography, from encryption through authentication and signatures to key exchange. In this talk I'll cover an assortment of aspects of hash functions.

In many applications, "what we really want" is a truly random function (a.k.a. a random oracle), but we settle for a hash function instead. I will explain the difference between the two and show some consequences of this difference.

Different applications require different security properties from the underlying hash functions. I will survey a few of these properties, make the case that applications should be designed to rely on security properties as weak as possible, and illustrate it with example applications to message authentication and digital signatures.

Most hash functions are constructed from lower-level primitives called compression functions. I will briefly describe this type of design and point out some advantages and drawbacks.

Finally, I will illustrate the design of a modern hash function using Fugue, which is a candidate for the NIST SHA3 competition. More than most hash functions, Fugue was designed to be amenable to rigorous security analysis.