# 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.

• In Perfectly one-way probabilistic hash functions (STOC 1998), D. Micciancio, and collaborators R. Canetti and O. Reingold,

propose various kinds of hash functions that hide all partial information about the input. The hiding property is achieved using randomization, so that if H is applied to the same input multiple times, it can return different values at every application.

### 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.

• In A new paradigm for collision-free hashing: Incrementality at reduced cost (Eurocrypt 1997), D. Micciancio and collaborator M. Bellare, propose several practical instantiations of incremental hash functions. Some proposal are extremely efficient, requiring only a handfull of arithmetic operations each time the value to be hashed is modified. The hash functions considered support block replacement operations, are are proved secure in the random oracle model, based on various standard intractability assumptions.

### 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.