October 8, 2008 - Matthew Green

Title: Cryptographic Techniques for Oblivious Database Access

Abstract:
In 2006, America Online accidentally published the web search histories for more than 650,000 of their customers. Although the data was anonymized, simple analysis of the customers' query patterns revealed deeply private information about their identities and interests. This example illustrates how increasingly dependent we are on third parties who not only provide us with our data, but must be trusted to protect our privacy in the way we access it. In this talk we will discuss new cryptographic techniques for constructing "privacy-preserving" databases that conceal users' identities and query patterns. In such a database, even the trusted database operator does not learn which records its users access. At the same time, we show how such a database may still enforce sophisticated (and history-dependent) access control policies limiting which records each user may obtain. The techniques we will discuss include two new protocols for efficient, adaptive Oblivious Transfer, as well as new access control mechanisms derived from e-Cash techniques.