Simulatable auditing

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.

REFERENCES

• 1: Nabil R. Adam , John C. Worthmann, Security-control methods for statistical databases: a comparative study, ACM Computing Surveys (CSUR), v.21 n.4, p.515-556, Dec. 1989 [doi>10.1145/76894.76895]
• 2: Leland L. Beck, A security machanism for statistical database, ACM Transactions on Database Systems (TODS), v.5 n.3, p.316-3338, Sept. 1980 [doi>10.1145/320613.320617]
• 3: Francis Chin, Security problems on inference control for SUM, MAX, and MIN queries, Journal of the ACM (JACM), v.33 n.3, p.451-464, July 1986 [doi>10.1145/5925.5928]
• 4: Francis Chin , Gultekin Ozsoyoglu, Auditing for secure statistical databases, Proceedings of the ACM '81 conference, p.53-59, January 1981 [doi>10.1145/800175.809832]
• 5: Mary Cryan , Martin Dyer, A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509946]
• 6: T. Dalenius. Towards a methodology for statistical disclosure control. Sartryck ur Statistisk tidskrift, 15:429--444, 1977.
• 7: P. Diaconis and B. Sturmfels. Algebraic algorithms for sampling from conditional distributions. Ann. Statist, 26:363--397, 1998.
• 8: Irit Dinur , Kobbi Nissim, Revealing information while preserving privacy, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.202-210, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773173]
• 9: David Dobkin , Anita K. Jones , Richard J. Lipton, Secure databases: protection against user influence, ACM Transactions on Database Systems (TODS), v.4 n.1, p.97-106, March 1979 [doi>10.1145/320064.320068]
• 10: C. Dwork and K. Nissim. Privacy-preserving datamining on vertically partitioned databases. In CRYPTO, 2004.
• 11: Martin Dyer , Alan Frieze , Ravi Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies, Journal of the ACM (JACM), v.38 n.1, p.1-17, Jan. 1991 [doi>10.1145/102782.102783]
• 12: Martin Dyer , Ravi Kannan , John Mount, Sampling contingency tables, Random Structures & Algorithms, v.10 n.4, p.487-506, July 1997 [doi>10.1002/(SICI)1098-2418(199707)10:4<487::AID-RSA4>3.0.CO;2-Q]
• 13: Alexandre Evfimievski , Johannes Gehrke , Ramakrishnan Srikant, Limiting privacy breaches in privacy preserving data mining, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.211-222, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773174]
• 14: Shafi Goldwasser , Silvio Micali, Probabilistic encryption & how to play mental poker keeping secret all partial information, Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.365-377, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802212]
• 15: John B. Kam , Jeffrey D. Ullman, A model of statistical database their security, ACM Transactions on Database Systems (TODS), v.2 n.1, p.1-10, March 1977 [doi>10.1145/320521.320525]
• 16: Ravi Kannan , László Lovász , Miklós Simonovits, Random walks and an O*(n5) volume algorithm for convex bodies, Random Structures & Algorithms, v.11 n.1, p.1-50, Aug. 1997 [doi>10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X]
• 17: Jon Kleinberg , Christos Papadimitriou , Prabhakar Raghavan, Auditing Boolean attributes, Journal of Computer and System Sciences, v.66 n.1, p.244-253, 01 February 2003 [doi>10.1016/S0022-0000(02)00036-3]
• 18: Yingjiu Li , Lingyu Wang , Xiaoyang Sean Wang , Sushil Jajodia, Auditing Interval-Based Inference, Proceedings of the 14th International Conference on Advanced Information Systems Engineering, p.553-567, May 27-31, 2002
• 19: L. Lovasz and M. Simonovits. Random walks in a convex body and an improved volume algorithm. Random Structures and Algorithms, 4:359--412, 1993.
• 20: László Lovász , Santosh Vempala, Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.650, October 11-14, 2003
• 21: Steven P. Reiss, Security in Databases: A Combinatorial Study, Journal of the ACM (JACM), v.26 n.1, p.45-57, Jan. 1979 [doi>10.1145/322108.322113]