Abstract

How to protect individuals’ privacy while releasing microdata tables for analysis pur- poses has attracted significant attention. We study the case where different microdata tables generalized over the same underlying secret table may be released upon users’ queries. To satisfy privacy constraints, an auditing system must determine whether the next query can be safely answered based on the history of answered queries. However, when answering a new query is not safe, denying it may not be, either, since a denial itself may still convey some sensitive information to the user. We first model this issue in the context of releasing microdata tables. Inspired by the Simulatable Auditing technique in statistical databases, we propose a safe strategy for auditing queries that ask for microdata tables generalized over secret tables. The strategy can provide provably safe answers and good data utility. We also study how to efficiently maintain the history of answered queries for the auditing purpose. To the best of our knowledge, this is the first study on the simulatable auditing issue of microdata queries.