如何通过二次采样设置加性噪声进行放大

Question

我正在测试一个隐私机制，并通过次抽样实现隐私放大。我正在计算已知参与人数的计数汇总函数。我正在应用Laplace机制，如下所示：

DP-count = True count + Laplace (\frac{\Delta}{\epsilon})

敏感度取决于人口规模。对种群大小，N的敏感性，\Delta = \frac{1}{N}。如果采用次抽样机制，会否影响灵敏度？对于m个样本，我应该设置灵敏度\Delta = \frac{1}{m}吗？为了比较的目的，我应该保持\epsilon和以前一样吗？

Answer 1

M是一种具有O(\epsilon)差异隐私的机制，D是数据库。若要通过抽样应用隐私放大，请通过使用概率D'选择D的每个成员来定义另一个数据库p，然后将M应用于D'。这个过程的总体隐私是O(p\epsilon)。有关隐藏在大O表示法中的确切表达式，请参见引理2 https://www.cs.bgu.ac.il/~beimel/Papers/BKN.pdf。

如果M仅为固定大小的数据库定义，那么显然不能将其应用于D'。另一方面，如果为任意大小的数据库定义了M，则要使用Laplace机制，则函数的灵敏度必须独立于输入(根据灵敏度的定义)。因此，关于函数f的敏感性是1/N的说法是没有道理的。