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
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

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 56 citing papers.

Rank Citing Paper Year Venue Pagerank
130 Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release 2007 PODS 0.00030604781
384 On the Complexity of Optimal K-Anonymity 2004 PODS 0.00019510305
510 Practical Privacy: The SuLQ Framework 2005 PODS 0.00017220509
567 Understanding Hierarchical Methods for Differentially Private Histograms 2013 VLDB 0.00016420715
1,144 PrivateSQL: A Differentially Private SQL Query Engine 2019 VLDB 0.00011999046
1,230 No Free Lunch in Data Privacy 2011 SIGMOD 0.00011572271
1,421 PrivBasis: Frequent Itemset Mining with Differential Privacy 2012 VLDB 0.00010828328
1,669 Injecting Utility into Anonymized Datasets 2006 SIGMOD 0.00010050522
1,746 The Boundary Between Privacy and Utility in Data Publishing 2007 VLDB 9.8564338e-05
1,837 Marginal Release Under Local Differential Privacy 2018 SIGMOD 9.6443703e-05
1,956 Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy 2012 VLDB 9.4157042e-05
2,012 Understanding the Sparse Vector Technique for Differential Privacy 2017 VLDB 9.3073552e-05
2,133 Two Can Keep a Secret: A Distributed Architecture for Secure Database Services 2005 CIDR 9.1164075e-05
2,397 Personalized Privacy Preservation 2006 SIGMOD 8.6343421e-05
2,401 Simulatable Auditing 2005 PODS 8.6299652e-05
2,841 AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data 2022 VLDB 8.0637668e-05
2,856 Publishing Set-Valued Data via Differential Privacy 2011 VLDB 8.0321774e-05
2,862 Privacy via Pseudorandom Sketches 2006 PODS 8.0209471e-05
2,992 Pan-private Algorithms Via Statistics on Sketches 2011 PODS 7.8836024e-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,407 Towards an Axiomatization of Statistical Privacy and Utility 2010 PODS 6.719141e-05
4,827 PrivLava: Synthesizing Relational Data with Foreign Keys under Differential Privacy 2023 SIGMOD 6.4895329e-05
5,588 Federated Matrix Factorization with Privacy Guarantee 2022 VLDB 6.1564686e-05
5,613 Differential Privacy in the Wild: A Tutorial on Current Practices & Open Challenges 2017 SIGMOD 6.1501263e-05
6,171 Longshot: Indexing Growing Databases using MPC and Differential Privacy 2023 VLDB 5.9513399e-05
6,370 Differential Privacy in the Wild: A tutorial on current practices & open challenges 2016 VLDB 5.8973335e-05
6,419 Provenance Views for Module Privacy 2011 PODS 5.8819368e-05
6,701 Information Preservation in Statistical Privacy and Bayesian Estimation of Unattributed Histograms 2013 SIGMOD 5.7980998e-05
6,826 Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy 2025 PODS 5.7621757e-05
7,147 Architecting a Differentially Private SQL Engine 2019 CIDR 5.6902859e-05
7,280 CALYPSO: Private Data Management for Decentralized Ledgers 2021 VLDB 5.6574761e-05
7,358 PreFair: Privately Generating Justifiably Fair Synthetic Data 2023 VLDB 5.6344213e-05
7,517 Private Incremental Regression 2017 PODS 5.6029996e-05
7,639 Budget Sharing for Multi-Analyst Differential Privacy 2021 VLDB 5.5767645e-05
7,875 Privacy-Enhancing k-Anonymization of Customer Data 2005 PODS 5.5253531e-05
7,924 PSynDB: Accurate and Accessible Private Data Generation 2019 VLDB 5.5181056e-05
7,968 Optimizing Fitness-For-Use of Differentially Private Linear Queries 2021 VLDB 5.516666e-05
8,662 To Do or Not To Do: The Dilemma of Disclosing Anonymized Data 2005 SIGMOD 5.3889537e-05
9,001 Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation 2008 SIGMOD 5.334788e-05
9,087 Preserving Privacy and Fairness in Peer-to-Peer Data Integration 2010 SIGMOD 5.3251649e-05
9,135 Universally Optimal Privacy Mechanisms for Minimax Agents 2010 PODS 5.3166398e-05
9,603 Multi-Analyst Differential Privacy for Online Query Answering 2023 VLDB 5.2487195e-05
10,158 Improved Lower Bounds for Privacy under Continual Release 2026 PODS 5.093636e-05
10,172 Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries 2026 PODS 5.093636e-05
10,642 Differentially Private Substring and Document Counting 2025 PODS 5.093636e-05
10,759 Efficient and Accurate Differentially Private Cardinality Continual Releases 2025 SIGMOD 5.093636e-05
10,914 Calibrating Noise for Group Privacy in Subsampled Mechanisms 2025 VLDB 5.093636e-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
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
Previous Page 1 / 1 Next

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