A new paradigm for collision-free hashing: Incrementality at reduced cost

Authors: Mihir Bellare and Daniele Micciancio

Advances in Cryptology - Eurocrypt 1997, volume 1233 of Lecture Notes in Computer Science, pages 163--192. Springer-Verlag, 11--15 May 1997.

[BibTeX] [PostScript] [PDF]

Abstract: We present a simple, new paradigm for the design of collision-free hash functions. A key feature of this paradigm is that any function emanating from it is incremental. This means that if a message x which I have previously hashed is modified to x' then rather than having to re-compute the hash of x'from scratch, I can quickly ``update'' the old hash value to the new one, in time proportional to the amount of modification made in xto get x'. Another property of any function emanating from this paradigm is to be parallelizable, useful for hardware implementation. We derive several specific functions from our paradigm. All use a standard hash function, assumed ideal, and some algebraic operations. The first function, MuHASH, uses one modular multiplication per block of the message, making it reasonably efficient, and significantly faster than previous incremental hash functions. Moreover its security is proven, based on the hardness of the discrete logarithm problem. A second function, AdHASH, is even faster, using additions instead of multiplications. Its security too is proven, given either that approximation of the length of shortest lattice vectors is hard or that the weighted subset sum problem is hard. A third function, LtHASH, is a practical variant of recent lattice based functions, with security proven based, again on the hardness of shortest lattice vector approximation.