The optimal noise-adding mechanism in differential privacy

Quan Geng, Pramod Viswanath

Research output: Contribution to journalArticle

Abstract

Differential privacy is a framework to quantify to what extent individual privacy in a statistical database is preserved while releasing useful aggregate information about the database. In this paper, within the classes of mechanisms oblivious of the database and the queries beyond the global sensitivity, we characterize the fundamental tradeoff between privacy and utility in differential privacy, and derive the optimal ∈-differentially private mechanism for a single realvalued query function under a very general utility-maximization (or cost-minimization) framework. The class of noise probability distributions in the optimal mechanism has staircase-shaped probability density functions which are symmetric (around the origin), monotonically decreasing and geometrically decaying. The staircase mechanism can be viewed as a geometric mixture of uniform probability distributions, providing a simple algorithmic description for the mechanism. Furthermore, the staircase mechanism naturally generalizes to discrete query output settings as well as more abstract settings. We explicitly derive the parameter of the optimal staircase mechanism for ℓ1 and ℓ2 cost functions. Comparing the optimal performances with those of the usual Laplacian mechanism, we show that in the high privacy regime (∈ is small), the Laplacian mechanism is asymptotically optimal as ∈ → 0; in the low privacy regime (∈ is large), the minimum magnitude and second moment of noise are Θ(Δe(-∈/2)) and Θ(Δ2e(-2∈/3)) as ∈ → +∞, respectively, while the corresponding figures when using the Laplacian mechanism are Δ/∈ and 2Δ2/∈2, where Δ is the sensitivity of the query function. We conclude that the gains of the staircase mechanism are more pronounced in the moderate-low privacy regime.

Original languageEnglish (US)
Article number2504967
Pages (from-to)925-951
Number of pages27
JournalIEEE Transactions on Information Theory
Volume62
Issue number2
DOIs
StatePublished - Feb 1 2016

Fingerprint

privacy
Probability distributions
Cost functions
Probability density function
regime
costs
Costs
performance

Keywords

  • Data privacy
  • Randomized algorithm

ASJC Scopus subject areas

  • Information Systems
  • Computer Science Applications
  • Library and Information Sciences

Cite this

The optimal noise-adding mechanism in differential privacy. / Geng, Quan; Viswanath, Pramod.

In: IEEE Transactions on Information Theory, Vol. 62, No. 2, 2504967, 01.02.2016, p. 925-951.

Research output: Contribution to journalArticle

@article{19ad2253ad1443509edcf2da1bdb42ac,
title = "The optimal noise-adding mechanism in differential privacy",
abstract = "Differential privacy is a framework to quantify to what extent individual privacy in a statistical database is preserved while releasing useful aggregate information about the database. In this paper, within the classes of mechanisms oblivious of the database and the queries beyond the global sensitivity, we characterize the fundamental tradeoff between privacy and utility in differential privacy, and derive the optimal ∈-differentially private mechanism for a single realvalued query function under a very general utility-maximization (or cost-minimization) framework. The class of noise probability distributions in the optimal mechanism has staircase-shaped probability density functions which are symmetric (around the origin), monotonically decreasing and geometrically decaying. The staircase mechanism can be viewed as a geometric mixture of uniform probability distributions, providing a simple algorithmic description for the mechanism. Furthermore, the staircase mechanism naturally generalizes to discrete query output settings as well as more abstract settings. We explicitly derive the parameter of the optimal staircase mechanism for ℓ1 and ℓ2 cost functions. Comparing the optimal performances with those of the usual Laplacian mechanism, we show that in the high privacy regime (∈ is small), the Laplacian mechanism is asymptotically optimal as ∈ → 0; in the low privacy regime (∈ is large), the minimum magnitude and second moment of noise are Θ(Δe(-∈/2)) and Θ(Δ2e(-2∈/3)) as ∈ → +∞, respectively, while the corresponding figures when using the Laplacian mechanism are Δ/∈ and 2Δ2/∈2, where Δ is the sensitivity of the query function. We conclude that the gains of the staircase mechanism are more pronounced in the moderate-low privacy regime.",
keywords = "Data privacy, Randomized algorithm",
author = "Quan Geng and Pramod Viswanath",
year = "2016",
month = "2",
day = "1",
doi = "10.1109/TIT.2015.2504967",
language = "English (US)",
volume = "62",
pages = "925--951",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "2",

}

