**Author:** Daniele Micciancio

Proceedings of the 29th Annual ACM Symposium on Theory of Computing - STOC 1997. May 4-6, El Paso, Texas. pp. 456-464.

**Abstract:** We introduce the notion of oblivious data
structure, motivated by the use of data structures in cryptography.
Informally, an oblivious data structure yields no knowledge about the
sequence of operations that have been applied to it other than the final
result of the operations. In particular we define Oblivious Tree, a data
structure very similar to 2-3 Tree, but with the additional property that the
only information conveyed by an Oblivious Tree is the set of values stored at
its leaves. This property is achieved through the use of randomization by the
update algorithms. We use the Oblivious Tree data structure to solve the
*privacy* problem for incremental digital signatures raised by
Bellare, Goldreich and Goldwasser. An incremental signing algorithm is
*private* if the digital signature it outputs does not give any
information on the sequence of edit operations that have been applied to
produce the final document. We show how the incremental signature scheme of
Bellare, Goldreich and Goldwasser can be made achieve privacy using Oblivious
Trees instead of 2-3 Trees.