caa a22 4500 445804416 CHVBK 20180317145152.0 cr unu---uuuuu 170323e20110701xx s 000 0 eng 10.1007/s00453-009-9355-7 doi (NATIONALLICENCE)springer-10.1007/s00453-009-9355-7 Efficient Authenticated Data Structures for Graph Connectivity and Geometric Search Problems [Elektronische Daten] [Michael Goodrich, Roberto Tamassia, Nikos Triandopoulos] 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 path hash accumulator, a new primitive based on cryptographic hashing for efficiently authenticating various properties of structured data represented as paths, including any decomposable query over sequences of elements. We show how to employ our primitive to authenticate queries about properties of paths in graphs and search queries on multi-catalogs. This allows the design of new, efficient authenticated data structures for fundamental problems on networks, such as path and connectivity queries over graphs, and complex queries on two-dimensional geometric objects, such as intersection and containment queries. By building on our new primitive we achieve efficiency and modularity: our schemes can be easily analyzed in terms of complexity and security and are simple to implement. Our work has applications to the authentication of network management systems and geographic information systems. Springer Science+Business Media, LLC, 2009 Authenticated data structures nationallicence Data authentication nationallicence Information integrity nationallicence Graph connectivity nationallicence Geometric searching nationallicence Goodrich Michael Department of Computer Science, University of California, 92697, Irvine, CA, USA aut Tamassia Roberto Department of Computer Science, Brown University, 02912, Providence, RI, USA aut Triandopoulos Nikos Department of Computer Science, Boston University, 02215, Boston, MA, USA aut Algorithmica Springer-Verlag 60/3(2011-07-01), 505-552 0178-4617 60:3<505 2011 60 453 https://doi.org/10.1007/s00453-009-9355-7 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-009-9355-7 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Goodrich Michael Department of Computer Science, University of California, 92697, Irvine, CA, USA aut NATIONALLICENCE 700 1- Tamassia Roberto Department of Computer Science, Brown University, 02912, Providence, RI, USA aut NATIONALLICENCE 700 1- Triandopoulos Nikos Department of Computer Science, Boston University, 02215, Boston, MA, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 60/3(2011-07-01), 505-552 0178-4617 60:3<505 2011 60 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer