Key points are not available for this paper at this time.
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.
Building similarity graph...
Analyzing shared references across papers
Loading...
Dinur et al. (Mon,) studied this question.
www.synapsesocial.com/papers/6a08bd733d5e33e46910992a — DOI: https://doi.org/10.1145/773153.773173
Irit Dinur
Kobbi Nissim
Princeton University
Building similarity graph...
Analyzing shared references across papers
Loading...