Document Open Access Logo

Privately Answering Counting Queries with Generalized Gaussian Mechanisms

Authors Arun Ganesh, Jiazheng Zhao

PDF
Thumbnail PDF

File

LIPIcs.FORC.2021.1.pdf
  • Filesize: 0.75 MB
  • 18 pages

Document Identifiers

Author Details

Arun Ganesh
  • Department of Electrical Engineering and Computer Sciences, University of California at Berkeley, CA, USA
Jiazheng Zhao
  • Computer Science Department, Stanford University, CA, USA

Funding

  • Ganesh, Arun: Supported in part by NSF Award CCF-1535989.

Acknowledgements

The inspiration for this project was a suggestion by Kunal Talwar that Generalized Gaussians could achieve the same asymptotic worst-case errors for query response as the mechanism of Steinke and Ullman. In particular, he suggested a proof sketch of a statement similar to Lemma 14 which was the basis for our proof that lemma. We are also thankful to the anonymous reviewers for multiple helpful suggestions on improving the paper.

Cite AsGet BibTex

Arun Ganesh and Jiazheng Zhao. Privately Answering Counting Queries with Generalized Gaussian Mechanisms. In 2nd Symposium on Foundations of Responsible Computing (FORC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 192, pp. 1:1-1:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FORC.2021.1

Abstract

We give the first closed-form privacy guarantees for the Generalized Gaussian mechanism (the mechanism that adds noise x to a vector with probability proportional to exp(-(||x||_p/σ)^p) for some σ, p), in the setting of answering k counting (i.e. sensitivity-1) queries about a database with (ε, δ)-differential privacy (in particular, with low 𝓁_∞-error). Just using Generalized Gaussian noise, we obtain a mechanism such that if the true answers to the queries are the vector d, the mechanism outputs answers d̃ with the 𝓁_∞-error guarantee: 𝔼[||d̃ - d||_∞] = O(√{k log log k log(1/δ)}/ε). This matches the error bound of [Steinke and Ullman, 2017], but using a much simpler mechanism. By composing this mechanism with the sparse vector mechanism (generalizing a technique of [Steinke and Ullman, 2017]), we obtain a mechanism improving the √{k log log k} dependence on k to √{k log log log k}, Our main technical contribution is showing that certain powers of Generalized Gaussians, which follow a Generalized Gamma distribution, are sub-gamma. In subsequent work, the optimal 𝓁_∞-error bound of O(√{k log (1/δ)}/ε) has been achieved by [Yuval Dagan and Gil Kur, 2020] and [Badih Ghazi et al., 2020] independently. However, the Generalized Gaussian mechanism has some qualitative advantages over the mechanisms used in these papers which may make it of interest to both practitioners and theoreticians, both in the setting of answering counting queries and more generally.

Subject Classification

ACM Subject Classification
  • Security and privacy → Privacy-preserving protocols
Keywords
  • Differential privacy
  • counting queries
  • Generalized Gaussians

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. S. Boucheron, G. Lugosi, and P. Massart. Concentration Inequalities: A Nonasymptotic Theory of Independence. OUP Oxford, 2013. URL: https://books.google.com/books?id=koNqWRluhP0C.
  2. Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Martin Hirt and Adam Smith, editors, Theory of Cryptography, pages 635-658, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg. Google Scholar
  3. Mark Bun, Jonathan Ullman, and Salil Vadhan. Fingerprinting codes and the price of approximate differential privacy. In Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’14, page 1–10, New York, NY, USA, 2014. Association for Computing Machinery. URL: https://doi.org/10.1145/2591796.2591877.
  4. Yuval Dagan and Gil Kur. A bounded-noise mechanism for differential privacy, 2020. URL: http://arxiv.org/abs/2012.03817.
  5. Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Serge Vaudenay, editor, Advances in Cryptology - EUROCRYPT 2006, pages 486-503, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. Google Scholar
  6. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin, editors, Theory of Cryptography, pages 265-284, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. Google Scholar
  7. Cynthia Dwork, Moni Naor, Omer Reingold, Guy N. Rothblum, and Salil Vadhan. On the complexity of differentially private data release: Efficient algorithms and hardness results. In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, STOC ’09, page 381–390, New York, NY, USA, 2009. Association for Computing Machinery. URL: https://doi.org/10.1145/1536414.1536467.
  8. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci., 9(3–4):211–407, 2014. URL: https://doi.org/10.1561/0400000042.
  9. Badih Ghazi, Ravi Kumar, and Pasin Manurangsi. On avoiding the union bound when answering multiple differentially private queries, 2020. URL: http://arxiv.org/abs/2012.09116.
  10. Moritz Hardt and Guy N. Rothblum. A multiplicative weights mechanism for privacy-preserving data analysis. In 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pages 61-70, October 2010. URL: https://doi.org/10.1109/FOCS.2010.85.
  11. Moritz Hardt and Kunal Talwar. On the geometry of differential privacy. In Proceedings of the Forty-Second ACM Symposium on Theory of Computing, STOC ’10, page 705–714, New York, NY, USA, 2010. Association for Computing Machinery. URL: https://doi.org/10.1145/1806689.1806786.
  12. N.L. Johnson, S. Kotz, and N. Balakrishnan. Continuous Univariate Distributions. John Wiley & Sons Incorporated, 1995. URL: https://books.google.com/books?id=q03oAAAACAAJ.
  13. D.A. Klain, G.C. Rota, and L.A.R. di Brozolo. Introduction to Geometric Probability. Lezioni Lincee. Cambridge University Press, 1997. URL: https://books.google.com/books?id=Q1ytkNM6BtAC.
  14. Fang Liu. Generalized gaussian mechanism for differential privacy. IEEE Transactions on Knowledge and Data Engineering, 31:747-756, 2019. Google Scholar
  15. Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS ’07, page 94–103, USA, 2007. IEEE Computer Society. URL: https://doi.org/10.1109/FOCS.2007.41.
  16. Ilya Mironov. Rényi differential privacy. 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275, 2017. Google Scholar
  17. Saralees Nadarajah. A generalized normal distribution. Journal of Applied Statistics, 32(7):685-694, 2005. URL: https://doi.org/10.1080/02664760500079464.
  18. Thomas Steinke and Jonathan Ullman. Between pure and approximate differential privacy. Journal of Privacy and Confidentiality, 7(2), 2017. URL: https://doi.org/10.29012/jpc.v7i2.648.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact