Efficient Data Authentication in Distributed Environments
Wednesday October 8, 2008, 1:15 pm in 111 Cummington Street, Room 135
Abstract: We consider the problem of authenticating data and the correctness of associated operations in untrusted or adversarial computing
environments: When data is managed by an untrusted third party, and not by the source that produced it, how can data received be proven authentic and operations on data be validated?
In this talk, we focus on the design of protocols that allow the secure and efficient authentication of the integrity of a dynamic data set that is hosted by an untrusted server, and that also support the correctness verification of operations remotely performed on the data. We describe a framework for authenticating general queries on structured data sets which advances the state of the art in many ways. By decoupling the answer-verification process from the data-querying process, and by reducing complex queries to simple membership queries, our method enables the use of existing or new algorithmic and cryptographic constructions that offer stronger security, achieve better performance and cover wider application areas, overall providing general data-authentication tools. We show how our framework can be applied to the efficient verification of operations on a database or file system that is outsourced to a remote untrusted server, ensuring that the database or the file system is fully consistent with the exact history of updates and queries requested at the server. We conclude with some interesting research directions.