The DOI matches its Crossref record; 17 of the 17 references it cites were found in a registry or an index.
Practical privacy: the SuLQ framework
Abstract
We consider a statistical database in which a trusted administrator introduces noise to the query responses with the goal of maintaining privacy of individual database entries. In such a database, a query consists of a pair (S, f) where S is a set of rows in the database and f is a function mapping database rows to {0, 1}. The true answer is ΣiεS f(di), and a noisy version is released as the response to the query. Results of Dinur, Dwork, and Nissim show that a strong form of privacy can be maintained using a surprisingly small amount of noise -- much less than the sampling error -- provided the total number of queries is sublinear in the number of database rows. We call this query and (slightly) noisy reply the SuLQ (Sub-Linear Queries) primitive. The assumption of sublinearity becomes reasonable as databases grow increasingly large.We extend this work in two ways. First, we modify the privacy analysis to real-valued functions f and arbitrary row types, as a consequence greatly improving the bounds on noise required for privacy. Second, we examine the computational power of the SuLQ primitive. We show that it is very powerful indeed, in that slightly noisy versions of the following computations can be carried out with very few invocations of the primitive: principal component analysis, k means clustering, the Perceptron Algorithm, the ID3 algorithm, and (apparently!) all algorithms that operate in the in the statistical query learning model [11].
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Quinlan, J. R. (1986) · Machine Learning · doi:10.1007/bf00116251 · Cited by 21,439
Information theory, inference, and learning algorithms
(2004) · Choice Reviews Online · doi:10.5860/choice.41-5949 · Cited by 6,362
Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems
Kocher, P. C. (1996) · Lecture Notes in Computer Science · doi:10.1007/3-540-68697-5_9 · Cited by 4,387
ASH, R. B. (1966) · Cited by 3,990
Privacy-preserving data mining
Agrawal, R., & Srikant, R. (2000) · ACM SIGMOD Record · doi:10.1145/335191.335438 · Cited by 2,961
Privacy-preserving data mining
Agrawal, R., & Srikant, R. (2000) · Proceedings of the 2000 ACM SIGMOD international conference on Management of data · doi:10.1145/342009.335438 · Cited by 1,719
Privacy Preserving Data Mining
Lindell, Y., & Pinkas, B. (2000) · Lecture Notes in Computer Science · doi:10.1007/3-540-44598-6_3 · Cited by 1,077
On the design and quantification of privacy preserving data mining algorithms
Agrawal, D., & Aggarwal, C. C. (2001) · Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/375551.375602 · Cited by 1,006
Revealing information while preserving privacy
Dinur, I., & Nissim, K. (2003) · Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/773153.773173 · Cited by 980
Self-citationSecurity-control methods for statistical databases: a comparative study
Adam, N. R., & Worthmann, J. C. (1989) · ACM Computing Surveys · doi:10.1145/76894.76895 · Cited by 969
Cited by
Calibrating Noise to Sensitivity in Private Data Analysis
Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_14 · Cited by 7,272
Self-citationDwork, C. (2006) · Lecture Notes in Computer Science · doi:10.1007/11787006_1 · Cited by 5,291
Self-citationThe Algorithmic Foundations of Differential Privacy
Dwork, C., & Roth, A. (2013) · doi:10.1561/9781601988195 · Cited by 3,856
Self-citationL -diversity: Privacy beyond k -anonymity
Machanavajjhala, A., Kifer, D., Gehrke, J., & Venkitasubramaniam, M. (2007) · ACM Transactions on Knowledge Discovery from Data · doi:10.1145/1217299.1217302 · Cited by 3,617
Differential Privacy: A Survey of Results
Dwork, C. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-79228-4_1 · Cited by 3,542
“…and from such diverse branches of computer science as algorithms, database theory, and cryptography , for example as in [3] [4] [21] [22] [23] [33] [34] [41] [48], [1] [24] [25] [31], and [6] [9] [11] [12] [13] [18] [7] [19]; see also the survey [2] for a summary of the field prior to 1989.”
Self-citationFederated Learning With Differential Privacy: Algorithms and Performance Analysis
Wei, K., Li, J., Ding, M., Ma, C., Yang, H. H., Farokhi, F., Jin, S., Quek, T. Q. S., & Vincent Poor, H. (2020) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2020.2988575 · Cited by 2,400
Robust De-anonymization of Large Sparse Datasets
Narayanan, A., & Shmatikov, V. (2008) · 2008 IEEE Symposium on Security and Privacy (sp 2008) · doi:10.1109/sp.2008.33 · Cited by 2,372
L-diversity: privacy beyond k-anonymity
Machanavajjhala, A., Gehrke, J., Kifer, D., & Venkitasubramaniam, M. (2006) · 22nd International Conference on Data Engineering (ICDE'06) · doi:10.1109/icde.2006.1 · Cited by 2,362
Our Data, Ourselves: Privacy Via Distributed Noise Generation
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., & Naor, M. (2006) · Lecture Notes in Computer Science · doi:10.1007/11761679_29 · Cited by 1,835
“A slightly different definition of privacy was used in [14, 4].”
InfluentialSelf-citationPrivacy-preserving data publishing: A survey of recent developments
Fung, B. C. M., Wang, K., Chen, R., & Yu, P. S. (2010) · ACM Computing Surveys · doi:10.1145/1749603.1749605 · Cited by 1,704
Mechanism Design via Differential Privacy
McSherry, F., & Talwar, K. (2007) · 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) · doi:10.1109/focs.2007.66 · Cited by 1,371
Self-citationTowards Sharp Inapproximability For Any 2-CSP
Austrin, P. (2007) · 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07) · doi:10.1109/focs.2007.41 · Cited by 1,294
Huang, L., Joseph, A. D., Nelson, B., Rubinstein, B. I. P., & Tygar, J. D. (2011) · Proceedings of the 4th ACM workshop on Security and artificial intelligence · doi:10.1145/2046684.2046692 · Cited by 1,194
Privacy integrated queries: an extensible platform for privacy-preserving data analysis
McSherry, F. D. (2009) · Proceedings of the 2009 ACM SIGMOD International Conference on Management of data · doi:10.1145/1559845.1559850 · Cited by 1,124
Self-citationSmooth sensitivity and sampling in private data analysis
Nissim, K., Raskhodnikova, S., & Smith, A. (2007) · Proceedings of the thirty-ninth annual ACM symposium on Theory of computing · doi:10.1145/1250790.1250803 · Cited by 974
Self-citationA Hybrid Approach to Privacy-Preserving Federated Learning
Truex, S., Baracaldo, N., Anwar, A., Steinke, T., Ludwig, H., Zhang, R., & Zhou, Y. (2019) · Proceedings of the 12th ACM Workshop on Artificial Intelligence and Security · doi:10.1145/3338501.3357370 · Cited by 1,029
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2011) · SIAM Journal on Computing · doi:10.1137/090756090 · Cited by 898
Self-citationBackstrom, L., Dwork, C., & Kleinberg, J. (2007) · Proceedings of the 16th international conference on World Wide Web · doi:10.1145/1242572.1242598 · Cited by 850
Self-citationA firm foundation for private data analysis
Dwork, C. (2011) · Communications of the ACM · doi:10.1145/1866739.1866758 · Cited by 841
Self-citationBoosting and Differential Privacy
Dwork, C., Rothblum, G. N., & Vadhan, S. (2010) · 2010 IEEE 51st Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2010.12 · Cited by 784
Self-citationDifferentially private recommender systems: Building privacy into the Netflix Prize contenders
McSherry, F., & Mironov, I. (2009) · Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1557019.1557090 · Cited by 664
Self-citationPrivate Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds
Bassily, R., Smith, A., & Thakurta, A. (2014) · 2014 IEEE 55th Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2014.56 · Cited by 621
Kifer, D., & Machanavajjhala, A. (2011) · Proceedings of the 2011 ACM SIGMOD International Conference on Management of data · doi:10.1145/1989323.1989345 · Cited by 619
Differential privacy and robust statistics
Dwork, C., & Lei, J. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536466 · Cited by 611
Self-citationDifferential privacy under continual observation
Dwork, C., Naor, M., Pitassi, T., & Rothblum, G. N. (2010) · Proceedings of the forty-second ACM symposium on Theory of computing · doi:10.1145/1806689.1806787 · Cited by 583
Self-citationDifferentially private aggregation of distributed time-series with transformation and encryption
Rastogi, V., & Nath, S. (2010) · Proceedings of the 2010 ACM SIGMOD International Conference on Management of data · doi:10.1145/1807167.1807247 · Cited by 534
A learning theory approach to non-interactive database privacy
Blum, A., Ligett, K., & Roth, A. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374464 · Cited by 505
Self-citationStochastic gradient descent with differentially private updates
Song, S., Chaudhuri, K., & Sarwate, A. D. (2013) · 2013 IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip.2013.6736861 · Cited by 501
A General Survey of Privacy-Preserving Data Mining Models and Algorithms
Aggarwal, C. C., & Yu, P. S. (2008) · Advances in Database Systems · doi:10.1007/978-0-387-70992-5_2 · Cited by 469
Privacy, accuracy, and consistency too: a holistic solution to contingency table release
Barak, B., Chaudhuri, K., Dwork, C., Kale, S., McSherry, F., & Talwar, K. (2007) · Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems · doi:10.1145/1265530.1265569 · Cited by 468
Self-citationData mining with differential privacy
Friedman, A., & Schuster, A. (2010) · Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1835804.1835868 · Cited by 461
Privacy: Theory meets Practice on the Map
Machanavajjhala, A., Kifer, D., Abowd, J., Gehrke, J., & Vilhuber, L. (2008) · 2008 IEEE 24th International Conference on Data Engineering · doi:10.1109/icde.2008.4497436 · Cited by 435
Measuring Large-Scale Social Networks with High Resolution
Stopczynski, A., Sekara, V., Sapiezynski, P., Cuttone, A., Madsen, M. M., Larsen, J. E., & Lehmann, S. (2014) · PLoS ONE · doi:10.1371/journal.pone.0095978 · Cited by 409
The composition theorem for differential privacy
Kairouz, P., Oh, S., & Viswanath, P. (2017) · IEEE Transactions on Information Theory · doi:10.1109/tit.2017.2685505 · Cited by 408
A Statistical Framework for Differential Privacy
Wasserman, L., & Zhou, S. (2010) · Journal of the American Statistical Association · doi:10.1198/jasa.2009.tm08651 · Cited by 397
Composition attacks and auxiliary information in data privacy
Ganta, S. R., Kasiviswanathan, S. P., & Smith, A. (2008) · Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1401890.1401926 · Cited by 395
Ateniese, G., Mancini, L. V., Spognardi, A., Villani, A., Vitali, D., & Felici, G. (2015) · International Journal of Security and Networks · doi:10.1504/ijsn.2015.071829 · Cited by 395
Airavat: security and privacy for MapReduce
Roy, I., Setty, S., Kilzer, A., Shmatikov, V., & Witchel, E. (2010) · doi:10.5555/1855711.1855731 · Cited by 393
Social Network Analysis and Mining for Business Applications
Bonchi, F., Castillo, C., Gionis, A., & Jaimes, A. (2011) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/1961189.1961194 · Cited by 359
Differentially Private Filtering
Le Ny, J., & Pappas, G. J. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2013.2283096 · Cited by 341
Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2008) · 2008 49th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.27 · Cited by 334
Self-citationDifferentially Private Data Publishing and Analysis: A Survey
Zhu, T., Li, G., Zhou, W., & Yu, P. S. (2017) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2017.2697856 · Cited by 330
The cost of privacy: destruction of data-mining utility in anonymized data publishing
Brickell, J., & Shmatikov, V. (2008) · Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining · doi:10.1145/1401890.1401904 · Cited by 319
On the geometry of differential privacy
Hardt, M., & Talwar, K. (2010) · Proceedings of the forty-second ACM symposium on Theory of computing · doi:10.1145/1806689.1806786 · Cited by 314
Slicing: A New Approach for Privacy Preserving Data Publishing
Li, T., Li, N., Zhang, J., & Molloy, I. (2012) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2010.236 · Cited by 312
Analyzing Graphs with Node Differential Privacy
Kasiviswanathan, S. P., Nissim, K., Raskhodnikova, S., & Smith, A. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-36594-2_26 · Cited by 294
Self-citationA simple and practical algorithm for differentially private data release
Hardt, M., Ligett, K., & McSherry, F. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1012.4763 · Cited by 283
Self-citationDemystifying Membership Inference Attacks in Machine Learning as a Service
Truex, S., Liu, L., Gursoy, M. E., Yu, L., & Wei, W. (2021) · IEEE Transactions on Services Computing · doi:10.1109/tsc.2019.2897554 · Cited by 282
Differential Privacy for Statistics: What we Know and What we Want to Learn
Dwork, C., & Smith, A. (2010) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.v1i2.570 · Cited by 264
Self-citationHow To Break Anonymity of the Netflix Prize Dataset
Narayanan, A., & Shmatikov, V. (2006) · arXiv (Cornell University) · doi:10.48550/arxiv.cs/0610105 · Cited by 263
Learning in a Large Function Space: Privacy-Preserving Mechanisms for SVM Learning
Rubinstein, B. I. P., Bartlett, P. L., Huang, L., & Taft, N. (2012) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.v4i1.612 · Cited by 262
Differentially private grids for geospatial data
Qardaji, W., Yang, W., & Li, N. (2013) · 2013 IEEE 29th International Conference on Data Engineering (ICDE) · doi:10.1109/icde.2013.6544872 · Cited by 260
How Much Is Enough? Choosing ε for Differential Privacy
Lee, J., & Clifton, C. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-24861-0_22 · Cited by 201
Distributed Privacy-Preserving Collaborative Intrusion Detection Systems for VANETs
Zhang, T., & Zhu, Q. (2018) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2018.2801622 · Cited by 168
Generalization in Adaptive Data Analysis and Holdout Reuse
Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., & Roth, A. (2015) · arXiv · doi:10.48550/arxiv.1506.02629 · Cited by 152
Self-citationA Survey on Differentially Private Machine Learning [Review Article]
Gong, M., Xie, Y., Pan, K., Feng, K., & Qin, A. K. (2020) · IEEE Computational Intelligence Magazine · doi:10.1109/mci.2020.2976185 · Cited by 115
InPrivate Digging: Enabling Tree-based Distributed Data Mining with Differential Privacy
Zhao, L., Ni, L., Hu, S., Chen, Y., Zhou, P., Xiao, F., & Wu, L. (2018) · IEEE INFOCOM 2018 - IEEE Conference on Computer Communications · doi:10.1109/infocom.2018.8486352 · Cited by 108
IBM Federated Learning: an Enterprise Framework White Paper V0.1
Ludwig, H., Baracaldo, N., Thomas, G., Zhou, Y., Anwar, A., Rajamoni, S., Ong, Y., Radhakrishnan, J., Verma, A., Sinn, M., et al. (2020) · arXiv · doi:10.48550/arxiv.2007.10987 · Cited by 106
Improved collaborative filtering recommendation algorithm based on differential privacy protection
Yin, C., Shi, L., Sun, R., & Wang, J. (2020) · The Journal of Supercomputing · doi:10.1007/s11227-019-02751-7 · Cited by 90
Learning about the world through long-term query logs
Richardson, M. (2008) · ACM Transactions on the Web · doi:10.1145/1409220.1409224 · Cited by 77
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
Beimel, A., Nissim, K., & Stemmer, U. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40328-6_26 · Cited by 72
Security and Privacy Issues in Deep Learning
Bae, H., Jang, J., Jung, D., Jang, H., Ha, H., Lee, H., & Yoon, S. (2018) · arXiv · doi:10.48550/arxiv.1807.11655 · Cited by 56
CoinPress: Practical Private Mean and Covariance Estimation
Biswas, S., Dong, Y., Kamath, G., & Ullman, J. (2020) · arXiv · doi:10.48550/arxiv.2006.06618 · Cited by 29
On the Power of Multiple Anonymous Messages
Ghazi, B., Golowich, N., Kumar, R., Pagh, R., & Velingker, A. (2019) · arXiv · doi:10.48550/arxiv.1908.11358 · Cited by 26
How Much Is Too Much? Leveraging Ads Audience Estimation to Evaluate Public Profile Uniqueness
Chen, T., Chaabane, A., Tournoux, P. U., Kaafar, M.-A., & Boreli, R. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-39077-7_12 · Cited by 21
“De-anonymization: Multiple studies explored the feasibility of de-anonymizing both statistical databases [2,3] and micro-data [4,20,21].”
BackgroundThe power of the hybrid model for mean estimation
Avent, B., Dubey, Y., & Korolova, A. (2020) · Proceedings on Privacy Enhancing Technologies · doi:10.2478/popets-2020-0062 · Cited by 9
Metadata
- Authors
- Blum, A., Dwork, C., McSherry, F., & Nissim, K.
- Venue
- Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
- Publisher
- ACM
- Published
- 2005-06-13
- Pages
- 128-138
- OpenAlex
- W2010523825
- Cited by
- 797
- References
- 17
- FWCI
- 15.50
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.