Simulatable Auditing

Summary: Show offline audit methods fail online because denials can leak information, and introduce simulatable auditing, a model where denials provably reveal no extra information. Prove max queries auditable under classical "no full compromise" privacy and define a probabilistic partial-compromise notion that enables simulatable auditing for sum queries. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1345
Venue: PODS
Year: 2005
Pagerank: 8.6299652e-05
Overall Rank: 2,401 | 83.53%
DOI: 10.1145/1065167.1065183

Incoming Non-self Citations Over Time

Authors

1. Krishnaram Kenthapadi (Stanford University)
2. Nina Mishra (Hewlett Packard Enterprise; Stanford University)
3. Kobbi Nissim (Ben Gurion University; Microsoft)

BibTeX Citation

@inproceedings{kenthapadi_pods05,
        address = {New York, NY, USA},
        series = {{PODS} '05},
        title = {{Simulatable Auditing}},
        url = {https://dl.acm.org/doi/10.1145/1065167.1065183},
        doi = {10.1145/1065167.1065183},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Kenthapadi, Krishnaram and Mishra, Nina and Nissim, Kobbi},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 13 of 13 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,669	Injecting Utility into Anonymized Datasets	2006	SIGMOD	0.00010050522
2,862	Privacy via Pseudorandom Sketches	2006	PODS	8.0209471e-05
3,296	Towards Robustness in Query Auditing	2006	VLDB	7.5459953e-05
3,375	Bayesian Differential Privacy on Correlated Data	2015	SIGMOD	7.4639817e-05
3,935	Output Perturbation with Query Relaxation	2008	VLDB	7.0083453e-05
3,974	Epistemic Privacy	2008	PODS	6.9803508e-05
4,159	On the Efficiency of Checking Perfect Privacy	2006	PODS	6.8626218e-05
9,001	Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation	2008	SIGMOD	5.334788e-05
12,301	The Power of the Dinur-Nissim Algorithm: Breaking Privacy of Statistical and Graph Databases	2012	PODS	5.093636e-05
12,309	Aggregate Suppression for Enterprise Search Engines	2012	SIGMOD	5.093636e-05
12,384	Randomized Generalization for Aggregate Suppression Over Hidden Web Databases	2011	VLDB	5.093636e-05
12,495	Privacy Preservation of Aggregates in Hidden Databases: Why and How?	2009	SIGMOD	5.093636e-05
12,545	Publishing Naive Bayesian Classifiers: Privacy without Accuracy Loss	2009	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 2 of 2 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
123	Revealing Information while Preserving Privacy	2003	PODS	0.00031082693
218	Limiting Privacy Breaches in Privacy Preserving Data Mining	2003	PODS	0.00024420564

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,935	Output Perturbation with Query Relaxation	2008	VLDB
2	1,746	The Boundary Between Privacy and Utility in Data Publishing	2007	VLDB
3	3,016	Plausible Deniability for Privacy-Preserving Data Synthesis	2017	VLDB
4	4,159	On the Efficiency of Checking Perfect Privacy	2006	PODS
5	123	Revealing Information while Preserving Privacy	2003	PODS
6	9,603	Multi-Analyst Differential Privacy for Online Query Answering	2023	VLDB
7	2,017	Auditing Boolean Attributes	2000	PODS
8	6,705	Efficient Auditing For Complex SQL queries	2011	SIGMOD
9	3,974	Epistemic Privacy	2008	PODS
10	3,296	Towards Robustness in Query Auditing	2006	VLDB