Efficient authenticated data structures for graph connectivity and geometric search problems

DOI10.1007/s00453-009-9355-7zbMath1218.68081arXiv0908.4116OpenAlexW2148473959MaRDI QIDQ548654

Roberto Tamassia, Michael T. Goodrich, Nikos Triandopoulos

Publication date: 30 June 2011

Published in: Algorithmica (Search for Journal in Brave)

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

zbMATH Keywords

graph connectivityauthenticated data structuresdata authenticationgeometric searchinginformation integrity

Mathematics Subject Classification ID

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

Related Items

Authenticated hash tables based on cryptographic accumulators

Uses Software

• LEDA

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Authenticated hash tables based on cryptographic accumulators
• Dynamic fractional cascading
• Fractional cascading. I: A data structuring technique
• Fractional cascading. II: Applications
• Maintaining bridge-connected and biconnected components on-line
• Checking the convexity of polytopes and the planarity of subdivisions
• Checking geometric programs or verification of geometric structures
• A data structure for dynamic trees
• A general model for authenticated data structures
• On-line maintenance of triconnected components with SPQR-trees
• Universal Accumulators with Efficient Nonmembership Proofs
• Efficient Content Authentication in Peer-to-Peer Networks
• Biased Search Trees
• 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
• Time and Space Efficient Algorithms for Two-Party Authenticated Data Structures
• Super-Efficient Verification of Dynamic Outsourced Databases
• Automata, Languages and Programming
• Topics in Cryptology – CT-RSA 2005
• Automata, Languages and Programming
• Data and Applications Security XIX