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)
Incoming Non-self Citations Over Time
Authors
- 1. Irit Dinur
- 2. Kobbi Nissim
Incoming Citations (Sorted by Pagerank)
Showing 4 of 54 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 11,382 | MIDE: Accuracy Aware Minimally Invasive Data Exploration For Decision Support | 2022 | VLDB | 4.1945683e-05 |
| 11,444 | Privacy: From Database Reconstruction to Legal Theorems | 2021 | PODS | 4.1945683e-05 |
| 12,104 | The Power of the Dinur-Nissim Algorithm: Breaking Privacy of Statistical and Graph Databases | 2012 | PODS | 4.1945683e-05 |
| 12,160 | Database Access Control & Privacy: Is There A Common Ground? | 2011 | CIDR | 4.1945683e-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 |
|---|---|---|---|---|
| 40 | Privacy-Preserving Data Mining | 2000 | SIGMOD | 0.00074232718 |
| 89 | Statistical Databases: Characteristics, Problems, and Some Solutions | 1982 | VLDB | 0.0005230007 |
| 147 | On the Design and Quantification of Privacy Preserving Data Mining Algorithms | 2001 | PODS | 0.00041235556 |
| 564 | An Analytic Approach to Statistical Databases | 1983 | VLDB | 0.00020017414 |
| 1,506 | Auditing Boolean Attributes | 2000 | PODS | 0.00011618118 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 568 | Practical Privacy: The SuLQ Framework | 2005 | PODS | 0.00019949368 |
| 12,616 | Privacy in Data Systems | 2003 | PODS | 4.1945683e-05 |
| 1,935 | A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy | 2014 | VLDB | 0.00010032967 |
| 4,794 | Optimal Random Perturbation at Multiple Privacy Levels | 2009 | VLDB | 5.9161511e-05 |
| 3,843 | Privacy via Pseudorandom Sketches | 2006 | PODS | 6.7077542e-05 |
| 8,794 | Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation | 2008 | SIGMOD | 4.4502028e-05 |
| 8,946 | Non-Reversible Privacy Transformations | 1982 | PODS | 4.4252228e-05 |
| 3,258 | Towards Robustness in Query Auditing | 2006 | VLDB | 7.3150323e-05 |
| 12,104 | The Power of the Dinur-Nissim Algorithm: Breaking Privacy of Statistical and Graph Databases | 2012 | PODS | 4.1945683e-05 |
| 3,760 | Output Perturbation with Query Relaxation | 2008 | VLDB | 6.7805033e-05 |