Krishnaram Kenthapadi
Nina Mishra
ABSTRACT
Given a data set consisting of private information about individuals, we consider the online query auditing problem: given a sequence of queries that have already been posed about the data, their corresponding answers -- where each answer is either the true answer or "denied" (in the event that revealing the answer compromises privacy) -- and given a new query, deny the answer if privacy may be breached or give the true answer otherwise. A related problem is the offline auditing problem where one is given a sequence of queries and all of their true answers and the goal is to determine if a privacy breach has already occurred.We uncover the fundamental issue that solutions to the offline auditing problem cannot be directly used to solve the online auditing problem since query denials may leak information. Consequently, we introduce a new model called simulatable auditing where query denials provably do not leak information. We demonstrate that max queries may be audited in this simulatable paradigm under the classical definition of privacy where a breach occurs if a sensitive value is fully compromised. We also introduce a probabilistic notion of (partial) compromise. Our privacy definition requires that the a-priori probability that a sensitive value lies within some small interval is not that different from the posterior probability (given the query answers). We demonstrate that sum queries can be audited in a simulatable fashion under this privacy definition.
- N. Adam and J. Worthmann. Security-control methods for statistical databases: a comparative study. ACM Comput. Surv., 21(4):515--556, 1989. Google Scholar
Digital Library
- L. Beck. A security machanism for statistical database. ACM Trans. Database Syst., 5(3):316--3338, 1980. Google ScholarDigital Library
- F. Chin. Security problems on inference control for sum, max, and min queries. J. ACM, 33(3):451--464, 1986. Google ScholarDigital Library
- F. Chin and G. Ozsoyoglu. Auditing for secure statistical databases. In Proceedings of the ACM'81 conference, pages 53--59. ACM Press, 1981. Google ScholarDigital Library
- M. Cryan and M. Dyer. A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, pages 240--249. ACM Press, 2002. Google ScholarDigital Library
- T. Dalenius. Towards a methodology for statistical disclosure control. Sartryck ur Statistisk tidskrift, 15:429--444, 1977.Google Scholar
- P. Diaconis and B. Sturmfels. Algebraic algorithms for sampling from conditional distributions. Ann. Statist, 26:363--397, 1998.Google ScholarCross Ref
- I. Dinur and K. Nissim. Revealing information while preserving privacy. In PODS, pages 202--210, 2003. Google ScholarDigital Library
- D. Dobkin, A. Jones, and R. Lipton. Secure databases: protection against user influence. ACM Trans. Database Syst., 4(1):97--106, 1979. Google ScholarDigital Library
- C. Dwork and K. Nissim. Privacy-preserving datamining on vertically partitioned databases. In CRYPTO, 2004.Google ScholarCross Ref
- M. Dyer, A. Frieze, and R. Kannan. A random polynomial-time algorithm for approximating the volume of convex bodies. J. ACM, 38(1):1--17, 1991. Google ScholarDigital Library
- Martin E. Dyer, Ravi Kannan, and John Mount. Sampling contingency tables. Random Structures and Algorithms, 10(4):487--506, 1997. Google ScholarDigital Library
- A. Evfimievski, J. Gehrke, and R. Srikant. Limiting privacy breaches in privacy preserving data mining. In Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pages 211--222. ACM Press, 2003. Google ScholarDigital Library
- S. Goldwasser and S. Micali. Probabilistic encryption & how to play mental poker keeping secret all partial information. In Proceedings of the 14th Annual Symposium on Theory of Computing (STOC), pages 365--377, New York, 1982. ACM Press. Google ScholarDigital Library
- J. Kam and J. Ullman. A model of statistical database their security. ACM Trans. Database Syst., 2(1):1--10, 1977. Google ScholarDigital Library
- R. Kannan, L. Lovasz, and M. Simonovits. Random walks and an O* (n5) volume algorithm for convex bodies. Random Structures and Algorithms, 11, 1997. Google ScholarDigital Library
- J. Kleinberg, C. Papadimitriou, and P. Raghavan. Auditing boolean attributes Journal of Computer and System Sciences, 6:244--253, 2003. Google ScholarDigital Library
- Y. Li, L. Wang, X. Wang, and S. Jajodia. Auditing interval-based inference. In Proceedings of the 14th International Conference on Advanced Information Systems Engineering, pages 553--567, 2002. Google ScholarDigital Library
- L. Lovasz and M. Simonovits. Random walks in a convex body and an improved volume algorithm. Random Structures and Algorithms, 4:359--412, 1993.Google ScholarCross Ref
- L. Lovasz and S. Vempala. Simulated annealing in convex bodies and an O*(n4) volume algorithm. In Proceedings 44th Annual IEEE Symposium on Foundations of Computer Science, pages 650--659, 2003. Google ScholarDigital Library
- S. Reiss. Security in databases: A combinatorial study. J. ACM, 26(1):45--57, 1979. Google ScholarDigital Library
Recommendations
Statistical Database Auditing Without Query Denial Threat
<P>Statistical database auditing is the process of checking aggregate queries that are submitted in a continuous manner, to prevent inference disclosure. Compared to other data protection mechanisms, auditing has the features of flexibility and maximum ...
Statistical Database Auditing Without Query Denial Threat
<P>Statistical database auditing is the process of checking aggregate queries that are submitted in a continuous manner, to prevent inference disclosure. Compared to other data protection mechanisms, auditing has the features of flexibility and maximum ...
Statistical Database Auditing Without Query Denial Threat
<P>Statistical database auditing is the process of checking aggregate queries that are submitted in a continuous manner, to prevent inference disclosure. Compared to other data protection mechanisms, auditing has the features of flexibility and maximum ...
Comments