CERIAS - Center for Education and Research in Information Assurance and Security

Skip Navigation
Purdue University - Discovery Park
Center for Education and Research in Information Assurance and Security

Obfuscated Databases: Definitions and Constructions

Vitaly Shmatikov - University of Texas at Austin

Feb 02, 2005

Size: 220.4MB

Download: Video Icon MP4 Video  
Watch in your Browser   Watch on Youtube Watch on YouTube


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.

About the Speaker

Vitaly Shmatikov is an assistant professor in the Department of Computer
Sciences at the University of Texas at Austin. Prior to joining UT,
he worked as a computer scientist at SRI International. Vitaly\'s
research focuses on tools and formal methods for automated analysis and
verification of secure systems, as well as various aspects of anonymity
and privacy. Vitaly received his PhD in 2000 from Stanford University,
with thesis on \"Finite-State Analysis of Security Protocols.\"

Unless otherwise noted, the security seminar is held on Wednesdays at 4:30P.M. STEW G52 (Suite 050B), West Lafayette Campus. More information...


The views, opinions and assumptions expressed in these videos are those of the presenter and do not necessarily reflect the official policy or position of CERIAS or Purdue University. All content included in these videos, are the property of Purdue University, the presenter and/or the presenter’s organization, and protected by U.S. and international copyright laws. The collection, arrangement and assembly of all content in these videos and on the hosting website exclusive property of Purdue University. You may not copy, reproduce, distribute, publish, display, perform, modify, create derivative works, transmit, or in any other way exploit any part of copyrighted material without permission from CERIAS, Purdue University.