Simulatable Auditing Krishnaram Kenthapadi and Kobbi Nissim   View Paper (PDF)   Return to Research Session 3: Security and Privacy 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 online 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 di erent from the posterior probability (given the query answers). We demonstrate that sum queries can be audited in a simulatable fashion under this privacy definition. ©2006 Association for Computing Machinery