Technical Reports
HPL-2009-119
Click here for full text:
Privacy-Preserving Computation and Verification of Aggregate Queries on Outsourced Databases
Thompson, Brian; Haber, Stuart; Horne, William G.; Sander, Tomas; Yao, Danfeng
HP Laboratories
HPL-2009-119
Keyword(s): aggregate query, outsource, privacy, integrity, secret sharing, verification
Abstract: Outsourced databases provide a solution for data owners who want to delegate the task of answering database queries to third-party service providers. However, distrustful users may desire a means of verifying the integrity of responses to their database queries. Simultaneously, for privacy or security reasons, the data owner may want to keep the database hidden from service providers. This security property is particularly relevant for aggregate databases, where data is sensitive, and results should only be revealed for queries that are aggregate in nature. In such a scenario, using simple signature schemes for verification does not suffice. We present a solution in which service providers can collaboratively compute aggregate queries without gaining knowledge of intermediate results, and users can verify the results of their queries, relying only on their trust of the data owner. Our protocols are secure under reasonable cryptographic assumptions, and are robust to collusion among k dishonest service providers.
17 Pages
Additional Publication Information: To be presented at the 9th Privacy Enhancing Technologies Symposium (PETS 2009), Seattle, WA, August 2009, and published by Springer-Verlag in the series Lecture Notes in Computer Science (www.springer.de/comp/lncs/).
External Posting Date: June 6, 2009 [Fulltext]. Approved for External Publication
Internal Posting Date: June 6, 2009 [Fulltext]