Protecting Data Privacy through Hard-to-Reverse Negative Databases

Full textClick to download.
CitationProtecting Data Privacy through Hard-to-Reverse Negative Databases. Int. Journal of Information Security 6:6 (2007).
AuthorsFernando Esponda
Elena Ackley
Paul Helman
Haixia Jia
Stephanie Forrest


A set DB of data elements can be represented in terms of its complement set, known as a negative database. That is, all of the elements not in DB are represented, and DB itself is not explicitly stored. This method of representing data has certain properties that are relevant for privacy enhancing applications. The paper reviews the negative database (N DB) representation scheme for storing a negative image compactly, and it proposes using a collection of N DBs to represent a single DB, that is, one N DB is assigned for each record in DB. This method has the advantage of producing negative databases that are hard to reverse in practice, i.e., from which it is hard to obtain DB. This result is obtained by adapting a technique for generating hard-to-solve 3-SAT formulas. Finally we suggest potential avenues of application.

Back to publications
Back to previous page