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: 1291
Venue: PODS
Year: 2003
Pagerank: 0.00031082693
Overall Rank: 123 | 99.16%
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 6 of 56 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,992	PrivAGM: Secure Construction of Differentially Private Directed Attributed Graph Models on Decentralized Social Graphs	2025	VLDB	5.093636e-05
11,459	Epistemic Parity: Reproducibility as an Evaluation Metric for Differential Privacy	2023	VLDB	5.093636e-05
11,580	MIDE: Accuracy Aware Minimally Invasive Data Exploration For Decision Support	2022	VLDB	5.093636e-05
11,642	Privacy: From Database Reconstruction to Legal Theorems	2021	PODS	5.093636e-05
12,301	The Power of the Dinur-Nissim Algorithm: Breaking Privacy of Statistical and Graph Databases	2012	PODS	5.093636e-05
12,356	Database Access Control & Privacy: Is There A Common Ground?	2011	CIDR	5.093636e-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
70	Privacy-Preserving Data Mining	2000	SIGMOD	0.0003804755
244	On the Design and Quantification of Privacy Preserving Data Mining Algorithms	2001	PODS	0.00023476901
249	Statistical Databases: Characteristics, Problems, and Some Solutions	1982	VLDB	0.00023275528
1,183	An Analytic Approach to Statistical Databases	1983	VLDB	0.00011778053
2,017	Auditing Boolean Attributes	2000	PODS	9.3006188e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	510	Practical Privacy: The SuLQ Framework	2005	PODS
2	12,809	Privacy in Data Systems	2003	PODS
3	1,504	A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy	2014	VLDB
4	4,732	Optimal Random Perturbation at Multiple Privacy Levels	2009	VLDB
5	2,862	Privacy via Pseudorandom Sketches	2006	PODS
6	9,001	Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation	2008	SIGMOD
7	9,169	Non-Reversible Privacy Transformations	1982	PODS
8	3,296	Towards Robustness in Query Auditing	2006	VLDB
9	12,301	The Power of the Dinur-Nissim Algorithm: Breaking Privacy of Statistical and Graph Databases	2012	PODS
10	3,935	Output Perturbation with Query Relaxation	2008	VLDB