Article ID: | iaor20114259 |
Volume: | 60 |
Issue: | 3 |
Start Page Number: | 505 |
End Page Number: | 552 |
Publication Date: | Jul 2011 |
Journal: | Algorithmica |
Authors: | Goodrich T, Tamassia Roberto, Triandopoulos Nikos |
Keywords: | data models, cryptography |
Following in the spirit of data structure and algorithm correctness checking, authenticated data structures provide cryptographic proofs that their answers are as accurate as the author intended, even if the data structure is being controlled by a remote untrusted host. In this paper we present efficient techniques for authenticating data structures that represent graphs and collections of geometric objects. We use a data‐querying model where a data structure maintained by a trusted source is mirrored at distributed untrusted servers, called responders, with the responders answering queries made by users: when a user queries a responder, along with the answer to the issued query, he receives a cryptographic proof that allows the verification of the answer trusting only a short statement (digest) signed by the source. We introduce the