Protecting Data Privacy through Hard-to-Reverse Negative Databases

Full textClick to download.
CitationProceedings of the 9th Information Security Conference, (2006).
AuthorsFernando Esponda
Elena S. Ackley
Paul Helman
Haixia Jia
Stephanie Forrest


The paper extends the idea of negative representations of information for enhancing privacy. Simply put, a set DB of data elements can be represented in terms of its complement set. That is, all the elements not in DB are depicted and DB 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 NDB 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.

Back to publications
Back to previous page