The Laplace Mechanism has optimal utility for differential privacy over continuous queries

Natasha Fernandes, Annabelle McIver, Carroll Morgan

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

Abstract

Differential Privacy protects individuals' data when statistical queries are published from aggregated databases: applying obfuscating mechanisms to the query results makes the released information less specific but, unavoidably, also decreases its utility. Yet it has been shown that for discrete data (e.g. counting queries), a mandated degree of privacy and a reasonable interpretation of loss of utility, the Geometric obfuscating mechanism is optimal: it loses as little utility as possible [Ghosh et al. [1]].For continuous query results however (e.g. real numbers) the optimality result does not hold. Our contribution here is to show that optimality is regained by using the Laplace mechanism for the obfuscation.The technical apparatus involved includes the earlier discrete result [Ghosh op. cit.], recent work on abstract channels and their geometric representation as hyper-distributions [Alvim et al. [2]], and the dual interpretations of distance between distributions provided by the Kantorovich-Rubinstein Theorem.

Original languageEnglish
Title of host publication36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages12
ISBN (Electronic)9781665448956
DOIs
Publication statusPublished - 2021
Event36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021 - Virtual, Online
Duration: 29 Jun 20212 Jul 2021

Publication series

NameProceedings - Symposium on Logic in Computer Science
Volume2021-June
ISSN (Print)1043-6871

Conference

Conference36th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2021
CityVirtual, Online
Period29/06/212/07/21

Keywords

  • abstract channels
  • Differential privacy
  • hyper-distributions
  • Laplace mechanism
  • optimal mechanisms
  • quantitative information flow
  • utility

Fingerprint

Dive into the research topics of 'The Laplace Mechanism has optimal utility for differential privacy over continuous queries'. Together they form a unique fingerprint.

Cite this