Generalized differential privacy: regions of priors that admit robust optimal mechanisms

Abstract : Differential privacy is a notion of privacy that was initially designed for statistical databases, and has been recently extended to a more general class of domains. Both differential privacy and its generalized version can be achieved by adding random noise to the reported data. Thus, privacy is obtained at the cost of reducing the data's accuracy, and therefore their utility. In this paper we consider the problem of identifying optimal mechanisms for gen- eralized differential privacy, i.e. mechanisms that maximize the utility for a given level of privacy. The utility usually depends on a prior distribution of the data, and naturally it would be desirable to design mechanisms that are universally optimal, i.e., optimal for all priors. However it is already known that such mechanisms do not exist in general. We then characterize maximal classes of priors for which a mechanism which is optimal for all the priors of the class does exist. We show that such classes can be defined as convex polytopes in the priors space. As an application, we consider the problem of privacy that arises when using, for instance, location-based services, and we show how to define mechanisms that maximize the quality of service while preserving the desired level of geo- indistinguishability.
Document type :
Book sections
Complete list of metadatas

Cited literature [25 references]  Display  Hide  Download
Contributor : Catuscia Palamidessi <>
Submitted on : Monday, June 16, 2014 - 2:47:00 AM
Last modification on : Wednesday, March 27, 2019 - 4:41:28 PM
Long-term archiving on : Tuesday, September 16, 2014 - 10:56:36 AM


Files produced by the author(s)




Ehab Elsalamouny, Konstantinos Chatzikokolakis, Catuscia Palamidessi. Generalized differential privacy: regions of priors that admit robust optimal mechanisms. van Breugel, Franck and Kashefi, Elham and Palamidessi, Catuscia and Rutten, Jan. Horizons of the Mind. A Tribute to Prakash Panangaden, 8464, Springer International Publishing, pp.292-318, 2014, Lecture Notes in Computer Science, 978-3-319-06879-4. ⟨10.1007/978-3-319-06880-0_16⟩. ⟨hal-01006380⟩



Record views


Files downloads