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.