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.00042381562
Overall Rank
137 | 99.05%
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.00047047599
305 On the Complexity of Optimal K-Anonymity 2004 PODS 0.00028264843
567 Practical Privacy: The SuLQ Framework 2005 PODS 0.00019940193
714 Understanding Hierarchical Methods for Differentially Private Histograms 2013 VLDB 0.00017670757
1,463 No Free Lunch in Data Privacy 2011 SIGMOD 0.00011856229
1,566 PrivBasis: Frequent Itemset Mining with Differential Privacy 2012 VLDB 0.00011324162
1,639 Injecting Utility into Anonymized Datasets 2006 SIGMOD 0.00011049413
1,740 PrivateSQL: A Differentially Private SQL Query Engine 2019 VLDB 0.00010696383
1,760 The Boundary Between Privacy and Utility in Data Publishing 2007 VLDB 0.00010641674
1,935 Marginal Release Under Local Differential Privacy 2018 SIGMOD 0.00010033955
2,061 Low-Rank Mechanism: Optimizing Batch Queries under Differential Privacy 2012 VLDB 9.6578455e-05
2,116 Two Can Keep a Secret: A Distributed Architecture for Secure Database Services 2005 CIDR 9.5135165e-05
2,579 Simulatable Auditing 2005 PODS 8.5010694e-05
2,629 Epistemic Privacy 2008 PODS 8.4237864e-05
2,656 Personalized Privacy Preservation 2006 SIGMOD 8.3636527e-05
2,757 Understanding the Sparse Vector Technique for Differential Privacy 2017 VLDB 8.1670378e-05
2,900 Pan-private Algorithms Via Statistics on Sketches 2011 PODS 7.9455873e-05
3,103 Publishing Set-Valued Data via Differential Privacy 2011 VLDB 7.5578714e-05
3,178 Bayesian Differential Privacy on Correlated Data 2015 SIGMOD 7.4350161e-05
3,264 Towards Robustness in Query Auditing 2006 VLDB 7.3073465e-05
3,332 AIM: An Adaptive and Iterative Mechanism for Differentially Private Synthetic Data 2022 VLDB 7.2086982e-05
3,769 Output Perturbation with Query Relaxation 2008 VLDB 6.7744696e-05
3,844 Privacy via Pseudorandom Sketches 2006 PODS 6.7044812e-05
4,185 Towards an Axiomatization of Statistical Privacy and Utility 2010 PODS 6.3713506e-05
5,264 PrivLava: Synthesizing Relational Data with Foreign Keys under Differential Privacy 2023 SIGMOD 5.5951175e-05
5,552 Differential Privacy in the Wild: A tutorial on current practices & open challenges 2016 VLDB 5.4413452e-05
5,700 Differential Privacy in the Wild: A Tutorial on Current Practices & Open Challenges 2017 SIGMOD 5.3655082e-05
5,784 Federated Matrix Factorization with Privacy Guarantee 2022 VLDB 5.3259797e-05
6,511 Provenance Views for Module Privacy 2011 PODS 5.0273291e-05
6,692 Information Preservation in Statistical Privacy and Bayesian Estimation of Unattributed Histograms 2013 SIGMOD 4.9568011e-05
6,916 Private Incremental Regression 2017 PODS 4.8878659e-05
6,969 Architecting a Differentially Private SQL Engine 2019 CIDR 4.8749348e-05
7,194 Longshot: Indexing Growing Databases using MPC and Differential Privacy 2023 VLDB 4.7990411e-05
7,249 CALYPSO: Private Data Management for Decentralized Ledgers 2021 VLDB 4.7841001e-05
7,475 Privacy-Enhancing k-Anonymization of Customer Data 2005 PODS 4.714352e-05
7,501 PSynDB: Accurate and Accessible Private Data Generation 2019 VLDB 4.7135369e-05
7,620 Budget Sharing for Multi-Analyst Differential Privacy 2021 VLDB 4.6896122e-05
8,000 Optimizing Fitness-For-Use of Differentially Private Linear Queries 2021 VLDB 4.6061476e-05
8,349 To Do or Not To Do: The Dilemma of Disclosing Anonymized Data 2005 SIGMOD 4.5343355e-05
8,608 PreFair: Privately Generating Justifiably Fair Synthetic Data 2023 VLDB 4.4810982e-05
8,791 Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation 2008 SIGMOD 4.4459403e-05
8,935 Preserving Privacy and Fairness in Peer-to-Peer Data Integration 2010 SIGMOD 4.4229886e-05
8,971 Universally Optimal Privacy Mechanisms for Minimax Agents 2010 PODS 4.4154104e-05
9,514 Multi-Analyst Differential Privacy for Online Query Answering 2023 VLDB 4.3294349e-05
10,358 Differentially Private Substring and Document Counting 2025 PODS 4.1905499e-05
10,360 Fully Dynamic Algorithms for Graph Databases with Edge Differential Privacy 2025 PODS 4.1905499e-05
10,490 Efficient and Accurate Differentially Private Cardinality Continual Releases 2025 SIGMOD 4.1905499e-05
10,672 Calibrating Noise for Group Privacy in Subsampled Mechanisms 2025 VLDB 4.1905499e-05
10,765 PrivAGM: Secure Construction of Differentially Private Directed Attributed Graph Models on Decentralized Social Graphs 2025 VLDB 4.1905499e-05
11,262 Epistemic Parity: Reproducibility as an Evaluation Metric for Differential Privacy 2023 VLDB 4.1905499e-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.00074213516
84 Statistical Databases: Characteristics, Problems, and Some Solutions 1982 VLDB 0.00053684302
148 On the Design and Quantification of Privacy Preserving Data Mining Algorithms 2001 PODS 0.00041196325
563 An Analytic Approach to Statistical Databases 1983 VLDB 0.00020005703
1,504 Auditing Boolean Attributes 2000 PODS 0.00011607327
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
567 Practical Privacy: The SuLQ Framework 2005 PODS 0.00019940193
12,625 Privacy in Data Systems 2003 PODS 4.1905499e-05
1,928 A Data- and Workload-Aware Algorithm for Range Queries Under Differential Privacy 2014 VLDB 0.00010062105
4,795 Optimal Random Perturbation at Multiple Privacy Levels 2009 VLDB 5.9104664e-05
3,844 Privacy via Pseudorandom Sketches 2006 PODS 6.7044812e-05
8,791 Dynamic Anonymization: Accurate Statistical Analysis with Privacy Preservation 2008 SIGMOD 4.4459403e-05
8,950 Non-Reversible Privacy Transformations 1982 PODS 4.4209796e-05
3,264 Towards Robustness in Query Auditing 2006 VLDB 7.3073465e-05
12,112 The Power of the Dinur-Nissim Algorithm: Breaking Privacy of Statistical and Graph Databases 2012 PODS 4.1905499e-05
3,769 Output Perturbation with Query Relaxation 2008 VLDB 6.7744696e-05