具有非确定性函数的Laplace机构的微分隐私

Question

这个问题是关于laplace机制的差别隐私的证明。

我发现了更多关于laplace机制是\epsilon-differentially私有的解释，使用确定性函数作为数据库上的查询f(例如计数查询)。

，但该语句实际上只对确定性f?

有效吗？

在我看来，添加Laplace噪声是一种很流行的方法，可以使任何类型的查询都具有不同的私有性。想象一下有一个随机的查询，但是它的随机性是奇怪的，你只是说，呃，跳过查找，如果这个机制本身是私有的。只需添加额外的噪声(在本例中为laplace噪声)，就可以了。从增加噪音以改善隐私的想法来看，这应该是可能的--我想。

如果拉普拉斯机制也适用于非确定性函数，那么在微分隐私的证明中，考虑到函数的随机性的影响在哪里？如果如下所示的标准证明(来自Dwork/Roth的“差分隐私的算法基础”)对随机f不起作用，那么还有其他方法来证明吗？多么?

提前感谢您的帮助。

Answer 1

Laplace机制只适用于确定性的f，因为“灵敏度”的概念(在上面公式中的\Delta f )对于随机函数没有很好的定义。\Delta f是f(x)和f(y)之间最大的差异，对于相邻的x和f。如果f是一个随机函数，那么捕获“差异”的概念就会变得更加复杂，所以一般来说，您只需假设f是确定性的。

要将其扩展到f是随机的情况，可以将\Delta f定义为f(x)的可能输出与f(y)的可能输出之间的最大差异，对于f使用的随机比特的所有可能值。这仍然允许你说\frac{||f(x)-f(y)||}{\Delta f}\le1。但是，如果这个值是无界的(例如，如果f隐式地向计算结果中添加高斯噪声)，这是无效的，这通常是一个松散的近似；所以它几乎从来没有完成。