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