skip to main content
10.1145/1807085.1807105acmconferencesArticle/Chapter ViewAbstractPublication PagespodsConference Proceedingsconference-collections
research-article

Universally optimal privacy mechanisms for minimax agents

Published: 06 June 2010 Publication History

Abstract

A scheme that publishes aggregate information about sensitive data must resolve the trade-off between utility to information consumers and privacy of the database participants. Differential privacy [5] is a well-established definition of privacy--this is a universal guarantee against all attackers, whatever their side-information or intent. Can we have a similar universal guarantee for utility?
There are two standard models of utility considered in decision theory: Bayesian and minimax [13]. Ghosh et. al. [8] show that a certain "geometric mechanism" gives optimal utility to all Bayesian information consumers. In this paper, we prove a similar result for minimax information consumers. Our result also works for a wider class of information consumers which includes Bayesian information consumers and subsumes the result from [8].
We model information consumers as minimax (risk-averse) agents, each endowed with a loss-function which models their tolerance to inaccuracies and each possessing some side-information about the query. Further, information consumers are rational in the sense that they actively combine information from the mechanism with their side-information in a way that minimizes their loss. Under this assumption of rational behavior, we show that for every fixed count query, the geometric mechanism is universally optimal for all minimax information consumers.
Additionally, our solution makes it possible to release query results, when information consumers are at different levels of privacy, in a collusion-resistant manner.

References

[1]
A. Blum, K. Ligett, and A. Roth. A learning theory approach to non-interactive database privacy. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pages 609--618, 2008.
[2]
I. Dinur and Nissim K. Revealing information while preserving privacy. In Proceedings of the 22nd ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pages 202--210, 2003.
[3]
C. Dwork. Differential privacy. In Proceedings of the 33rd Annual International Colloquium on Automata, Languages, and Programming (ICALP), volume 4051 of Lecture Notes in Computer Science, pages 1--12, 2006.
[4]
C. Dwork. Differential privacy: A survey of results. In 5th International Conference on Theory and Applications of Models of Computation (TAMC), volume 4978 of Lecture Notes in Computer Science, pages 1--19, 2008.
[5]
C. Dwork, F. McSherry, K. Nissim, and A. Smith. Calibrating noise to sensitivity in private data analysis. In Third Theory of Cryptography Conference (TCC), volume 3876 of Lecture Notes in Computer Science, pages 265--284, 2006.
[6]
C. Dwork, F. McSherry, and K. Talwar. The price of privacy and the limits of LP decoding. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 85--94, 2007.
[7]
C. Dwork and K. Nissim. Privacy-preserving datamining on vertically partitioned databases. In 24th Annual International Cryptology Conference (CRYPTO), volume 3152 of Lecture Notes in Computer Science, pages 528--544, 2004.
[8]
A. Ghosh, T. Roughgarden, and M. Sundararajan. Universally utility-maximizing privacy mechanisms. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC), pages 351--360, 2009.
[9]
M. Hardt and K. Talwar. On the geometry of differential privacy. In CoRR abs/0907.3754, 2009.
[10]
M. Hay, V. Rastogi, G. Miklau, and D. Suciu. Boosting the accuracy of differentially-private queries through consistency. In To appear in 36th International Conference on Very Large Databases (VLDB), 2010.
[11]
S. P. Kasiviswanathan, H. K. Lee, K. Nissim, S. Raskhodnikova, and A. Smith. What can we learn privately? In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 531--540, 2008.
[12]
S. P. Kasiviswanathan and A. Smith. A note on differential privacy: Defining resistance to arbitrary side information. http://arxiv.org/abs/0803.3946v1, 2008.
[13]
Graham Loomes and Robert Sugden. Regret theory: An alternative theory of rational choice under uncertainty. Economic Journal, 92(368):805--24, December 1982.
[14]
A. Mas-Colell, M. D. Whinston, and J. R. Green. Microeconomic Theory. Oxford University Press, New York, 1995.
[15]
F. McSherry and K. Talwar. Mechanism design via differential privacy. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 94--103, 2007.
[16]
A. Narayanan and V. Shmatikov. Robust de-anonymization of large sparse datasets. In Proceedings of the 2008 IEEE Symposium on Security and Privacy (SP), pages 111--125, 2008.
[17]
K. Nissim, S. Raskhodnikova, and A. Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC), pages 75--84, 2007.
[18]
California Department of Public Health. H1n1 flu-data tables. http://www.cdph.ca.gov/HealthInfo/discond/Documents/ H1N1-Data-Table-CA-Cases-by-County-102409.pdf, October 2009.
[19]
D. G. Poole. The stochastic group. American Mathematical Monthly, 102(798--801), 1995.
[20]
L. Sweeney. k-anonymity: a model for protecting privacy. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10(5):557--570, 2002.
[21]
Wikipedia. AOL search data scandal. http://en.wikipedia.org/wiki/AOL_search_data_scandal.
[22]
M. Wu, W. Trappe, Z. Jane Wang, and K.J. Ray Liu. Collusion-resistant fingerprinting for multimedia. IEEE Signal Processing Magazine, 21(2):15 -- 27, 2004.
[23]
X. Xiao, Y. Tao, and M. Chen. Optimal random perturbation at multiple privacy levels. In 35th International Conference on Very Large Databases (VLDB), pages 814--825, 2009.

