Obfuscated Databases: Definitions and Constructions

Feb 02, 2005

Download: MP4 Video Size: 220.4MB  
Watch on YouTube

Abstract

I will present some new definitions and constructions for privacy in
large databases. In contrast to conventional privacy mechanisms that aim
to prevent any access to individual records, our techniques are designed
to prevent indiscriminate harvesting of information while enabling some
forms of legitimate access.

We start with a simple construction for an obfuscated database that is
provably indistinguishable from a black-box lookup oracle (in the random
oracle model). Some attributes of the database are designated as "key,"
the rest as "data." The database behaves as a lookup oracle if, for any
record, it is infeasible to extract the data fields without specifying
the key fields, yet, given the values of the key fields, it is easy to
retrieve the corresponding data fields.

We then generalize our constructions to a larger class of queries, and
achieve a privacy property we call "group privacy." It ensures that
users can retrieve individual records or small subsets of records from
the database by identifying them precisely. The database is obfuscated
in such a way that queries returning a large subset of records are
computationally infeasible.

This is joint work with Arvind Narayanan.