CS 269S, Spring 2012: Theory Seminar
Bren Hall, Room 1420
May 18, 2012:

Authenticated Data Structures for Graph and Geometric Searching

Lowell Trott

Authenticated data structures provide cryptographic proofs that their answers are as accurate as the author intended, even if the data structure is maintained by a remote host. We present techniques for authenticating data structures that represent graphs and collections of geometric objects. In our model, a data structure maintained by a trusted source is mirrored at distributed directories that answer queries and provide proof of correctness. Our work has applications to the authentication of network management systems and geographic information systems.

(Based on a paper by Michael T. Goodrich, Roberto Tamassia, Nikos Triandopoulos, and Robert Cohen in RSA 2003.)