Log-Concave and Multivariate Canonical Noise Distributions for Differential Privacy
Log-Concave and Multivariate Canonical Noise Distributions for Differential Privacy
复制标题
DOI：
10.48550/arxiv.2206.04572
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Jordan Awan;Jinshuo Dong
中科院分区：
文献类型：
--
作者：
Jordan Awan;Jinshuo Dong
典型噪声分布（CND）是一种附加机制，旨在满足$f$-差分隐私（$f$-DP），没有任何浪费的隐私预算。$f$-DP是一种基于假设检验的隐私公式，根据权衡函数进行措辞，它抓住了假设检验的难度。在本文中，我们考虑对数凹CND和多元CND的存在性和构造。对数凹分布对于确保机制的较高输出对应于较高输入值是重要的，而多变量噪声分布对于确保多个输出的联合发布具有紧密的隐私特性是重要的。我们发现，这两种类型的问题的CND的存在和建设有关的权衡功能是否可以分解的功能组成（有关组隐私）或机制组成。特别是，我们表明，纯$\n $-DP不能以任何方式分解，既没有对数凹CND也没有任何多元CND的$\n $-DP。另一方面，我们表明，高斯-DP，$（0，\delta）$-DP，和拉普拉斯-DP都有对数凹和多元CND。
A canonical noise distribution (CND) is an additive mechanism designed to satisfy $f$-differential privacy ($f$-DP), without any wasted privacy budget. $f$-DP is a hypothesis testing-based formulation of privacy phrased in terms of tradeoff functions, which captures the difficulty of a hypothesis test. In this paper, we consider the existence and construction of both log-concave CNDs and multivariate CNDs. Log-concave distributions are important to ensure that higher outputs of the mechanism correspond to higher input values, whereas multivariate noise distributions are important to ensure that a joint release of multiple outputs has a tight privacy characterization. We show that the existence and construction of CNDs for both types of problems is related to whether the tradeoff function can be decomposed by functional composition (related to group privacy) or mechanism composition. In particular, we show that pure $\epsilon$-DP cannot be decomposed in either way and that there is neither a log-concave CND nor any multivariate CND for $\epsilon$-DP. On the other hand, we show that Gaussian-DP, $(0,\delta)$-DP, and Laplace-DP each have both log-concave and multivariate CNDs.