Efficient authenticated data structures for graph connectivity and geometric search problems
From MaRDI portal
Abstract: 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. We present efficient techniques for authenticating data structures that represent graphs and collections of geometric objects. 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.
Recommendations
Cites work
- scientific article; zbMATH DE number 3936534 (Why is no real title available?)
- scientific article; zbMATH DE number 1302843 (Why is no real title available?)
- scientific article; zbMATH DE number 1305509 (Why is no real title available?)
- scientific article; zbMATH DE number 1941253 (Why is no real title available?)
- scientific article; zbMATH DE number 1942413 (Why is no real title available?)
- scientific article; zbMATH DE number 1962158 (Why is no real title available?)
- scientific article; zbMATH DE number 2044545 (Why is no real title available?)
- scientific article; zbMATH DE number 1368469 (Why is no real title available?)
- scientific article; zbMATH DE number 1394309 (Why is no real title available?)
- scientific article; zbMATH DE number 1440067 (Why is no real title available?)
- A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks
- A data structure for dynamic trees
- A general model for authenticated data structures
- Authentic third-party data publication
- Authenticated hash tables based on cryptographic accumulators
- Automata, Languages and Programming
- Automata, Languages and Programming
- Biased Search Trees
- Certification of computational results
- Checking geometric programs or verification of geometric structures
- Checking the convexity of polytopes and the planarity of subdivisions
- Data and Applications Security XIX
- Designing programs that check their work
- Dynamic fractional cascading
- Efficient Content Authentication in Peer-to-Peer Networks
- Fractional cascading. I: A data structuring technique
- Fractional cascading. II: Applications
- Maintaining bridge-connected and biconnected components on-line
- Maintenance of a minimum spanning forest in a dynamic plane graph
- On-line maintenance of triconnected components with SPQR-trees
- Super-Efficient Verification of Dynamic Outsourced Databases
- Time and Space Efficient Algorithms for Two-Party Authenticated Data Structures
- Topics in Cryptology – CT-RSA 2005
- Universal Accumulators with Efficient Nonmembership Proofs
Cited in
(4)
This page was built for publication: Efficient authenticated data structures for graph connectivity and geometric search problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q548654)
