DBScholar

Back to papers

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.00030654879
Overall Rank
123 | 99.18%
DOI
10.1145/773153.773173

Incoming Non-self Citations Over Time

Authors

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 50 of 57 citing papers.

Rank Citing Paper Year Venue Pagerank
134 Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release 2007 PODS 0.00029947443
406 On the Complexity of Optimal K-Anonymity 2004 PODS 0.00019009895
525 Practical Privacy: The SuLQ Framework 2005 PODS 0.00016875512
559 Understanding Hierarchical Methods for Differentially Private Histograms 2013 VLDB 0.00016409103
1,170 PrivateSQL: A Differentially Private SQL Query Engine 2019 VLDB 0.00011687052
1,256 No Free Lunch in Data Privacy 2011 SIGMOD 0.00011304781
1,458 PrivBasis: Frequent Itemset Mining with Differential Privacy 2012 VLDB 0.00010562758
1,714 Injecting Utility into Anonymized Datasets 2006 SIGMOD 9.7943215e-05
1,792 The Boundary Between Privacy and Utility in Data Publishing 2007 VLDB 9.6159131e-05
1,899 Marginal Release Under Local Differential Privacy 2018 SIGMOD 9.3931147e-05
1,998 Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy 2012 VLDB 9.2114984e-05
2,064 Understanding the Sparse Vector Technique for Differential Privacy 2017 VLDB 9.0768606e-05
2,194 Two Can Keep a Secret: A Distributed Architecture for Secure Database Services 2005 CIDR 8.8822913e-05
2,457 Simulatable Auditing 2005 PODS 8.4172033e-05
2,462 Personalized Privacy Preservation 2006 SIGMOD 8.4116174e-05
2,917 AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data 2022 VLDB 7.8530527e-05
2,925 Publishing Set-Valued Data via Differential Privacy 2011 VLDB 7.8390031e-05
2,945 Privacy via Pseudorandom Sketches 2006 PODS 7.8121754e-05
3,064 Pan-private Algorithms Via Statistics on Sketches 2011 PODS 7.6775964e-05
3,134 Bayesian Differential Privacy on Correlated Data 2015 SIGMOD 7.5944855e-05
3,370 Towards Robustness in Query Auditing 2006 VLDB 7.3503641e-05
4,008 Output Perturbation with Query Relaxation 2008 VLDB 6.8439132e-05
4,062 Epistemic Privacy 2008 PODS 6.8129278e-05
4,441 Towards an Axiomatization of Statistical Privacy and Utility 2010 PODS 6.5824511e-05
4,964 PrivLava: Synthesizing Relational Data with Foreign Keys under Differential Privacy 2023 SIGMOD 6.3234288e-05
5,698 Differential Privacy in the Wild: A Tutorial on Current Practices & Open Challenges 2017 SIGMOD 6.0140309e-05
5,736 Federated Matrix Factorization with Privacy Guarantee 2022 VLDB 5.995594e-05
6,323 Longshot: Indexing Growing Databases using MPC and Differential Privacy 2023 VLDB 5.7958256e-05
6,516 Differential Privacy in the Wild: A tutorial on current practices & open challenges 2016 VLDB 5.7432938e-05
6,538 PreFair: Privately Generating Justifiably Fair Synthetic Data 2023 VLDB 5.7352151e-05
6,550 Provenance Views for Module Privacy 2011 PODS 5.7316808e-05
6,858 Information Preservation in Statistical Privacy and Bayesian Estimation of Unattributed Histograms 2013 SIGMOD 5.6466085e-05
6,985 Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy 2025 PODS 5.6116044e-05
7,315 Architecting a Differentially Private SQL Engine 2019 CIDR 5.5415931e-05
7,453 CALYPSO: Private Data Management for Decentralized Ledgers 2021 VLDB 5.5099895e-05
7,682 Private Incremental Regression 2017 PODS 5.4565877e-05
7,815 Budget Sharing for Multi-Analyst Differential Privacy 2021 VLDB 5.4310381e-05
8,066 Privacy-Enhancing k-Anonymization of Customer Data 2005 PODS 5.3811151e-05
8,117 PSynDB: Accurate and Accessible Private Data Generation 2019 VLDB 5.3739121e-05
8,156 Optimizing Fitness-For-Use of Differentially Private Linear Queries 2021 VLDB 5.3727254e-05
8,854 To Do or Not To Do: The Dilemma of Disclosing Anonymized Data 2005 SIGMOD 5.2487405e-05
9,198 Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation 2008 SIGMOD 5.1954442e-05
9,295 Preserving Privacy and Fairness in Peer-to-Peer Data Integration 2010 SIGMOD 5.1860131e-05
9,342 Universally Optimal Privacy Mechanisms for Minimax Agents 2010 PODS 5.1777115e-05
9,816 Multi-Analyst Differential Privacy for Online Query Answering 2023 VLDB 5.1115653e-05
10,453 Improved Lower Bounds for Privacy under Continual Release 2026 PODS 4.9605343e-05
10,467 Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries 2026 PODS 4.9605343e-05
10,896 Composition for Pufferfish Privacy 2026 VLDB 4.9605343e-05
11,155 Differentially Private Substring and Document Counting 2025 PODS 4.9605343e-05
11,251 Efficient and Accurate Differentially Private Cardinality Continual Releases 2025 SIGMOD 4.9605343e-05
Previous Page 1 / 2 Next

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
69 Privacy-Preserving Data Mining 2000 SIGMOD 0.00037815735
256 On the Design and Quantification of Privacy Preserving Data Mining Algorithms 2001 PODS 0.00022933612
263 Statistical Databases: Characteristics, Problems, and Some Solutions 1982 VLDB 0.00022797298
1,189 An Analytic Approach to Statistical Databases 1983 VLDB 0.00011569335
2,061 Auditing Boolean Attributes 2000 PODS 9.0857589e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

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