Ensuring correctness over untrusted private database

Get BibTex-formatted data

Author

Sarvjeet Singh, Sunil Prabhakar

Entry type

proceedings

Abstract

In this paper we address the problem of ensuring the correctness of query results returned by an untrusted private database. The database owns the data and may modify it at any time. The querier is allowed to execute queries over this database; however it may not learn anything more than the result of these legal queries. The querier does not necessarily trust the database and would like the owner to furnish proof that the data has not been modified in response to recent events such as the submission of the query. We develop two metrics that capture the correctness of query answers and propose a range of solutions that provide a trade-off between the degree of exposure of private data, and the overhead of generation and verification of the proof. Our proposed solutions are tested on real data through implementation using PostgreSQL.

Date

2008 – 1 – 1

URL

http://portal.acm.org/citation ... 930&CFTOKEN;=52279028

Booktitle

ACM International Conference Proceeding Series; Vol. 261. Proceedings of the 11th international conference on Extending database technology: Advances in database technology

Key alpha

Prabhakar

Pages

476-486

Publisher

ACM

Volume

261

Publication Date

2008-01-01

BibTex-formatted data

To refer to this entry, you may select and copy the text below and paste it into your BibTex document. Note that the text may not contain all macros that BibTex supports.

@Proceedings{ Prabhakar,
	title = "Ensuring correctness over untrusted private database",
	author = "Sarvjeet Singh, Sunil Prabhakar",
	year = "2008",
	month = "1",
	booktitle = "ACM International Conference Proceeding Series; Vol. 261. Proceedings of the 11th international conference on Extending database technology: Advances in database technology",
	pages = "476-486",
	publisher = "ACM",
	volume = "261",
	day = "1",
	abstract = "In this paper we address the problem of ensuring the correctness of query results returned by an untrusted private database. The database owns the data and may modify it at any time. The querier is allowed to execute queries over this database; however it may not learn anything more than the result of these legal queries. The querier does not necessarily trust the database and would like the owner to furnish proof that the data has not been modified in response to recent events such as the submission of the query. We develop two metrics that capture the correctness of query answers and propose a range of solutions that provide a trade-off between the degree of exposure of private data, and the overhead of generation and verification of the proof. Our proposed solutions are tested on real data through implementation using PostgreSQL.",
	url = "http://portal.acm.org/citation.cfm?id=1353343.1353402&coll;=ACM&dl;=ACM&CFID;=71194930&CFTOKEN;=52279028",
}