Statistical Security of a Statistical Data Base

Traub, Joseph F.; Wozniakowski, Henryk; Yemini, Yechiam

This paper proposes a statistical perturbation scheme to protect a statistical database against compromise. The proposed scheme can handle the security of numerical as well as non-numerical sensitive fields or a combination of fields. Furthermore, knowledge of some records in a database does not help to compromise unknown records. We use Chebychev's inequality to analyze the tradeoffs between 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.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-036-82
Published Here
October 26, 2011