The staircase mechanism in differential privacy

Quan Geng, Peter Kairouz, Sewoong Oh, Pramod Viswanath

Research output: Contribution to journalArticle

Abstract

Adding Laplacian noise is a standard approach in differential privacy to sanitize numerical data before releasing it. In this paper, we propose an alternative noise adding mechanism: the staircase mechanism, which is a geometric mixture of uniform random variables. The staircase mechanism can replace the Laplace mechanism in each instance in the literature and for the same level of differential privacy, the performance in each instance improves; the improvement is particularly stark in medium-low privacy regimes. We show that the staircase mechanism is the optimal noise adding mechanism in a universal context, subject to a conjectured technical lemma (which we also prove to be true for one and two dimensional data).

Original languageEnglish (US)
Article number7093132
Pages (from-to)1176-1184
Number of pages9
JournalIEEE Journal on Selected Topics in Signal Processing
Volume9
Issue number7
DOIs
StatePublished - Oct 1 2015

Fingerprint

Random variables

Keywords

  • Data privacy
  • Randomized algorithm

ASJC Scopus subject areas

  • Signal Processing
  • Electrical and Electronic Engineering

Cite this

The staircase mechanism in differential privacy. / Geng, Quan; Kairouz, Peter; Oh, Sewoong; Viswanath, Pramod.

In: IEEE Journal on Selected Topics in Signal Processing, Vol. 9, No. 7, 7093132, 01.10.2015, p. 1176-1184.

Research output: Contribution to journalArticle

Geng, Quan ; Kairouz, Peter ; Oh, Sewoong ; Viswanath, Pramod. / The staircase mechanism in differential privacy. In: IEEE Journal on Selected Topics in Signal Processing. 2015 ; Vol. 9, No. 7. pp. 1176-1184.
@article{667fd4578c6448af806f087417518d9a,
title = "The staircase mechanism in differential privacy",
abstract = "Adding Laplacian noise is a standard approach in differential privacy to sanitize numerical data before releasing it. In this paper, we propose an alternative noise adding mechanism: the staircase mechanism, which is a geometric mixture of uniform random variables. The staircase mechanism can replace the Laplace mechanism in each instance in the literature and for the same level of differential privacy, the performance in each instance improves; the improvement is particularly stark in medium-low privacy regimes. We show that the staircase mechanism is the optimal noise adding mechanism in a universal context, subject to a conjectured technical lemma (which we also prove to be true for one and two dimensional data).",
keywords = "Data privacy, Randomized algorithm",
author = "Quan Geng and Peter Kairouz and Sewoong Oh and Pramod Viswanath",
year = "2015",
month = "10",
day = "1",
doi = "10.1109/JSTSP.2015.2425831",
language = "English (US)",
volume = "9",
pages = "1176--1184",
journal = "IEEE Journal on Selected Topics in Signal Processing",
issn = "1932-4553",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
number = "7",

}

TY - JOUR

T1 - The staircase mechanism in differential privacy

AU - Geng, Quan

AU - Kairouz, Peter

AU - Oh, Sewoong

AU - Viswanath, Pramod

PY - 2015/10/1

Y1 - 2015/10/1

N2 - Adding Laplacian noise is a standard approach in differential privacy to sanitize numerical data before releasing it. In this paper, we propose an alternative noise adding mechanism: the staircase mechanism, which is a geometric mixture of uniform random variables. The staircase mechanism can replace the Laplace mechanism in each instance in the literature and for the same level of differential privacy, the performance in each instance improves; the improvement is particularly stark in medium-low privacy regimes. We show that the staircase mechanism is the optimal noise adding mechanism in a universal context, subject to a conjectured technical lemma (which we also prove to be true for one and two dimensional data).

AB - Adding Laplacian noise is a standard approach in differential privacy to sanitize numerical data before releasing it. In this paper, we propose an alternative noise adding mechanism: the staircase mechanism, which is a geometric mixture of uniform random variables. The staircase mechanism can replace the Laplace mechanism in each instance in the literature and for the same level of differential privacy, the performance in each instance improves; the improvement is particularly stark in medium-low privacy regimes. We show that the staircase mechanism is the optimal noise adding mechanism in a universal context, subject to a conjectured technical lemma (which we also prove to be true for one and two dimensional data).

KW - Data privacy

KW - Randomized algorithm

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

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

U2 - 10.1109/JSTSP.2015.2425831

DO - 10.1109/JSTSP.2015.2425831

M3 - Article

AN - SCOPUS:84942288037

VL - 9

SP - 1176

EP - 1184

JO - IEEE Journal on Selected Topics in Signal Processing

JF - IEEE Journal on Selected Topics in Signal Processing

SN - 1932-4553

IS - 7

M1 - 7093132

ER -