|
|
|
     |
                                     |
Return to Security and Privacy
to be answered by summation, for all i in q, of 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 Omega(square root of 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(square root of n). For time-T bounded adversaries we demonstrate a privacy- preserving access algorithm whose perturbation magnitude is approximately equal to the square root of T.
@inproceedings {DBLP:conf/pods/DinurN03, author = {Irit Dinur and Kobbi Nissim}, booktitle = {PODS}, title = {Revealing information while preserving privacy.}, pages = {202-210}, year = {2003}, url = {db/conf/pods/pods2003.html#DinurN03}, ee = {http://doi.acm.org/10.1145/773153.773173}, crossref = {conf/pods/2003}, bibsource = {DBLP, http://dblp.uni-trier.de} }  ©2004 Association for Computing Machinery |
