The incremental cryptography papers

Incremental cryptography is a way to speed up the computation of cryptographic functions (eg. signatures, hash functions, MACs) in certain settings. The idea is that if we have already computed the function on some document, and this document is modified, then we update the function value based on the old value rather than re-computing it from scratch. The idea was introduced by Bellare, Goldreich and Goldwasser in the papers Incremental cryptography: the case of hashing and signing and Incremental cryptography with application to virus protection. More efficient solutions for hashing were found in A new paradigm for collision-free hashing: Incrementality at reduced cost.


Incremental cryptography: the case of hashing and signing

Authors: M. Bellare, O. Goldreich and S. Goldwasser

Abstract: We initiate the investigation of a new kind of efficiency for cryptographic transformations. The idea is that having once applied the transformation to some document M, the time to update the result upon modification of M should be ``proportional'' to the ``amount of modification'' done to M. Thereby one obtains much faster cryptographic primitives for environments where closely related documents are undergoing the same cryptographic transformations.

We provide some basic definitions enabling treatment of the new notion. We then exemplify our approach by suggesting incremental schemes for hashing and signing which are efficient according to our new measure.

Ref: Extended abstract in Advances in Cryptology - Crypto 94 Proceedings, Lecture Notes in Computer Science Vol. 839, Y. Desmedt ed, Springer-Verlag, 1994. Full paper available below.

Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).


Incremental cryptography with application to virus protection

Authors: M. Bellare, O. Goldreich and S. Goldwasser

Abstract: The goal of incremental cryptography is to design cryptographic algorithms with the property that having applied the algorithm to a document, it is possible to quickly update the result of the algorithm for a modified document, rather than having to re-compute it from scratch. In settings where cryptographic algorithms such as encryption or signatures are frequently applied to changing documents, dramatic efficiency improvements can be achieved. One such setting is the use of authentication tags for virus protection.

We consider documents that can be modified by powerful (and realistic) document modification operations such as insertion and deletion of character-strings (or equivalently cut and paste of text). We provide efficient incremental signature and message authentication schemes supporting the above document modification operations. They meet a strong notion of tamper-proof security which is appropriate for the virus protection setting. We initiate a study of incremental encryption, providing definitions as well as solutions. Finally, we raise the novel issue of ``privacy'' of incremental authentication schemes.

Ref: Extended abstract in Proc. 27th Annual Symposium on the Theory of Computing, ACM, 1995. Available below.

Best available version: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).


A New Paradigm for collision-free hashing: Incrementality at reduced cost

Authors: M. Bellare and D. Micciancio

Abstract: We present a simple, new paradigm for the design of collision-free hash functions. Any function emanating from this paradigm 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'.) Also any function emanating from this paradigm is 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. 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, with security 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.

Ref: Extended abstract was in Advances in Cryptology- Eurocrypt 97 Proceedings, Lecture Notes in Computer Science Vol. 1233, W. Fumy ed, Springer-Verlag, 1997. Full paper available below.

Full paper: Available as compressed postscript, postscript, or pdf. ( Help if this doesn't work).


Related work