{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T02:47:48Z","timestamp":1784774868084,"version":"3.55.0"},"reference-count":25,"publisher":"SAGE Publications","issue":"5","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["JCS"],"published-print":{"date-parts":[[2023,10,13]]},"abstract":"<jats:p>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 \u201cbest\u201d mechanism for a certain query that simultaneously satisfies (a fixed) \u03b5-differential privacy constraint whilst at the same time providing better utility compared to any other \u03b5-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 \u03b5-differential privacy and a metric meaningful to the underlying state space. Using this framework we are able to clarify Nissim and Brenner\u2019s 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.<\/jats:p>","DOI":"10.3233\/jcs-230036","type":"journal-article","created":{"date-parts":[[2023,7,18]],"date-time":"2023-07-18T11:41:27Z","timestamp":1689680487000},"page":"539-580","source":"Crossref","is-referenced-by-count":5,"title":["Universal optimality and robust utility bounds for metric differential privacy1"],"prefix":"10.1177","volume":"31","author":[{"given":"Natasha","family":"Fernandes","sequence":"first","affiliation":[{"name":"School of Computing, Macquarie University, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Annabelle","family":"McIver","sequence":"additional","affiliation":[{"name":"School of Computing, Macquarie University, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Catuscia","family":"Palamidessi","sequence":"additional","affiliation":[{"name":"Inria and Institut Polytechnique de Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ming","family":"Ding","sequence":"additional","affiliation":[{"name":"Data61, CSIRO, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"179","reference":[{"key":"10.3233\/JCS-230036_ref1","unstructured":"J. Acharya, K. Bonawitz, P. Kairouz, D. Ramage and Z. Sun, Context aware local differential privacy, in: International Conference on Machine Learning, PMLR, 2020, pp. 52\u201362."},{"key":"10.3233\/JCS-230036_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22012-8_4"},{"key":"10.3233\/JCS-230036_ref3","doi-asserted-by":"crossref","unstructured":"M.S. Alvim, K. Chatzikokolakis, A. McIver, C. Morgan, C. Palamidessi and G. Smith, The Science of Quantitative Information Flow, Springer, 2019.","DOI":"10.1007\/978-3-319-96131-6"},{"key":"10.3233\/JCS-230036_ref4","doi-asserted-by":"publisher","DOI":"10.1109\/CSF.2012.26"},{"key":"10.3233\/JCS-230036_ref5","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CONCUR.2020.1"},{"key":"10.3233\/JCS-230036_ref6","doi-asserted-by":"crossref","unstructured":"M.E. Andr\u00e9s, N.E. Bordenabe, K. Chatzikokolakis and C. Palamidessi, Geo-indistinguishability: Differential privacy for location-based systems, in: Proceedings of the 2013 ACM SIGSAC Conference on Computer & Communications Security, 2013, pp. 901\u2013914.","DOI":"10.1145\/2508859.2516735"},{"key":"10.3233\/JCS-230036_ref7","doi-asserted-by":"crossref","unstructured":"N.E. Bordenabe, K. Chatzikokolakis and C. Palamidessi, Optimal geo-indistinguishable mechanisms for location privacy, in: Proc. CCS, 2014, pp. 251\u2013262.","DOI":"10.1145\/2660267.2660345"},{"key":"10.3233\/JCS-230036_ref8","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.13"},{"key":"10.3233\/JCS-230036_ref9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39077-7_5"},{"key":"10.3233\/JCS-230036_ref10","doi-asserted-by":"crossref","unstructured":"K. Chatzikokolakis, N. Fernandes and C. Palamidessi, Comparing systems: Max-case refinement orders and application to differential privacy, in: Proc. CSF, IEEE Press, 2019.","DOI":"10.1109\/CSF.2019.00037"},{"issue":"1","key":"10.3233\/JCS-230036_ref11","doi-asserted-by":"publisher","first-page":"40","DOI":"10.3390\/jcp1010004","article-title":"Refinement orders for quantitative information flow and differential privacy","volume":"1","author":"Chatzikokolakis","year":"2021","journal-title":"Journal of Cybersecurity and Privacy"},{"key":"10.3233\/JCS-230036_ref12","unstructured":"H.A.J.C. Duchi, Near Instance-Optimality in Differential Privacy, 2020, 2020, arXiv:2005.10630v1."},{"key":"10.3233\/JCS-230036_ref13","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.53"},{"key":"10.3233\/JCS-230036_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_1"},{"key":"10.3233\/JCS-230036_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"10.3233\/JCS-230036_ref16","doi-asserted-by":"crossref","unstructured":"\u00da. Erlingsson, V. Pihur and A. Korolova, RAPPOR: Randomized aggregatable privacy-preserving ordinal response, in: Proc. CCS, 2014, pp. 1054\u20131067.","DOI":"10.1145\/2660267.2660348"},{"key":"10.3233\/JCS-230036_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17138-4_6"},{"key":"10.3233\/JCS-230036_ref18","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470718"},{"key":"10.3233\/JCS-230036_ref19","doi-asserted-by":"publisher","DOI":"10.1109\/CSF54842.2022.9919647"},{"issue":"6","key":"10.3233\/JCS-230036_ref20","doi-asserted-by":"publisher","first-page":"1673","DOI":"10.1137\/09076828X","article-title":"Universally utility-maximizing privacy mechanisms","volume":"41","author":"Ghosh","year":"2012","journal-title":"SIAM Journal on Computing"},{"key":"10.3233\/JCS-230036_ref21","doi-asserted-by":"publisher","DOI":"10.1145\/1807085.1807105"},{"issue":"1","key":"10.3233\/JCS-230036_ref22","first-page":"492","article-title":"Extremal mechanisms for local differential privacy","volume":"17","author":"Kairouz","year":"2016","journal-title":"The Journal of Machine Learning Research"},{"key":"10.3233\/JCS-230036_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-54792-8_5"},{"key":"10.3233\/JCS-230036_ref25","unstructured":"S.T. Rachev and L. R\u00fcschendorf, Mass Transportation Problems: Volume I: Theory, Vol. 1, Springer Science & Business Media, 1998."},{"key":"10.3233\/JCS-230036_ref26","doi-asserted-by":"publisher","DOI":"10.1145\/3460120.3484734"}],"container-title":["Journal of Computer Security"],"original-title":[],"link":[{"URL":"https:\/\/content.iospress.com\/download?id=10.3233\/JCS-230036","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T20:45:44Z","timestamp":1777495544000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/full\/10.3233\/JCS-230036"}},"subtitle":[],"editor":[{"given":"Stefano","family":"Calzavara","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]},{"given":"David","family":"Naumann","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"editor"}]}],"short-title":[],"issued":{"date-parts":[[2023,10,13]]},"references-count":25,"journal-issue":{"issue":"5"},"URL":"https:\/\/doi.org\/10.3233\/jcs-230036","relation":{},"ISSN":["1875-8924","0926-227X"],"issn-type":[{"value":"1875-8924","type":"electronic"},{"value":"0926-227X","type":"print"}],"subject":[],"published":{"date-parts":[[2023,10,13]]}}}