Efficient authenticated data structures for graph connectivity and geometric search problems

DOI10.1007/S00453-009-9355-7zbMATH Open1218.68081arXiv0908.4116OpenAlexW2148473959MaRDI QIDQ548654FDOQ548654

Authors: Michael T. Goodrich, Roberto Tamassia, Nikos Triandopoulos 

Publication date: 30 June 2011

Published in: Algorithmica (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0908.4116

Recommendations

• scientific article; zbMATH DE number 1962158
• A general model for authenticated data structures
• Authenticated data structures, generically
• Authenticated hash tables based on cryptographic accumulators
• Time and Space Efficient Algorithms for Two-Party Authenticated Data Structures

zbMATH Keywords

authenticated data structuresgraph connectivitydata authenticationgeometric searchinginformation integrity

Mathematics Subject Classification ID

Cryptography (94A60) Data structures (68P05) Connectivity (05C40) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Cites Work

• Title not available (Why is that?)
• A data structure for dynamic trees
• A general model for authenticated data structures
• Authenticated hash tables based on cryptographic accumulators
• Universal Accumulators with Efficient Nonmembership Proofs
• Efficient Content Authentication in Peer-to-Peer Networks
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Time and Space Efficient Algorithms for Two-Party Authenticated Data Structures
• Super-Efficient Verification of Dynamic Outsourced Databases
• Topics in Cryptology – CT-RSA 2005
• Automata, Languages and Programming
• Data and Applications Security XIX
• A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks
• Maintenance of a minimum spanning forest in a dynamic plane graph
• Designing programs that check their work
• Certification of computational results
• Dynamic fractional cascading
• Biased Search Trees
• Fractional cascading. I: A data structuring technique
• Title not available (Why is that?)
• On-line maintenance of triconnected components with SPQR-trees
• Title not available (Why is that?)
• Checking the convexity of polytopes and the planarity of subdivisions
• Checking geometric programs or verification of geometric structures
• Title not available (Why is that?)
• Fractional cascading. II: Applications
• Maintaining bridge-connected and biconnected components on-line
• Authentic third-party data publication
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Automata, Languages and Programming

Cited In (3)

• Title not available (Why is that?)
• Authenticated hash tables based on cryptographic accumulators
• A general model for authenticated data structures

Uses Software

• LEDA

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)