We examine privacy in statistical databases, and in particular the possibility of achieving privacy via randomization (perturbation). We present a lower bound on the perturbation needed for privacy, possibly severely limiting the usability of the database. Namely, in order to achieve privacy one has to add perturbation of magnitude sqrt{n} as a 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 sqrt{n}.
We also consider time-T bounded adversaries. In this framework we demonstrate that privacy may be maintained with a lower perturbation of magnitude sqrt{T}.
Time permiting, we will also consider auditors and self-auditors for statistical databases.
Based on joint work with Irit Dinur.
Gates 4B (opposite 490), 01/27/04, 4:30 PM