research-article

On the complexity of differentially private data release: efficient algorithms and hardness results

Authors:

Guy N. Rothblum,

Salil VadhanAuthors Info & Claims

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

Pages 381 - 390

https://doi.org/10.1145/1536414.1536467

Published: 31 May 2009 Publication History

Abstract

We consider private data analysis in the setting in which a trusted and trustworthy curator, having obtained a large data set containing private information, releases to the public a "sanitization" of the data set that simultaneously protects the privacy of the individual contributors of data and offers utility to the data analyst. The sanitization may be in the form of an arbitrary data structure, accompanied by a computational procedure for determining approximate answers to queries on the original data set, or it may be a "synthetic data set" consisting of data items drawn from the same universe as items in the original data set; queries are carried out as if the synthetic data set were the actual input. In either case the process is non-interactive; once the sanitization has been released the original data and the curator play no further role.

For the task of sanitizing with a synthetic dataset output, we map the boundary between computational feasibility and infeasibility with respect to a variety of utility measures. For the (potentially easier) task of sanitizing with unrestricted output format, we show a tight qualitative and quantitative connection between hardness of sanitizing and the existence of traitor tracing schemes.

References

[1]

A. Blum, K. Ligett, and A. Roth. A learning theory approach to non--interactive database privacy. In STOC, pages 609--618, 2008.

Digital Library

[2]

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

Digital Library

[3]

D. Boneh, A. Sahai, and B. Waters. Fully collusion resistant traitor tracing with short ciphertexts and private keys. In EUROCRYPT, pages 573--592, 2006.

Digital Library

[4]

B. Chor, A. Fiat, and M. Naor. Tracing traitors. In CRYPTO, pages 257--270, 1994.

Digital Library

[5]

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

Digital Library

[6]

C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In S. Halevy and T. Rabin, editors, First Theory of Cryptography Conference (TCC), volume 3876, pages 265--284. Springer-Verlag, 2006.

Digital Library

[7]

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

Digital Library

[8]

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

[9]

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

Digital Library

[10]

D. Feldman, A. Fiat, H. Kaplan, and K. Nissim. Private coresets. These Proceedings, 2009.

Digital Library

[11]

O. Goldreich. The Foundations of Cryptography -- Volume 2. Cambridge University Press, 2004.

Digital Library

[12]

O. Goldreich, S. Goldwasser, and S. Micali. How to construct pseudorandom functions. Journal of the ACM, 33(2):792--807, 1986.

Digital Library

[13]

S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270--299, 1984.

[14]

R. Impagliazzo, R. Jaiswal, V. Kabanets, and A. Wigderson. Uniform direct product theorems: simplified, optimized, and derandomized. In STOC, pages 579--588, 2008.

Digital Library

[15]

P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can we learn privately? In FOCS, pages 1--19, 2008.

Digital Library

[16]

A. Kiayias and M. Yung. Self protecting pirates and black-box traitor tracing. In CRYPTO, pages 63--79, 2001.

Digital Library

[17]

F. McSherry and K. Talwar. Mechanism design via differential privacy. In FOCS, pages 94--103. IEEE Computer Society, 2007.

Digital Library

[18]

M. E. Saks and S. Zhou. Bp space(s) subseteq dspace(s^3/2). J. Comput. Syst. Sci., 58(2):376--403, 1999.

Digital Library

[19]

R. E. Schapire. Theoretical views of boosting and applications. In ATL, pages 13--25, 1999.

Digital Library

[20]

L. G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134--1142, 1984.

Digital Library

Cited By

Zhao PZhang KZhang HChen H(2025)Alternating minimization differential privacy protection algorithm for the novel dual-mode learning tasks modelExpert Systems with Applications10.1016/j.eswa.2024.125279259(125279)Online publication date: Jan-2025
https://doi.org/10.1016/j.eswa.2024.125279
Feng GWang GPeng T(2024)Toward Answering Federated Spatial Range Queries Under Local Differential PrivacyInternational Journal of Intelligent Systems10.1155/2024/24082702024:1Online publication date: 26-Oct-2024
https://doi.org/10.1155/2024/2408270
Cho HFroelicher DDokmai NNandi ASadhuka SHong MBerger B(2024)Privacy-Enhancing Technologies in Biomedical Data ScienceAnnual Review of Biomedical Data Science10.1146/annurev-biodatasci-120423-1201077:1(317-343)Online publication date: 23-Aug-2024
https://doi.org/10.1146/annurev-biodatasci-120423-120107
Show More Cited By