Cited By

View all
  • (2024)Budget Recycling Differential Privacy2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00212(1028-1046)Online publication date: 19-May-2024
  • (2024)Discrete Offset-Symmetric Gaussians for Differential PrivacyIEEE Signal Processing Letters10.1109/LSP.2024.343195131(1915-1919)Online publication date: 2024
  • (2023)Universal optimality and robust utility bounds for metric differential privacy1Journal of Computer Security10.3233/JCS-23003631:5(539-580)Online publication date: 13-Oct-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
PODS '10: Proceedings of the twenty-ninth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
June 2010
350 pages
ISBN:9781450300339
DOI:10.1145/1807085
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: 06 June 2010

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. decision theory
  2. differential privacy
  3. linear algebra
  4. minimax
  5. universally optimal privacy

Qualifiers

  • Research-article

Conference

SIGMOD/PODS '10
Sponsor:
SIGMOD/PODS '10: International Conference on Management of Data
June 6 - 11, 2010
Indiana, Indianapolis, USA

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)12
  • Downloads (Last 6 weeks)2
Reflects downloads up to 22 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Budget Recycling Differential Privacy2024 IEEE Symposium on Security and Privacy (SP)10.1109/SP54263.2024.00212(1028-1046)Online publication date: 19-May-2024
  • (2024)Discrete Offset-Symmetric Gaussians for Differential PrivacyIEEE Signal Processing Letters10.1109/LSP.2024.343195131(1915-1919)Online publication date: 2024
  • (2023)Universal optimality and robust utility bounds for metric differential privacy1Journal of Computer Security10.3233/JCS-23003631:5(539-580)Online publication date: 13-Oct-2023
  • (2023)Quantitative Information Flow Techniques for Studying Optimality in Differential PrivacyACM SIGLOG News10.1145/3584676.358468010:1(4-22)Online publication date: 14-Feb-2023
  • (2023)Differential Private Discrete Noise-Adding Mechanism: Conditions, Properties, and OptimizationIEEE Transactions on Signal Processing10.1109/TSP.2023.331764471(3534-3547)Online publication date: 2023
  • (2023)Optimal Multidimensional Differentially Private Mechanisms in the Large-Composition Regime2023 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT54713.2023.10206658(2195-2200)Online publication date: 25-Jun-2023
  • (2023)Variations and Extensions of Information Leakage Metrics with Applications to Privacy Problems with Imperfect Statistical Information2023 IEEE 36th Computer Security Foundations Symposium (CSF)10.1109/CSF57540.2023.00007(407-422)Online publication date: Jul-2023
  • (2022)L-SRRProceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security10.1145/3548606.3560636(2809-2823)Online publication date: 7-Nov-2022
  • (2022)Cactus Mechanisms: Optimal Differential Privacy Mechanisms in the Large-Composition Regime2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834438(1838-1843)Online publication date: 26-Jun-2022
  • (2022)Universal Optimality and Robust Utility Bounds for Metric Differential Privacy2022 IEEE 35th Computer Security Foundations Symposium (CSF)10.1109/CSF54842.2022.9919647(348-363)Online publication date: Aug-2022
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media