DROPS

Document

DOI: 10.4230/LIPIcs.ITC.2021.18

Differentially Private Approximations of a Convex Hull in Low Dimensions

Authors: Yue Gao and Or Sheffet

Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)

Abstract

We give the first differentially private algorithms that estimate a variety of geometric features of points in the Euclidean space, such as diameter, width, volume of convex hull, min-bounding box, min-enclosing ball, etc. Our work relies heavily on the notion of Tukey-depth. Instead of (non-privately) approximating the convex-hull of the given set of points P, our algorithms approximate the geometric features of D_{P}(κ) - the κ-Tukey region induced by P (all points of Tukey-depth κ or greater). Moreover, our approximations are all bi-criteria: for any geometric feature μ our (α,Δ)-approximation is a value "sandwiched" between (1-α)μ(D_P(κ)) and (1+α)μ(D_P(κ-Δ)). Our work is aimed at producing a (α,Δ)-kernel of D_P(κ), namely a set 𝒮 such that (after a shift) it holds that (1-α)D_P(κ) ⊂ CH(𝒮) ⊂ (1+α)D_P(κ-Δ). We show that an analogous notion of a bi-critera approximation of a directional kernel, as originally proposed by [Pankaj K. Agarwal et al., 2004], fails to give a kernel, and so we result to subtler notions of approximations of projections that do yield a kernel. First, we give differentially private algorithms that find (α,Δ)-kernels for a "fat" Tukey-region. Then, based on a private approximation of the min-bounding box, we find a transformation that does turn D_P(κ) into a "fat" region but only if its volume is proportional to the volume of D_P(κ-Δ). Lastly, we give a novel private algorithm that finds a depth parameter κ for which the volume of D_P(κ) is comparable to the volume of D_P(κ-Δ). We hope our work leads to the further study of the intersection of differential privacy and computational geometry.

Cite as

Yue Gao and Or Sheffet. Differentially Private Approximations of a Convex Hull in Low Dimensions. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{gao_et_al:LIPIcs.ITC.2021.18,
  author =	{Gao, Yue and Sheffet, Or},
  title =	{{Differentially Private Approximations of a Convex Hull in Low Dimensions}},
  booktitle =	{2nd Conference on Information-Theoretic Cryptography (ITC 2021)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-197-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{199},
  editor =	{Tessaro, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.18},
  URN =		{urn:nbn:de:0030-drops-143377},
  doi =		{10.4230/LIPIcs.ITC.2021.18},
  annote =	{Keywords: Differential Privacy, Computational Geometry, Tukey Depth}
}

Document

DOI: 10.4230/LIPIcs.ITC.2020.14

The Power of Synergy in Differential Privacy: Combining a Small Curator with Local Randomizers

Authors: Amos Beimel, Aleksandra Korolova, Kobbi Nissim, Or Sheffet, and Uri Stemmer

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract

Motivated by the desire to bridge the utility gap between local and trusted curator models of differential privacy for practical applications, we initiate the theoretical study of a hybrid model introduced by "Blender" [Avent et al., USENIX Security '17], in which differentially private protocols of n agents that work in the local-model are assisted by a differentially private curator that has access to the data of m additional users. We focus on the regime where m ≪ n and study the new capabilities of this (m,n)-hybrid model. We show that, despite the fact that the hybrid model adds no significant new capabilities for the basic task of simple hypothesis-testing, there are many other tasks (under a wide range of parameters) that can be solved in the hybrid model yet cannot be solved either by the curator or by the local-users separately. Moreover, we exhibit additional tasks where at least one round of interaction between the curator and the local-users is necessary - namely, no hybrid model protocol without such interaction can solve these tasks. Taken together, our results show that the combination of the local model with a small curator can become part of a promising toolkit for designing and implementing differential privacy.

Cite as

Amos Beimel, Aleksandra Korolova, Kobbi Nissim, Or Sheffet, and Uri Stemmer. The Power of Synergy in Differential Privacy: Combining a Small Curator with Local Randomizers. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 14:1-14:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{beimel_et_al:LIPIcs.ITC.2020.14,
  author =	{Beimel, Amos and Korolova, Aleksandra and Nissim, Kobbi and Sheffet, Or and Stemmer, Uri},
  title =	{{The Power of Synergy in Differential Privacy: Combining a Small Curator with Local Randomizers}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{14:1--14:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.14},
  URN =		{urn:nbn:de:0030-drops-121195},
  doi =		{10.4230/LIPIcs.ITC.2020.14},
  annote =	{Keywords: differential privacy, hybrid model, private learning, local model}
}

Search Results

Documents authored by Sheffet, Or

Differentially Private Approximations of a Convex Hull in Low Dimensions

Abstract

Cite as

The Power of Synergy in Differential Privacy: Combining a Small Curator with Local Randomizers

Abstract

Cite as

Thanks for your feedback!

Could not send message