Universal optimality and robust utility bounds for metric differential privacy

Natasha Fernandes*, Annabelle McIver, Catuscia Palamidessi, Ming Ding

*Corresponding author for this work

Research output: Contribution to journalConference paperpeer-review

1 Citation (Scopus)

Abstract

We study the privacy-utility trade-off in the context of metric differential privacy. Ghosh et al. introduced the idea of universal optimality to characterise the 'best' mechanism for a certain query that simultaneously satisfies (a fixed) ϵ-differential privacy constraint whilst at the same time providing better utility compared to any other ϵ-differentially private mechanism for the same query. They showed that the Geometric mechanism is universally optimal for the class of counting queries. On the other hand, Brenner and Nissim showed that outside the space of counting queries, and for the Bayes risk loss function, no such universally optimal mechanisms exist. Except for the universal optimality of the Laplace mechanism, there have been no generalisations of these universally optimal results to other classes of differentially-private mechanisms. 

In this paper, we use metric differential privacy and quantitative information flow as the fundamental principle for studying universal optimality. Metric differential privacy is a generalisation of both standard (i.e., central) differential privacy and local differential privacy, and it is increasingly being used in various application domains, for instance in location privacy and in privacy-preserving machine learning. Similar to the approaches adopted by Ghosh et al. and Brenner and Nissim, we measure utility in terms of loss functions, and we interpret the notion of a privacy mechanism as an information-Theoretic channel satisfying constraints defined by ϵ-differential privacy and a metric meaningful to the underlying state space. Using this framework we are able to clarify Nissim and Brenner's negative results by (a) that in fact all privacy types contain optimal mechanisms relative to certain kinds of non-Trivial loss functions, and (b) extending and generalising their negative results beyond Bayes risk specifically to a wide class of non-Trivial loss functions. 

Our exploration suggests that universally optimal mechanisms are indeed rare within privacy types. We therefore propose weaker universal benchmarks of utility called privacy type capacities. We show that such capacities always exist and can be computed using a convex optimisation algorithm. Further, we illustrate these ideas on a selection of examples with several different underlying metrics.

Original languageEnglish
Pages (from-to)539-580
Number of pages42
JournalJournal of Computer Security
Volume31
Issue number5
DOIs
Publication statusPublished - 2023
Event35th IEEE Computer Security Foundations Symposium, CSF 2022 - Haifa, Israel
Duration: 7 Aug 202210 Aug 2022

Bibliographical note

This paper is an extended and revised version of a paper presented at CSF'22.

Keywords

  • Universal optimality
  • metric differential privacy
  • privacy-utility trade-off

Fingerprint

Dive into the research topics of 'Universal optimality and robust utility bounds for metric differential privacy'. Together they form a unique fingerprint.

Cite this