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.00030770793
Overall Rank
122 | 99.19%
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
133 Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release 2007 PODS 0.0003006035
404 On the Complexity of Optimal K-Anonymity 2004 PODS 0.00019081867
520 Practical Privacy: The SuLQ Framework 2005 PODS 0.00016939312
558 Understanding Hierarchical Methods for Differentially Private Histograms 2013 VLDB 0.00016470707
1,166 PrivateSQL: A Differentially Private SQL Query Engine 2019 VLDB 0.00011731286
1,246 No Free Lunch in Data Privacy 2011 SIGMOD 0.00011346748
1,453 PrivBasis: Frequent Itemset Mining with Differential Privacy 2012 VLDB 0.0001060277
1,705 Injecting Utility into Anonymized Datasets 2006 SIGMOD 9.831451e-05
1,782 The Boundary Between Privacy and Utility in Data Publishing 2007 VLDB 9.652327e-05
1,888 Marginal Release Under Local Differential Privacy 2018 SIGMOD 9.4287112e-05
1,989 Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy 2012 VLDB 9.246325e-05
2,056 Understanding the Sparse Vector Technique for Differential Privacy 2017 VLDB 9.111259e-05
2,175 Two Can Keep a Secret: A Distributed Architecture for Secure Database Services 2005 CIDR 8.9159708e-05
2,449 Simulatable Auditing 2005 PODS 8.4490697e-05
2,453 Personalized Privacy Preservation 2006 SIGMOD 8.4435151e-05
2,902 AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data 2022 VLDB 7.8828375e-05
2,912 Publishing Set-Valued Data via Differential Privacy 2011 VLDB 7.8687198e-05
2,929 Privacy via Pseudorandom Sketches 2006 PODS 7.8418021e-05
3,050 Pan-private Algorithms Via Statistics on Sketches 2011 PODS 7.7067158e-05
3,123 Bayesian Differential Privacy on Correlated Data 2015 SIGMOD 7.6232896e-05
3,359 Towards Robustness in Query Auditing 2006 VLDB 7.3781883e-05
3,993 Output Perturbation with Query Relaxation 2008 VLDB 6.8685183e-05
4,040 Epistemic Privacy 2008 PODS 6.8387308e-05
4,418 Towards an Axiomatization of Statistical Privacy and Utility 2010 PODS 6.6074165e-05
4,944 PrivLava: Synthesizing Relational Data with Foreign Keys under Differential Privacy 2023 SIGMOD 6.3439252e-05
5,686 Differential Privacy in the Wild: A Tutorial on Current Practices & Open Challenges 2017 SIGMOD 6.0368403e-05
5,721 Federated Matrix Factorization with Privacy Guarantee 2022 VLDB 6.018334e-05
6,307 Longshot: Indexing Growing Databases using MPC and Differential Privacy 2023 VLDB 5.8178079e-05
6,498 Differential Privacy in the Wild: A tutorial on current practices & open challenges 2016 VLDB 5.7650744e-05
6,522 PreFair: Privately Generating Justifiably Fair Synthetic Data 2023 VLDB 5.7569675e-05
6,538 Provenance Views for Module Privacy 2011 PODS 5.7534198e-05
6,837 Information Preservation in Statistical Privacy and Bayesian Estimation of Unattributed Histograms 2013 SIGMOD 5.6680244e-05
6,963 Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy 2025 PODS 5.6328879e-05
7,295 Architecting a Differentially Private SQL Engine 2019 CIDR 5.5626111e-05
7,426 CALYPSO: Private Data Management for Decentralized Ledgers 2021 VLDB 5.5308877e-05
7,663 Private Incremental Regression 2017 PODS 5.4772833e-05
7,793 Budget Sharing for Multi-Analyst Differential Privacy 2021 VLDB 5.4516368e-05
8,041 Privacy-Enhancing k-Anonymization of Customer Data 2005 PODS 5.4015242e-05
8,092 PSynDB: Accurate and Accessible Private Data Generation 2019 VLDB 5.3942942e-05
8,133 Optimizing Fitness-For-Use of Differentially Private Linear Queries 2021 VLDB 5.3931029e-05
8,827 To Do or Not To Do: The Dilemma of Disclosing Anonymized Data 2005 SIGMOD 5.268646e-05
9,164 Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation 2008 SIGMOD 5.2151493e-05
9,261 Preserving Privacy and Fairness in Peer-to-Peer Data Integration 2010 SIGMOD 5.2056825e-05
9,308 Universally Optimal Privacy Mechanisms for Minimax Agents 2010 PODS 5.1973494e-05
9,779 Multi-Analyst Differential Privacy for Online Query Answering 2023 VLDB 5.1309523e-05
10,375 Improved Lower Bounds for Privacy under Continual Release 2026 PODS 4.9793485e-05
10,389 Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries 2026 PODS 4.9793485e-05
10,825 Composition for Pufferfish Privacy 2026 VLDB 4.9793485e-05
11,085 Differentially Private Substring and Document Counting 2025 PODS 4.9793485e-05
11,183 Efficient and Accurate Differentially Private Cardinality Continual Releases 2025 SIGMOD 4.9793485e-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
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
Previous Page 1 / 1 Next

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