Cryptography and Information Security Group Research
Project: 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).