Authors:

Michael Hicks (UMD), Andrew Miller (UCF), Jon Katz (UMD), and Elaine
Shi (UMD). 

Title: 

Authenticated Data structures, Generically

Abstract:

An authenticated data structure (ADS) is a data structure whose
operations can be carried out by an untrusted server, the results of
which a client can efficiently verify as authentic. This is normally
done by having the server produce a compact "verification object"
along with a query result that the client uses to check the
result. ADSs thus support outsourcing data maintenance and processing
tasks to untrusted servers without loss of authenticity. Past work on
ADSs has focused on developing particular data structures, or limited
classes of data structures, one at a time, often with support only for
particular operations, e.g., particular types of queries. In this
short talk I will present work-in-progress on a method that manifests
as a small extension to a ML-like functional programming language and
which supports general-purpose authenticated computation. We can
support authenticated operations over data structures constructed from
standard type constructors, including recursive types, sums, products,
base types, and polymorphic types, programmed using standard language
constructs. Using our approach, one can trivially produce
authenticated versions of many interesting data structures, including
binary search trees, red-black trees, and skip lists; we are working
on developing recursive separator tree for a planar graph, to support
efficient (authenticated) shortest path queries.