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.00030756232
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.00030046147
404 On the Complexity of Optimal K-Anonymity 2004 PODS 0.00019072866
520 Practical Privacy: The SuLQ Framework 2005 PODS 0.00016931295
558 Understanding Hierarchical Methods for Differentially Private Histograms 2013 VLDB 0.0001646292
1,168 PrivateSQL: A Differentially Private SQL Query Engine 2019 VLDB 0.00011725733
1,250 No Free Lunch in Data Privacy 2011 SIGMOD 0.00011341376
1,453 PrivBasis: Frequent Itemset Mining with Differential Privacy 2012 VLDB 0.00010597751
1,705 Injecting Utility into Anonymized Datasets 2006 SIGMOD 9.8267971e-05
1,782 The Boundary Between Privacy and Utility in Data Publishing 2007 VLDB 9.6477589e-05
1,889 Marginal Release Under Local Differential Privacy 2018 SIGMOD 9.4242478e-05
1,991 Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy 2012 VLDB 9.2419484e-05
2,058 Understanding the Sparse Vector Technique for Differential Privacy 2017 VLDB 9.1069458e-05
2,178 Two Can Keep a Secret: A Distributed Architecture for Secure Database Services 2005 CIDR 8.9117503e-05
2,450 Simulatable Auditing 2005 PODS 8.4450717e-05
2,453 Personalized Privacy Preservation 2006 SIGMOD 8.439518e-05
2,902 AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data 2022 VLDB 7.8791059e-05
2,913 Publishing Set-Valued Data via Differential Privacy 2011 VLDB 7.8649948e-05
2,930 Privacy via Pseudorandom Sketches 2006 PODS 7.8380899e-05
3,054 Pan-private Algorithms Via Statistics on Sketches 2011 PODS 7.7030675e-05
3,125 Bayesian Differential Privacy on Correlated Data 2015 SIGMOD 7.6196809e-05
3,359 Towards Robustness in Query Auditing 2006 VLDB 7.3746967e-05
3,993 Output Perturbation with Query Relaxation 2008 VLDB 6.8652975e-05
4,041 Epistemic Privacy 2008 PODS 6.8354934e-05
4,420 Towards an Axiomatization of Statistical Privacy and Utility 2010 PODS 6.6042887e-05
4,947 PrivLava: Synthesizing Relational Data with Foreign Keys under Differential Privacy 2023 SIGMOD 6.3409221e-05
5,687 Differential Privacy in the Wild: A Tutorial on Current Practices & Open Challenges 2017 SIGMOD 6.0339826e-05
5,722 Federated Matrix Factorization with Privacy Guarantee 2022 VLDB 6.015485e-05
6,311 Longshot: Indexing Growing Databases using MPC and Differential Privacy 2023 VLDB 5.8150538e-05
6,501 Differential Privacy in the Wild: A tutorial on current practices & open challenges 2016 VLDB 5.7623453e-05
6,525 PreFair: Privately Generating Justifiably Fair Synthetic Data 2023 VLDB 5.7542422e-05
6,540 Provenance Views for Module Privacy 2011 PODS 5.7506962e-05
6,841 Information Preservation in Statistical Privacy and Bayesian Estimation of Unattributed Histograms 2013 SIGMOD 5.6653413e-05
6,964 Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy 2025 PODS 5.6302214e-05
7,299 Architecting a Differentially Private SQL Engine 2019 CIDR 5.5599778e-05
7,430 CALYPSO: Private Data Management for Decentralized Ledgers 2021 VLDB 5.5282694e-05
7,669 Private Incremental Regression 2017 PODS 5.4746904e-05
7,800 Budget Sharing for Multi-Analyst Differential Privacy 2021 VLDB 5.4490561e-05
8,048 Privacy-Enhancing k-Anonymization of Customer Data 2005 PODS 5.3989672e-05
8,099 PSynDB: Accurate and Accessible Private Data Generation 2019 VLDB 5.3917406e-05
8,139 Optimizing Fitness-For-Use of Differentially Private Linear Queries 2021 VLDB 5.3905499e-05
8,836 To Do or Not To Do: The Dilemma of Disclosing Anonymized Data 2005 SIGMOD 5.2661518e-05
9,173 Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation 2008 SIGMOD 5.2126805e-05
9,271 Preserving Privacy and Fairness in Peer-to-Peer Data Integration 2010 SIGMOD 5.2032182e-05
9,317 Universally Optimal Privacy Mechanisms for Minimax Agents 2010 PODS 5.194889e-05
9,784 Multi-Analyst Differential Privacy for Online Query Answering 2023 VLDB 5.1285234e-05
10,387 Improved Lower Bounds for Privacy under Continual Release 2026 PODS 4.9769913e-05
10,401 Weighted Fourier Factorizations: Optimal Gaussian Noise for Differentially Private Marginal and Product Queries 2026 PODS 4.9769913e-05
10,835 Composition for Pufferfish Privacy 2026 VLDB 4.9769913e-05
11,094 Differentially Private Substring and Document Counting 2025 PODS 4.9769913e-05
11,192 Efficient and Accurate Differentially Private Cardinality Continual Releases 2025 SIGMOD 4.9769913e-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.00037940729
254 On the Design and Quantification of Privacy Preserving Data Mining Algorithms 2001 PODS 0.00023009248
260 Statistical Databases: Characteristics, Problems, and Some Solutions 1982 VLDB 0.00022870648
1,186 An Analytic Approach to Statistical Databases 1983 VLDB 0.0001160653
2,053 Auditing Boolean Attributes 2000 PODS 9.1158712e-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,105 Privacy in Data Systems 2003 PODS
3 1,530 A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy 2014 VLDB
4 4,797 Optimal Random Perturbation at Multiple Privacy Levels 2009 VLDB
5 2,930 Privacy via Pseudorandom Sketches 2006 PODS
6 9,173 Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation 2008 SIGMOD
7 9,351 Non-Reversible Privacy Transformations 1982 PODS
8 3,359 Towards Robustness in Query Auditing 2006 VLDB
9 12,598 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