research-article

Fingerprinting codes and the price of approximate differential privacy

Authors:

Jonathan Ullman,

Salil VadhanAuthors Info & Claims

STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

Pages 1 - 10

https://doi.org/10.1145/2591796.2591877

Published: 31 May 2014 Publication History

Abstract

We show new lower bounds on the sample complexity of (ε, δ)-differentially private algorithms that accurately answer large sets of counting queries. A counting query on a database D ∈ ({0, 1}^d)ⁿ has the form "What fraction of the individual records in the database satisfy the property q?" We show that in order to answer an arbitrary set Q of » nd counting queries on D to within error ±α it is necessary that

[EQUATION]

This bound is optimal up to poly-logarithmic factors, as demonstrated by the Private Multiplicative Weights algorithm (Hardt and Rothblum, FOCS'10). It is also the first to show that the sample complexity required for (ε, δ)-differential privacy is asymptotically larger than what is required merely for accuracy, which is O(log |Q|/α²). In addition, we show that our lower bound holds for the specific case of k-way marginal queries (where |Q| = 2^k(d/k)) when α is a constant.

Our results rely on the existence of short fingerprinting codes (Boneh and Shaw, CRYPTO'95; Tardos, STOC'03), which we show are closely connected to the sample complexity of differentially private data release. We also give a new method for combining certain types of sample complexity lower bounds into stronger lower bounds.

Supplementary Material

MP4 File (p1-sidebyside.mp4)

Download
225.50 MB

References

[1]

Barak, B., Chaudhuri, K., Dwork, C., Kale, S., McSherry, F., and Talwar, K. Privacy, accuracy, and consistency too: a holistic solution to contingency table release. In PODS (2007), pp. 273--282.

Digital Library

[2]

Beimel, A., Kasiviswanathan, S. P., and Nissim, K. Bounds on the sample complexity for private learning and private data release. In TCC (2010), pp. 437--454.

Digital Library

[3]

Beimel, A., Nissim, K., and Stemmer, U. Characterizing the sample complexity of private learners. In ITCS (2013), pp. 97--110.

Digital Library

[4]

Beimel, A., Nissim, K., and Stemmer, U. Private learning and sanitization: Pure vs. approximate differential privacy. In APPROX-RANDOM (2013), pp. 363--378.

[5]

Blum, A., Dwork, C., McSherry, F., and Nissim, K. Practical privacy: the SuLQ framework. In PODS (2005), pp. 128--138.

Digital Library

[6]

Blum, A., Ligett, K., and Roth, A. A learning theory approach to noninteractive database privacy. In STOC (2008), pp. 609--618.

Digital Library

[7]

Boneh, D., Kiayias, A., and Montgomery, H. W. Robust fingerprinting codes: a near optimal construction. In Digital Rights Management Workshop (2010), pp. 3--12.

Digital Library

[8]

Boneh, D., and Naor, M. Traitor tracing with constant size ciphertext. In ACM Conference on Computer and Communications Security (2008), pp. 501--510.

Digital Library

[9]

Boneh, D., and Shaw, J. Collusion-secure fingerprinting for digital data. IEEE Transactions on Information Theory 44, 5 (1998), 1897--1905.

Digital Library

[10]

Chandrasekaran, K., Thaler, J., Ullman, J., and Wan, A. Faster private release of marginals on small databases. ITCS 2014 (to appear) (2014).

Digital Library

[11]

De, A. Lower bounds in differential privacy. In TCC (2012), pp. 321--338.

Digital Library

[12]

Dinur, I., and Nissim, K. Revealing information while preserving privacy. In PODS (2003), pp. 202--210.

Digital Library

[13]

Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., and Naor, M. Our data, ourselves: Privacy via distributed noise generation. In EUROCRYPT (2006), pp. 486--503.

Digital Library

[14]

Dwork, C., McSherry, F., Nissim, K., and Smith, A. Calibrating noise to sensitivity in private data analysis. In TCC (2006), pp. 265--284.

Digital Library

[15]

Dwork, C., McSherry, F., and Talwar, K. The price of privacy and the limits of lp decoding. In STOC (2007), pp. 85--94.

Digital Library

[16]

Dwork, C., Naor, M., Reingold, O., Rothblum, G. N., and Vadhan, S. P. On the complexity of differentially private data release: efficient algorithms and hardness results. In STOC (2009), pp. 381--390.

Digital Library

[17]

Dwork, C., Nikolov, A., and Talwar, K. Efficient algorithms for privately releasing marginals via convex programming. Manuscript (2013).

[18]

Dwork, C., and Nissim, K. Privacy-preserving datamining on vertically partitioned databases. In CRYPTO (2004), pp. 528--544.

[19]

Dwork, C., Rothblum, G. N., and Vadhan, S. P. Boosting and differential privacy. In FOCS (2010), pp. 51--60.

Digital Library

[20]

Dwork, C., and Yekhanin, S. New efficient attacks on statistical disclosure control mechanisms. In CRYPTO (2008), pp. 469--480.

Digital Library

[21]

Gupta, A., Hardt, M., Roth, A., and Ullman, J. Privately releasing conjunctions and the statistical query barrier. In STOC (2011), pp. 803--812.

Digital Library

[22]

Gupta, A., Roth, A., and Ullman, J. Iterative constructions and private data release. In TCC (2012), pp. 339--356.

Digital Library

[23]

Hardt, M. A Study in Privacy and Fairness in Sensitive Data Analysis. PhD thesis, Princeton University, 2011.

Digital Library

[24]

Hardt, M., Ligett, K., and McSherry, F. A simple and practical algorithm for differentially private data release. In NIPS (2012), pp. 2348--2356.

Digital Library

[25]

Hardt, M., and Rothblum, G. N. A multiplicative weights mechanism for privacy-preserving data analysis. In FOCS (2010), pp. 61--70.

Digital Library

[26]

Hardt, M., and Talwar, K. On the geometry of differential privacy. In STOC (2010), pp. 705--714.

Digital Library

[27]

Kasiviswanathan, S. P., Rudelson, M., Smith, A., and Ullman, J. The price of privately releasing contingency tables and the spectra of random matrices with correlated rows. In STOC (2010), pp. 775--784.

Digital Library

[28]

Nikolov, A., Talwar, K., and Zhang, L. The geometry of differential privacy: the sparse and approximate cases. In STOC (2013), pp. 351--360.

Digital Library

[29]

Roth, A. Differential privacy and the fat-shattering dimension of linear queries. In APPROX-RANDOM (2010), pp. 683--695.

Digital Library

[30]

Roth, A., and Roughgarden, T. Interactive privacy via the median mechanism. In STOC (2010), pp. 765--774.

Digital Library

[31]

Tardos, G. Optimal probabilistic fingerprint codes. J. ACM 55, 2 (2008).

Digital Library

[32]

Thaler, J., Ullman, J., and Vadhan, S. P. Faster algorithms for privately releasing marginals. In ICALP (1) (2012), pp. 810--821.

Digital Library

[33]

Ullman, J. Answering n^2+o(1) counting queries with differential privacy is hard. In STOC (2013), pp. 361--370.

Digital Library

Cited By

Azize ABasu D(2024)Concentrated Differential Privacy for Bandits2024 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)10.1109/SaTML59370.2024.00013(78-109)Online publication date: 9-Apr-2024
https://doi.org/10.1109/SaTML59370.2024.00013
Girgis ADiggavi S(2024)Multi-Message Shuffled Privacy in Federated LearningIEEE Journal on Selected Areas in Information Theory10.1109/JSAIT.2024.33662255(12-27)Online publication date: 2024
https://doi.org/10.1109/JSAIT.2024.3366225
Livni ROh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Information theoretic lower bounds for information theoretic upper boundsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667762(37716-37727)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667762
Show More Cited By

