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) $\epsilon$-differential privacy constraint whilst at the same time providing better utility compared to any other $\epsilon$-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. 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. Using this framework we are able to clarify Nissim and Brenner's negative results, showing (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. We also 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.
翻译:Ghosh等人介绍了普世最佳机制的概念,以描述某种同时满足(固定的) $\ epsilon$ 差异隐私限制的某种查询的最佳机制,同时为同一查询提供比其他任何标准(即中央) 差异隐私和地方差异隐私机制更好的效用。它们表明,几何机制对于计算查询类别来说是“普遍最佳”的。另一方面,Brenner和Nisim则表明,在计算查询空间之外和Bayes风险损失功能方面,始终没有这种普遍的最佳机制。在本文件中,我们使用差异隐私和数量信息流动作为研究普遍最佳隐私的基本原则,同时为同一查询提供比任何其他标准(即中央) 差异隐私和地方差异私人机制都更好的效用。它们正越来越多地用于各种应用领域,例如地点隐私和隐私保护机器学习。利用这个框架,我们可以澄清Nisim和Brenner的负面结果,但总是没有这样的普遍最佳最佳机制。 在本文中,我们使用不准确的通用的保密和标准(a) 将所有最差的保密性成本机制都称为“最差的“我们最差的” 。