Obfuscated databases and group privacy

Arvind Narayanan, Vitaly Shmatikov

Research output: Chapter in Book/Report/Conference proceedingConference contribution

36 Scopus citations


We investigate whether it is possible to encrypt a database and then give it away in such a form that users can still access it, but only in a restricted way. In contrast to conventional privacy mechanisms that aim to prevent any access to individual records, we aim to restrict the set of queries that can be feasibly evaluated on the encrypted database. We start with a simple form of database obfuscation which makes database records indistinguishable from lookup functions. The only feasible operation on an obfuscated record is to look up some attribute Y by supplying the value of another attribute X that appears in the same record (i.e., someone who does not know X cannot feasibly retrieve Y). We then (i) generalize our construction to conjunctions of equality tests on any attributes of the database, and (ii) achieve a new property we call group privacy. This property ensures that it is easy to retrieve individual records or small subsets of records from the encrypted database by identifying them precisely, but "mass harvesting" queries matching a large number of records are computationally infeasible. Our constructions are non-interactive. The database is transformed in such a way that all queries except those explicitly allowed by the privacy policy become computationally infeasible, i.e., our solutions do not rely on any access-control software or hardware.

Original languageEnglish (US)
Title of host publicationCCS 2005 - Proceedings of the 12th ACM Conference on Computer and Communications Security
Number of pages10
StatePublished - 2005
Externally publishedYes
EventCCS 2005 - 12th ACM Conference on Computer and Communications Security - Alexandria, VA, United States
Duration: Nov 7 2005Nov 11 2005

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221


OtherCCS 2005 - 12th ACM Conference on Computer and Communications Security
Country/TerritoryUnited States
CityAlexandria, VA

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Networks and Communications


  • Database privacy
  • Obfuscation


Dive into the research topics of 'Obfuscated databases and group privacy'. Together they form a unique fingerprint.

Cite this