Index Terms

Fingerprinting codes and the price of approximate differential privacy
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

On the geometry of differential privacy
STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

We consider the noise complexity of differentially private mechanisms in the setting where the user asks d linear queries f:Rⁿ -> R non-adaptively. Here, the database is represented by a vector in R and proximity between databases is measured in the l₁-...
Fingerprinting Codes and the Price of Approximate Differential Privacy

We show new information-theoretic lower bounds on the sample complexity of $(\varepsilon, \delta)$-differentially private algorithms that accurately answer large sets of counting queries. A counting query on a database $D \in (\{0,1\}^d)^n$ has the form “...
Answering n_{2+o(1)} counting queries with differential privacy is hard
STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

A central problem in differentially private data analysis is how to design efficient algorithms capable of answering large numbers of counting queries on a sensitive database. Counting queries are of the form "What fraction of individual records in the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '14: Proceedings of the forty-sixth annual ACM symposium on Theory of computing

May 2014

984 pages

ISBN:9781450327107

DOI:10.1145/2591796

Program Chair:
David Shmoys
Cornell University

Copyright © 2014 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2014

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Division of Computer and Network Systems
Simons Foundation
NDSEG Fellowship
Google

Conference

STOC '14

Sponsor:

SIGACT

STOC '14: Symposium on Theory of Computing

