Incremental Cryptography
The goal of incremental cryptography is the design of 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. Incremental cryptography offers considerable advantages in all settings where similar documents are processed by the same cryptographic transformation. For example if you want to send signed copies of the same letter to several people just changing in each letter the name of the recepient, instead of signing each copy from scratch, you can sign only one letter and then obtain the other signatures by fast update operations. Incrementality can be defined for all cryptographic primitives: digital signatures, encryption, hashing, authentication.
- The notion of incremental cryptography has been introduced by CIS members Oded Golreich, Shafi Goldwasser and Mihir Bellare from UCSD in the papers [BGG94] and [BGG95].
- In [Mi97] CIS member Daniele Micciancio explores issues like privacy in the presence of incremental operations. Specifically, he defines Oblivious Tree, a data structure that hides the sequence of operations that has been applied to it, and uses this data structure to design an incremental digital signature algorithm achieving privacy. Slides on this work are avaliable online.
- CIS member Daniele Micciancio and Mihir Bellare from UCSD introduced a new paradigm for efficient incremental hashing in the paper [BM97] where various fast collision-free hash functions are derived from the paradigm. Slides on this work are available online.
- Shafi Goldwasser, Yoav Yerushalmi, and Grant Emery have been working on various implementations of incremental cryptography. Right now work is underway on an incremental signature editor (which generates valid signatures for documents while they are editted). This builds on work already done with an editor that generates Message Authentication Codes (MAC) for documents. This is closely tied into Emacs (a popular text editor in the UNIX world).