Revealing Information while Preserving Privacy

Summary: Model DB as an n-bit vector and give a polynomial-time reconstruction algorithm that recovers the data from noisy subset-sum answers, showing privacy is violated unless noise is Ω(√n). Tightness: exhibit access schemes with Õ(√n) noise; for time-T adversaries required noise ≈√T. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h2aea8a8c88b2a2aa
Venue: PODS
Year: 2003
Pagerank: 0.00030770793
Overall Rank: 122 | 99.19%
DOI: 10.1145/773153.773173

Incoming Non-self Citations Over Time

Authors

1. Irit Dinur (NEC Research Institute)
2. Kobbi Nissim (Microsoft; NEC Research Institute; Rutgers University)

BibTeX Citation

@inproceedings{dinur_pods03,
        address = {New York, NY, USA},
        series = {{PODS} '03},
        title = {{Revealing Information while Preserving Privacy}},
        url = {https://dl.acm.org/doi/10.1145/773153.773173},
        doi = {10.1145/773153.773173},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Dinur, Irit and Nissim, Kobbi},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 7 of 57 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
11,308	Calibrating Noise for Group Privacy in Subsampled Mechanisms	2025	VLDB	4.9793485e-05
11,369	PrivAGM: Secure Construction of Differentially Private Directed Attributed Graph Models on Decentralized Social Graphs	2025	VLDB	4.9793485e-05
11,771	Epistemic Parity: Reproducibility as an Evaluation Metric for Differential Privacy	2023	VLDB	4.9793485e-05
11,888	MIDE: Accuracy Aware Minimally Invasive Data Exploration For Decision Support	2022	VLDB	4.9793485e-05
11,949	Privacy: From Database Reconstruction to Legal Theorems	2021	PODS	4.9793485e-05
12,592	The Power of the Dinur-Nissim Algorithm: Breaking Privacy of Statistical and Graph Databases	2012	PODS	4.9793485e-05
12,647	Database Access Control & Privacy: Is There A Common Ground?	2011	CIDR	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
68	Privacy-Preserving Data Mining	2000	SIGMOD	0.00037958605
254	On the Design and Quantification of Privacy Preserving Data Mining Algorithms	2001	PODS	0.00023020039
260	Statistical Databases: Characteristics, Problems, and Some Solutions	1982	VLDB	0.00022880477
1,185	An Analytic Approach to Statistical Databases	1983	VLDB	0.0001161182
2,050	Auditing Boolean Attributes	2000	PODS	9.1201864e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	520	Practical Privacy: The SuLQ Framework	2005	PODS
2	13,099	Privacy in Data Systems	2003	PODS
3	1,528	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB
4	4,794	Optimal Random Perturbation at Multiple Privacy Levels	2009	VLDB
5	2,929	Privacy via Pseudorandom Sketches	2006	PODS
6	9,164	Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation	2008	SIGMOD
7	9,342	Non-Reversible Privacy Transformations	1982	PODS
8	3,359	Towards Robustness in Query Auditing	2006	VLDB
9	12,592	The Power of the Dinur-Nissim Algorithm: Breaking Privacy of Statistical and Graph Databases	2012	PODS
10	3,993	Output Perturbation with Query Relaxation	2008	VLDB