Cryptology ePrint Archive: Report 1997/001
A New Paradigm for Collision-free Hashing: Incrementality at Reduced Cost
Mihir Bellare and Daniele Micciancio
Abstract: We present a simple, new paradigm for the design of collision-free hash
functions. Any function emanating from this paradigm is <i>incremental.</i>
(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'.) Also any function
emanating from this paradigm is parallelizable, useful for hardware
Category / Keywords: Incremental cryptography, hash functions, collision-resistance, discrete logarithms.
Publication Info: Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Date: received February 26th, 1997.
Contact author: mihir at cs ucsd edu
Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]