Traditional methods for data authentication, based on individually signed statements, are unsuitable for large collections of dynamically evolving data. Authenticated data structures are a model of computation where untrusted responders answer queries on a data structure on behalf of a trusted source and provide a proof of the validity of the answer to the user. We present techniques for designing authenticated data structures and we provide lower bounds on the efficiency of authenticated data structures based on a hierarchical hashing scheme.

Prof. Tamassia at Brown University