Project: Cryptographic Hash Functions

A cryptographic hash function is a function H that on input a (long) document x, produces a short digest H(x). The most fundamental property of hash functions, used in many applications, is collision resistance: it should be hard to find two input values x,y such that H(x) = H(y). Some applications may require additional properties. This projects explores various kinds of cryptographic hash with additional properties:

Probabilistic hash functions

A typical application of hash functions is comparing large documents. Instead of comparing x and y directly, one can compare H(x) = H(y). Since it is computationally hard to find distinct strings x,y with the same hash, if H(x)=H(y) then almost certainly x=y.

One step forward, the hash value H(x) can be given out as a short “signature” that allows to determine if the value x (e.g., the solution to a puzzle, or a homework assignment) has been found. In this kind of applications, it is important that the hash value H(x) does not make the problem of finding x any easier. We need “perfect” hash functions that hide all information about x, but still allow to check for equality.

Incremental hashing

Another very useful property is incrementality. In many applications where the hash H(x) of some string x is requires, the hash value of some related string H(x’) is already known. This is the case, for example, if we are editing x, while computing the hash value H(x) on the fly, or if we want to compute the hash value of several related documents, e.g., letters written according to a template.

Lattice based hashing

In addition, Micciancio has worked the construction of provably secure collision resistant hash functions, based on the worst-case intractability of computational problems on point lattices. See the Lattice based Cryptography project page for details.