Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Revealing information while preserving privacy

Revealing information while preserving privacy Revealing Information while Preserving Privacy Irit Dinur Kobbi Nissim — NEC Research Institute 4 Independence Way Princeton, NJ 08540 {iritd,kobbi }@research.nj.nec.com ABSTRACT We examine the tradeo € 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 O( n). For time-T bounded adversaries we demonstrate a privacypreserving access algorithm whose perturbation magnitude š is ˆ T . Keywords Integrity and Security, Data Reconstruction, Subset-sums with noise. One simple tempting solution is to remove from the database all ˜identifying ™ attributes such as the patients ™ names and social security numbers. However, this solution is not http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

Revealing information while preserving privacy

Association for Computing Machinery — Jun 9, 2003

Loading next page...
/lp/association-for-computing-machinery/revealing-information-while-preserving-privacy-CmZl7c3fba

References (23)

Datasource
Association for Computing Machinery
Copyright
Copyright © 2003 by ACM Inc.
ISBN
1-58113-670-6
doi
10.1145/773153.773173
Publisher site
See Article on Publisher Site

Abstract

Revealing Information while Preserving Privacy Irit Dinur Kobbi Nissim — NEC Research Institute 4 Independence Way Princeton, NJ 08540 {iritd,kobbi }@research.nj.nec.com ABSTRACT We examine the tradeo € 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 O( n). For time-T bounded adversaries we demonstrate a privacypreserving access algorithm whose perturbation magnitude š is ˆ T . Keywords Integrity and Security, Data Reconstruction, Subset-sums with noise. One simple tempting solution is to remove from the database all ˜identifying ™ attributes such as the patients ™ names and social security numbers. However, this solution is not

There are no references for this article.