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

**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 *x*to 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.