Personal tools
You are here: Home Events Abstract Archives 2003 The Secrecy of Database Queries

The Secrecy of Database Queries

Dan Suciu Department of Computer Science & Engineering University of Washington 11am 3 September 2003 Room 2511, JCMB, King's Buildings

The standard technique for hiding secret data from unauthorized database users is to give them access only to a view, and not to the entire database. Such a view typically omits secret data values, or breaks sensitive associations between values, or otherwise restructures the data to hide some secret information.

We study here the following problem. Given a view V, which we want to publish, and a query Q, which we want to hide, determine whether the view leaks any information about the query. Our initial motivation was to study the secrecy of data published with the XML Encryption Standard, where clear text data is interleaved with encrypted data, but we soon realized that secrecy in databases is not understood even in the absence of any encryption. To formalize the problem, we adapt Shannon's definition of perfect secrecy, and provide a complete characterization of perfect secrecy for the case when both V and Q are conjunctive queries, showing that the problem is Pi_2 complete. This is a first step towards understanding the hiding power of traditional database views. I will then describe a number of open problems in query secrecy.

Joint work with Gerome Miklau

Document Actions