Protecting data privacy through hard-to-reverse negative databases

Fernando Esponda, Elena S. Ackley, Paul Helman, Haixia Jia, Stephanie Forrest

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

12 Scopus citations


The paper extends the idea of negative representations of information for enhancing privacy. Simply put, a set D B of data elements can be represented in terms of its complement set. That is. all the elements not in D B are depicted and D B itself is not explicitly stored. We review the negative database (NDB) representation scheme for storing a negative image compactly and propose a design for depicting a multiple record DB using a collection of NDBs - in contrast to the single N D B approach of previous work. Finally, we present a method for creating negative databases that are hard to reverse in practice, i.e., from which it is hard to obtain DB, by adapting a technique for generating 3-SAT formulas.

Original languageEnglish (US)
Title of host publicationInformation Security - 9th International Conference, ISC 2006, Proceedings
PublisherSpringer Verlag
Number of pages13
ISBN (Print)3540383417, 9783540383413
StatePublished - 2006
Externally publishedYes
Event9th International Information Security Conference, ISC 2006 - Samos Island, Greece
Duration: Aug 30 2006Sep 2 2006

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4176 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other9th International Information Security Conference, ISC 2006
CitySamos Island

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Protecting data privacy through hard-to-reverse negative databases'. Together they form a unique fingerprint.

Cite this