1 Search Results for "Zhao, Jiazheng"

Document

DOI: 10.4230/LIPIcs.FORC.2021.1

Privately Answering Counting Queries with Generalized Gaussian Mechanisms

Authors: Arun Ganesh and Jiazheng Zhao

Published in: LIPIcs, Volume 192, 2nd Symposium on Foundations of Responsible Computing (FORC 2021)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{ganesh_et_al:LIPIcs.FORC.2021.1,
  author =	{Ganesh, Arun and Zhao, Jiazheng},
  title =	{{Privately Answering Counting Queries with Generalized Gaussian Mechanisms}},
  booktitle =	{2nd Symposium on Foundations of Responsible Computing (FORC 2021)},
  pages =	{1:1--1:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-187-0},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{192},
  editor =	{Ligett, Katrina and Gupta, Swati},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2021.1},
  URN =		{urn:nbn:de:0030-drops-138698},
  doi =		{10.4230/LIPIcs.FORC.2021.1},
  annote =	{Keywords: Differential privacy, counting queries, Generalized Gaussians}
}

Refine by Author
1 Ganesh, Arun
1 Zhao, Jiazheng

Refine by Classification
1 Security and privacy → Privacy-preserving protocols

Refine by Keyword
1 Differential privacy
1 Generalized Gaussians
1 counting queries

Refine by Type
1 document

Refine by Publication Year
1 2021

1 Search Results for "Zhao, Jiazheng"

Privately Answering Counting Queries with Generalized Gaussian Mechanisms

Abstract

Cite as

Thanks for your feedback!

Could not send message