Optimal noise adding mechanisms for approximate differential privacy

Quan Geng, Pramod Viswanath

Research output: Contribution to journalArticle

Abstract

We study the (nearly) optimal mechanisms in (∈, δ)-differential privacy for integer-valued query functions and vector-valued (histogram-like) query functions under a utilitymaximization/ cost-minimization framework. Within the classes of mechanisms oblivious of the database and the queries beyond the global sensitivity, we characterize the tradeoff between ∈ and δ in utility and privacy analysis for histogram-like query functions, and show that the (∈, δ)-differential privacy is a framework not much more general than the (∈, 0)-differential privacy and (0, δ)-differential privacy in the context of ℓ1 and ℓ2 cost functions, i.e., minimum expected noise magnitude and noise power. In the same context of ℓ1 and ℓ2 cost functions, we show the near-optimality of uniform noise mechanism and discrete Laplacian mechanism in the high privacy regime (as (∈, δ) → (0, 0)). We conclude that in (∈, δ)-differential privacy, the optimal noise magnitude and the noise power are Θ(min((1/∈), (1/δ))) and Θ(min((1/∈2), (1/δ2))), respectively, in the high privacy regime.

Original languageEnglish (US)
Article number2504972
Pages (from-to)952-969
Number of pages18
JournalIEEE Transactions on Information Theory
Volume62
Issue number2
DOIs
StatePublished - Feb 1 2016

Fingerprint

privacy
Cost functions
costs
regime
Costs

Keywords

  • Data privacy
  • Randomized algorithm

ASJC Scopus subject areas

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

Cite this

Optimal noise adding mechanisms for approximate differential privacy. / Geng, Quan; Viswanath, Pramod.

In: IEEE Transactions on Information Theory, Vol. 62, No. 2, 2504972, 01.02.2016, p. 952-969.

Research output: Contribution to journalArticle

@article{be11ffe8fe3946409e029d7d70253fa9,
title = "Optimal noise adding mechanisms for approximate differential privacy",
abstract = "We study the (nearly) optimal mechanisms in (∈, δ)-differential privacy for integer-valued query functions and vector-valued (histogram-like) query functions under a utilitymaximization/ cost-minimization framework. Within the classes of mechanisms oblivious of the database and the queries beyond the global sensitivity, we characterize the tradeoff between ∈ and δ in utility and privacy analysis for histogram-like query functions, and show that the (∈, δ)-differential privacy is a framework not much more general than the (∈, 0)-differential privacy and (0, δ)-differential privacy in the context of ℓ1 and ℓ2 cost functions, i.e., minimum expected noise magnitude and noise power. In the same context of ℓ1 and ℓ2 cost functions, we show the near-optimality of uniform noise mechanism and discrete Laplacian mechanism in the high privacy regime (as (∈, δ) → (0, 0)). We conclude that in (∈, δ)-differential privacy, the optimal noise magnitude and the noise power are Θ(min((1/∈), (1/δ))) and Θ(min((1/∈2), (1/δ2))), respectively, in the high privacy regime.",
keywords = "Data privacy, Randomized algorithm",
author = "Quan Geng and Pramod Viswanath",
year = "2016",
month = "2",
day = "1",
doi = "10.1109/TIT.2015.2504972",
language = "English (US)",
volume = "62",
pages = "952--969",
journal = "IEEE Transactions on Information Theory",
issn = "0018-9448",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "2",

}

TY - JOUR

T1 - Optimal noise adding mechanisms for approximate differential privacy

AU - Geng, Quan

AU - Viswanath, Pramod

PY - 2016/2/1

Y1 - 2016/2/1

N2 - We study the (nearly) optimal mechanisms in (∈, δ)-differential privacy for integer-valued query functions and vector-valued (histogram-like) query functions under a utilitymaximization/ cost-minimization framework. Within the classes of mechanisms oblivious of the database and the queries beyond the global sensitivity, we characterize the tradeoff between ∈ and δ in utility and privacy analysis for histogram-like query functions, and show that the (∈, δ)-differential privacy is a framework not much more general than the (∈, 0)-differential privacy and (0, δ)-differential privacy in the context of ℓ1 and ℓ2 cost functions, i.e., minimum expected noise magnitude and noise power. In the same context of ℓ1 and ℓ2 cost functions, we show the near-optimality of uniform noise mechanism and discrete Laplacian mechanism in the high privacy regime (as (∈, δ) → (0, 0)). We conclude that in (∈, δ)-differential privacy, the optimal noise magnitude and the noise power are Θ(min((1/∈), (1/δ))) and Θ(min((1/∈2), (1/δ2))), respectively, in the high privacy regime.

AB - We study the (nearly) optimal mechanisms in (∈, δ)-differential privacy for integer-valued query functions and vector-valued (histogram-like) query functions under a utilitymaximization/ cost-minimization framework. Within the classes of mechanisms oblivious of the database and the queries beyond the global sensitivity, we characterize the tradeoff between ∈ and δ in utility and privacy analysis for histogram-like query functions, and show that the (∈, δ)-differential privacy is a framework not much more general than the (∈, 0)-differential privacy and (0, δ)-differential privacy in the context of ℓ1 and ℓ2 cost functions, i.e., minimum expected noise magnitude and noise power. In the same context of ℓ1 and ℓ2 cost functions, we show the near-optimality of uniform noise mechanism and discrete Laplacian mechanism in the high privacy regime (as (∈, δ) → (0, 0)). We conclude that in (∈, δ)-differential privacy, the optimal noise magnitude and the noise power are Θ(min((1/∈), (1/δ))) and Θ(min((1/∈2), (1/δ2))), respectively, in the high privacy regime.

KW - Data privacy

KW - Randomized algorithm

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

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

U2 - 10.1109/TIT.2015.2504972

DO - 10.1109/TIT.2015.2504972

M3 - Article

AN - SCOPUS:84959420145

VL - 62

SP - 952

EP - 969

JO - IEEE Transactions on Information Theory

JF - IEEE Transactions on Information Theory

SN - 0018-9448

IS - 2

M1 - 2504972

ER -