TY - JOUR

T1 - The optimal noise-adding mechanism in differential privacy

AU - Geng, Quan

AU - Viswanath, Pramod

PY - 2016/2/1

Y1 - 2016/2/1

N2 - Differential privacy is a framework to quantify to what extent individual privacy in a statistical database is preserved while releasing useful aggregate information about the database. In this paper, within the classes of mechanisms oblivious of the database and the queries beyond the global sensitivity, we characterize the fundamental tradeoff between privacy and utility in differential privacy, and derive the optimal ∈-differentially private mechanism for a single realvalued query function under a very general utility-maximization (or cost-minimization) framework. The class of noise probability distributions in the optimal mechanism has staircase-shaped probability density functions which are symmetric (around the origin), monotonically decreasing and geometrically decaying. The staircase mechanism can be viewed as a geometric mixture of uniform probability distributions, providing a simple algorithmic description for the mechanism. Furthermore, the staircase mechanism naturally generalizes to discrete query output settings as well as more abstract settings. We explicitly derive the parameter of the optimal staircase mechanism for ℓ1 and ℓ2 cost functions. Comparing the optimal performances with those of the usual Laplacian mechanism, we show that in the high privacy regime (∈ is small), the Laplacian mechanism is asymptotically optimal as ∈ → 0; in the low privacy regime (∈ is large), the minimum magnitude and second moment of noise are Θ(Δe(-∈/2)) and Θ(Δ2e(-2∈/3)) as ∈ → +∞, respectively, while the corresponding figures when using the Laplacian mechanism are Δ/∈ and 2Δ2/∈2, where Δ is the sensitivity of the query function. We conclude that the gains of the staircase mechanism are more pronounced in the moderate-low privacy regime.

AB - Differential privacy is a framework to quantify to what extent individual privacy in a statistical database is preserved while releasing useful aggregate information about the database. In this paper, within the classes of mechanisms oblivious of the database and the queries beyond the global sensitivity, we characterize the fundamental tradeoff between privacy and utility in differential privacy, and derive the optimal ∈-differentially private mechanism for a single realvalued query function under a very general utility-maximization (or cost-minimization) framework. The class of noise probability distributions in the optimal mechanism has staircase-shaped probability density functions which are symmetric (around the origin), monotonically decreasing and geometrically decaying. The staircase mechanism can be viewed as a geometric mixture of uniform probability distributions, providing a simple algorithmic description for the mechanism. Furthermore, the staircase mechanism naturally generalizes to discrete query output settings as well as more abstract settings. We explicitly derive the parameter of the optimal staircase mechanism for ℓ1 and ℓ2 cost functions. Comparing the optimal performances with those of the usual Laplacian mechanism, we show that in the high privacy regime (∈ is small), the Laplacian mechanism is asymptotically optimal as ∈ → 0; in the low privacy regime (∈ is large), the minimum magnitude and second moment of noise are Θ(Δe(-∈/2)) and Θ(Δ2e(-2∈/3)) as ∈ → +∞, respectively, while the corresponding figures when using the Laplacian mechanism are Δ/∈ and 2Δ2/∈2, where Δ is the sensitivity of the query function. We conclude that the gains of the staircase mechanism are more pronounced in the moderate-low privacy regime.

KW - Data privacy

KW - Randomized algorithm

UR - http://www.scopus.com/inward/record.url?scp=84959378185&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84959378185&partnerID=8YFLogxK

U2 - 10.1109/TIT.2015.2504967

DO - 10.1109/TIT.2015.2504967

M3 - Article

AN - SCOPUS:84959378185

VL - 62

SP - 925

EP - 951

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 2

M1 - 2504967

ER -