Negative databases

摘要

The intriguing idea of a "negative database" that stores everything except the information of interest has been proposed recently (Esponda 2005) as a means for providing data privacy against partially-specified queries, while at the same time providing an efficient mechanism to answer fully-specified queries. To make this concrete, consider a database containing information about the names, institutions and professions of individuals. Here, partially-specified queries would look like "List all engineers in the database", whereas fully-specified queries would be of the form "Does {P Balaram, Indian Institute of Science, Molecular Biologist} exist in the database?". In a nutshell, the goal of a negative database is to prevent "probing attacks" without adversely impacting standard verification queries. The crux of the technique is that although logically trivial, it is computationally extremely hard to invert a well-designed negative database and thereby determine the original contents.