Incremental Cryptography: The Case of Hashing and Signing

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.