The statistical security of a statistical database

This note proposes a statistical perturbation scheme to protect a statistical database against compromise. The proposed scheme can handle the security of numerical as well as nonnumerical sensitive fields. Furthermore, knowledge of some records in a database does not help to compromise unknown records. We use Chebyshev's inequality to analyze the trade-offs among the magnitude of the perturbations, the error incurred by statistical queries, and the size of the query set to which they apply. We show that if the statistician is given absolute error guarantees, then a compromise is possible, but the cost is made exponential in the size of the database.