Authenticated Index Structures for Aggregation Queries

by Feifei Li, Marios Hadjieleftheriou, George Kollios, and Leonid Reyzin

Query authentication is an essential component in outsourced database (ODB) systems. This article introduces efficient index structures for authenticating aggregation queries over large data sets. First, we design an index that features good performance characteristics for static environments. Then, we propose more involved structures for the dynamic case. Our structures feature excellent performance for authenticating queries with multiple aggregate attributes and multiple selection predicates. Furthermore, our techniques cover a large number of aggregate types, including distributive aggregates (such as SUM, COUNT, MIN and MAX), algebraic aggregates (such as the AVG), and holistic aggregates (such as MEDIAN and QUANTILE). We have also addressed the issue of authenticating aggregation queries efficiently when the database is encrypted to protect data confidentiality. Finally, we implemented a working prototype of the proposed techniques and experimentally validated the effectiveness and efficiency of our methods.

Note: an implemenation of some of the algorithms in this paper is available on the project website. You may also want to see our related SIGMOD 2006 paper that addresses simpler query types.

ACM Transactions on Information and System Security, to appear.