Index Terms

On the complexity of differentially private data release: efficient algorithms and hardness results
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

A differentially private algorithm for location data release

The rise of mobile technologies in recent years has led to large volumes of location information, which are valuable resources for knowledge discovery such as travel patterns mining and traffic analysis. However, location dataset has been confronted ...
Incremental release of differentially-private check-in data

Due to the growing popularity of location-based services and geo-social networks, users communicate more and more private location traces to service providers, as well as explicit spatio-temporal data, often called "check-ins", about their presence in ...
Differentially private data publishing via optimal univariate microaggregation and record perturbation
Abstract
We present an approach to generate differentially private data sets that consists in adding noise to a microaggregated version of the original data set. While this idea has already been pursued in the literature to reduce the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '09: Proceedings of the forty-first annual ACM symposium on Theory of computing

May 2009

750 pages

ISBN:9781605585062

DOI:10.1145/1536414

Program Chair:
Michael Mitzenmacher
Harvard University

Copyright © 2009 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 31 May 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC '09

Sponsor:

STOC '09: Symposium on Theory of Computing

May 31 - June 2, 2009

MD, Bethesda, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

224
Total Citations
View Citations
1,139
Total Downloads

Downloads (Last 12 months)102
Downloads (Last 6 weeks)16

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhao PZhang KZhang HChen H(2025)Alternating minimization differential privacy protection algorithm for the novel dual-mode learning tasks modelExpert Systems with Applications10.1016/j.eswa.2024.125279259(125279)Online publication date: Jan-2025
https://doi.org/10.1016/j.eswa.2024.125279
Feng GWang GPeng T(2024)Toward Answering Federated Spatial Range Queries Under Local Differential PrivacyInternational Journal of Intelligent Systems10.1155/2024/24082702024:1Online publication date: 26-Oct-2024
https://doi.org/10.1155/2024/2408270
Cho HFroelicher DDokmai NNandi ASadhuka SHong MBerger B(2024)Privacy-Enhancing Technologies in Biomedical Data ScienceAnnual Review of Biomedical Data Science10.1146/annurev-biodatasci-120423-1201077:1(317-343)Online publication date: 23-Aug-2024
https://doi.org/10.1146/annurev-biodatasci-120423-120107
Dong WFang JYi KTao YMachanavajjhala A(2024)Instance-optimal Truncation for Differentially Private Query Evaluation with Foreign KeysACM Transactions on Database Systems10.1145/369783149:4(1-40)Online publication date: 26-Sep-2024
https://dl.acm.org/doi/10.1145/3697831
Biswas ACormode GKanza YSrivastava DZhou Z(2024)Differentially Private Hierarchical Heavy HittersProceedings of the ACM on Management of Data10.1145/36958262:5(1-25)Online publication date: 7-Nov-2024
https://dl.acm.org/doi/10.1145/3695826
Rosenblatt LHerman BHolovenko ALee WLoftus JMcKinnie ERumezhak TStadnik AHowe BStoyanovich J(2024)Epistemic Parity: Reproducibility as an Evaluation Metric for Differential PrivacyACM SIGMOD Record10.1145/3665252.366526753:1(65-74)Online publication date: 14-May-2024
https://dl.acm.org/doi/10.1145/3665252.3665267
Dong WChen ZLuo QShi EYi K(2024)Continual Observation of Joins under Differential PrivacyProceedings of the ACM on Management of Data10.1145/36549312:3(1-27)Online publication date: 30-May-2024
https://dl.acm.org/doi/10.1145/3654931
Zhang YLiang XDu RTian J(2024)DP-Discriminator: A Differential Privacy Evaluation Tool Based on GANProceedings of the 21st ACM International Conference on Computing Frontiers10.1145/3649153.3649211(285-293)Online publication date: 7-May-2024
https://dl.acm.org/doi/10.1145/3649153.3649211
Jia JLi XLi TLiu ZTan CLv SGuo LDong CLiu Z(2024)ABSyn: An Accurate Differentially Private Data Synthesis Scheme With Adaptive Selection and Batch ProcessesIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.345317519(8338-8352)Online publication date: 2024
https://doi.org/10.1109/TIFS.2024.3453175
Jain PSmith AWagaman C(2024)Time-Aware Projections: Truly Node-Private Graph Statistics under Continual Observation*2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00196(127-145)Online publication date: 19-May-2024
https://doi.org/10.1109/SP54263.2024.00196
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