Enhancing Privacy through Negative Representations of Data

Abstract

The paper introduces the concept of a negative database, in which a set of records DB is represented by its complement set. That is, all the records not in DB are represented, and DB itself is not explicitly stored. After introducing the concept, several results are given regarding the feasibility of such a scheme and its potential for enhancing privacy. It is shown that a database consisting of n, l-bit records can be represented negatively using only O"ln" records. It is also shown that membership queries for DB can be processed against the negative representation in time no worse than linear in its size and that reconstructing the database DB represented by a negative database NDB given as input is an NP-hard problem when time complexity is measured as a function of the size of NDB.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2004
Accession Number
ADA498766

Entities

People

  • Fernando Esponda
  • Paul Helman
  • Stephanie Forrest

Organizations

  • University of New Mexico

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Alphabets
  • Anomaly Detection
  • Change Detection
  • Computational Complexity
  • Computer Science
  • Cryptography
  • Data Mining
  • Data Sets
  • Databases
  • Detection
  • Information Operations
  • Language
  • New Mexico
  • Recognition
  • Sequences
  • Standards

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Database Systems and Applications
  • Regression Analysis.