Abstract
We examine the tradeoff between privacy and usability of statistical databases. We model a statistical database by an n-bit string d1,..,dn, with a query being a subset q ⊆ [n] to be answered by Σiεq di. Our main result is a polynomial reconstruction algorithm of data from noisy (perturbed) subset sums. Applying this reconstruction algorithm to statistical databases we show that in order to achieve privacy one has to add perturbation of magnitude (Ω√n). That is, smaller perturbation always results in a strong violation of privacy. We show that this result is tight by exemplifying access algorithms for statistical databases that preserve privacy while adding perturbation of magnitude Õ(√n).For time-T bounded adversaries we demonstrate a privacypreserving access algorithm whose perturbation magnitude is ≈ √T.
Keywords
Computer sciencePerturbation (astronomy)Bounded functionUsabilityTheoretical computer scienceInformation privacyAlgorithmStatistical analysisDifferential privacyData miningMathematicsComputer securityStatistics
Affiliated Institutions
Related Publications
On the design and quantification of privacy preserving data mining algorithms
The increasing ability to track and collect large amounts of data with the use of current hardware technology has lead to an interest in the development of data mining algorithm...
Federated Learning With Differential Privacy: Algorithms and Performance Analysis
Federated learning (FL), as a type of distributed machine learning, is capable of significantly preserving clients’ private data from being exposed to adversaries. Ne...
On lattices, learning with errors, random linear codes, and cryptography
Our main result is a reduction from worst-case lattice problems such as SVP and SIVP to a certain learning problem. This learning problem is a natural extension of the 'learning...
A learning theory approach to noninteractive database privacy
In this article, we demonstrate that, ignoring computational constraints, it is possible to release synthetic databases that are useful for accurately answering large classes of...
Guaranteeing anonymity when sharing medical data, the Datafly system
We present a computer program named Datafly that maintains anonymity in medical data by automatically generalizing, substituting, and removing information as appropriate without...
Publication Info
- Year
- 2003
- Type
- article
- Pages
- 202-210
- Citations
- 982
- Access
- Closed
External Links
Social Impact
Altmetric
PlumX Metrics
Social media, news, blog, policy document mentions
Citation Metrics
982
OpenAlex
Cite This
Irit Dinur,
Kobbi Nissim
(2003).
Revealing information while preserving privacy.
, 202-210.
https://doi.org/10.1145/773153.773173
Identifiers
- DOI
- 10.1145/773153.773173