The optimal mechanism in differential privacy

Quan Geng, Pramod Viswanath

Research output: Chapter in Book/Report/Conference proceedingConference contribution

59 Scopus citations


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 work we study the fundamental tradeoff between privacy and utility in differential privacy. We derive the optimal ε-differentially private mechanism for single real-valued 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 can be viewed as a geometric mixture of uniform probability distributions. In the context of ℓ1 and ℓ2 utility functions, we show that the standard Laplacian mechanism, which has been widely used in the literature, is asymptotically optimal in the high privacy regime, while in the low privacy regime, the staircase mechanism performs exponentially better than the Laplacian mechanism. We conclude that the gains of the staircase mechanism are more pronounced in the moderate-low privacy regime.

Original languageEnglish (US)
Title of host publication2014 IEEE International Symposium on Information Theory, ISIT 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages5
ISBN (Print)9781479951864
StatePublished - 2014
Externally publishedYes
Event2014 IEEE International Symposium on Information Theory, ISIT 2014 - Honolulu, HI, United States
Duration: Jun 29 2014Jul 4 2014

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Other2014 IEEE International Symposium on Information Theory, ISIT 2014
Country/TerritoryUnited States
CityHonolulu, HI

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics


Dive into the research topics of 'The optimal mechanism in differential privacy'. Together they form a unique fingerprint.

Cite this