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

### Papers

In our Crypto94 paper
[see PDF],
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
[see PDF],
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.

### Errata (re Thm 3.1 in STOC95)

As pointed out by Damien Vergnaud and Louiza Khati (in April 2018),
the original scheme as described is Sec 3.2 can be broken by
(making a signing query and) presenting a forged signature
that uses the same randomization in several blocks.
While the same randomization is indeed unlikely to occur in signatures
signed by the legitimate signer, such signatures were not deemed invalid.
One possible fix is to indeed disallow such signatures
(in which the same randomization occurs in different blocks),
which introduces a probability of error in the case of legitimate operation.
Actually, one can replace the block-randomization by augmenting
the blocks by any sequence of different values;
this can be implemented by using consecutive values
when creating a new signature from scratch, and making sure
that the last block is augmented by the largest value.
This invariant can be maintained by increamenting the
value used in the last block when inserting a new block
which is augmented with the previous value of the last block.
(When deleting a block, the value used in the last block remains intact,
except in the case that the last block is deleted, in which case
we update the value used in the block preceeding it.)

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