Incremental Cryptography

by Mihir Bellare, Oded Goldreich and Shafi Goldwasser

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.


In our Crypto94 paper, the notion of incremental cryptography was introduced and applied in the context of Hashing and Signing and with respect to character replacement operations.

In our STOC95 paper, we widen the scope of investigation: In particular, we considered stonger document modification operations and provided efficient incremental signature and message authentication schemes supporting these document modification operations. These schemes meet a strong notion of tamper-proof security which is appropriate for the virus protection setting. We initiated a study of incremental encryption, providing definitions as well as solutions. Finally, we raised the issue of ``privacy'' of incremental authentication schemes.

Highly Recommended Link

See Daniele Micciancio's page on Incremental Cryptography.

Back to Oded Goldreich's homepage or to General list of Oded Goldreich's papers