May 31 - June 3, 2014

New York, New York

Acceptance Rates

STOC '14 Paper Acceptance Rate 91 of 319 submissions, 29%;

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

47
Total Citations
View Citations
680
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)6

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Azize ABasu D(2024)Concentrated Differential Privacy for Bandits2024 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML)10.1109/SaTML59370.2024.00013(78-109)Online publication date: 9-Apr-2024
https://doi.org/10.1109/SaTML59370.2024.00013
Girgis ADiggavi S(2024)Multi-Message Shuffled Privacy in Federated LearningIEEE Journal on Selected Areas in Information Theory10.1109/JSAIT.2024.33662255(12-27)Online publication date: 2024
https://doi.org/10.1109/JSAIT.2024.3366225
Livni ROh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Information theoretic lower bounds for information theoretic upper boundsProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3667762(37716-37727)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3667762
Allouah YGuerraoui RGupta NPinot RStephan JKrause ABrunskill ECho KEngelhardt BSabato SScarlett J(2023)On the privacy-robustness-utility trilemma in distributed learningProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3618435(569-626)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.5555/3618408.3618435
Xiao HWan JDevadas SMeng WJensen CCremers CKirda E(2023)Geometry of Sensitivity: Twice Sampling and Hybrid Clipping in Differential Privacy with Optimal Gaussian Noise and Application to Deep LearningProceedings of the 2023 ACM SIGSAC Conference on Computer and Communications Security10.1145/3576915.3623142(2636-2650)Online publication date: 15-Nov-2023
https://dl.acm.org/doi/10.1145/3576915.3623142
Alabi DKothari PTankala PVenkat PZhang FSaha BServedio R(2023)Privately Estimating a Gaussian: Efficient, Robust, and OptimalProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585194(483-496)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585194
Dinur IStemmer UWoodruff DZhou S(2023)On Differential Privacy and Adaptive Data Analysis with Bounded SpaceAdvances in Cryptology – EUROCRYPT 202310.1007/978-3-031-30620-4_2(35-65)Online publication date: 15-Apr-2023
https://doi.org/10.1007/978-3-031-30620-4_2
Kamath GMouzakis ASinghal VKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)New lower bounds for private estimation and a generalized fingerprinting lemmaProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3602042(24405-24418)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3602042
Cai TWang YZhang L(2021)The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacyThe Annals of Statistics10.1214/21-AOS205849:5Online publication date: 1-Oct-2021
https://doi.org/10.1214/21-AOS2058
Cheu AUllman JKhuller SVassilevska Williams V(2021)The limits of pan privacy and shuffle privacy for learning and estimationProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing10.1145/3406325.3450995(1081-1094)Online publication date: 15-Jun-2021
https://dl.acm.org/doi/10.1145/3406325.3450995
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents