Database Paper Browser

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
1292
Venue
PODS
Year
2003
Pagerank
0.0004241101
Overall Rank
136 | 99.06%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 54 citing papers.

Rank Citing Paper Year Venue Pagerank
111 Privacy, Accuracy, and Consistency Too: A Holistic Solution to Contingency Table Release 2007 PODS 0.00047073785
304 On the Complexity of Optimal K-Anonymity 2004 PODS 0.00028290121
568 Practical Privacy: The SuLQ Framework 2005 PODS 0.00019949368
719 Understanding Hierarchical Methods for Differentially Private Histograms 2013 VLDB 0.00017626484
1,465 No Free Lunch in Data Privacy 2011 SIGMOD 0.00011860847
1,567 PrivBasis: Frequent Itemset Mining with Differential Privacy 2012 VLDB 0.0001133268
1,633 Injecting Utility into Anonymized Datasets 2006 SIGMOD 0.00011060784
1,738 PrivateSQL: A Differentially Private SQL Query Engine 2019 VLDB 0.00010720057
1,761 The Boundary Between Privacy and Utility in Data Publishing 2007 VLDB 0.00010651764
1,930 Marginal Release Under Local Differential Privacy 2018 SIGMOD 0.00010040732
2,052 Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy 2012 VLDB 9.676612e-05
2,119 Two Can Keep a Secret: A Distributed Architecture for Secure Database Services 2005 CIDR 9.5090272e-05
2,577 Simulatable Auditing 2005 PODS 8.5099821e-05
2,625 Epistemic Privacy 2008 PODS 8.4317678e-05
2,682 Personalized Privacy Preservation 2006 SIGMOD 8.3202837e-05
2,758 Understanding the Sparse Vector Technique for Differential Privacy 2017 VLDB 8.1653216e-05
2,894 Pan-private Algorithms Via Statistics on Sketches 2011 PODS 7.9474698e-05
3,097 Publishing Set-Valued Data via Differential Privacy 2011 VLDB 7.5647028e-05
3,172 Bayesian Differential Privacy on Correlated Data 2015 SIGMOD 7.4411955e-05
3,258 Towards Robustness in Query Auditing 2006 VLDB 7.3150323e-05
3,329 AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data 2022 VLDB 7.2156424e-05
3,760 Output Perturbation with Query Relaxation 2008 VLDB 6.7805033e-05
3,843 Privacy via Pseudorandom Sketches 2006 PODS 6.7077542e-05
4,189 Towards an Axiomatization of Statistical Privacy and Utility 2010 PODS 6.3743594e-05
5,349 PrivLava: Synthesizing Relational Data with Foreign Keys under Differential Privacy 2023 SIGMOD 5.553869e-05
5,545 Differential Privacy in the Wild: A tutorial on current practices & open challenges 2016 VLDB 5.4462098e-05
5,687 Differential Privacy in the Wild: A Tutorial on Current Practices & Open Challenges 2017 SIGMOD 5.3706593e-05
5,775 Federated Matrix Factorization with Privacy Guarantee 2022 VLDB 5.3310992e-05
6,515 Provenance Views for Module Privacy 2011 PODS 5.0321577e-05
6,691 Information Preservation in Statistical Privacy and Bayesian Estimation of Unattributed Histograms 2013 SIGMOD 4.9613269e-05
6,914 Private Incremental Regression 2017 PODS 4.8925595e-05
6,970 Architecting a Differentially Private SQL Engine 2019 CIDR 4.8796169e-05
7,196 Longshot: Indexing Growing Databases using MPC and Differential Privacy 2023 VLDB 4.8036487e-05
7,253 CALYPSO: Private Data Management for Decentralized Ledgers 2021 VLDB 4.7886948e-05
7,502 PSynDB: Accurate and Accessible Private Data Generation 2019 VLDB 4.7180617e-05
7,541 Privacy-Enhancing k-Anonymization of Customer Data 2005 PODS 4.7157092e-05
7,619 Budget Sharing for Multi-Analyst Differential Privacy 2021 VLDB 4.6941145e-05
7,997 Optimizing Fitness-For-Use of Differentially Private Linear Queries 2021 VLDB 4.6105691e-05
8,353 To Do or Not To Do: The Dilemma of Disclosing Anonymized Data 2005 SIGMOD 4.5386781e-05
8,609 PreFair: Privately Generating Justifiably Fair Synthetic Data 2023 VLDB 4.4853979e-05
8,794 Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation 2008 SIGMOD 4.4502028e-05
8,931 Preserving Privacy and Fairness in Peer-to-Peer Data Integration 2010 SIGMOD 4.427232e-05
8,965 Universally Optimal Privacy Mechanisms for Minimax Agents 2010 PODS 4.4196402e-05
9,513 Multi-Analyst Differential Privacy for Online Query Answering 2023 VLDB 4.3335882e-05
10,346 Differentially Private Substring and Document Counting 2025 PODS 4.1945683e-05
10,348 Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy 2025 PODS 4.1945683e-05
10,480 Efficient and Accurate Differentially Private Cardinality Continual Releases 2025 SIGMOD 4.1945683e-05
10,664 Calibrating Noise for Group Privacy in Subsampled Mechanisms 2025 VLDB 4.1945683e-05
10,759 PrivAGM: Secure Construction of Differentially Private Directed Attributed Graph Models on Decentralized Social Graphs 2025 VLDB 4.1945683e-05
11,260 Epistemic Parity: Reproducibility as an Evaluation Metric for Differential Privacy 2023 VLDB 4.1945683e-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
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