我们如何定义非确定性算法的$\epsilon$-差分隐私？

Question

我们知道，非琐碎的确定性算法不能保证隐私，而随机性对于隐私是必不可少的( Dwork和Roth 2014中的第16页)。众所周知的\epsilon-diferential隐私被定义为随机(概率)算法(参见链接https://en.wikipedia.org/wiki/Differential_私隐)。

从不确定性的更广泛的角度来看，我想知道我们是否能够为非确定性(多值或集值)算法定义类似的不同隐私概念？又是如何做到的？

Answer 1

我觉得这个问题很有趣。他们认为，对于所有非确定性算法来说，不存在不同的隐私概念。一些不确定的算法可以是(\varepsilon,\delta)-differential私有的.但并不是所有的非确定性算法都是(\varepsilon,\delta)-differential私有的，它们给出了算法的例子.

Algoritm:

输入:数据库D

输出：f(D)从D(非确定性地)删除行/寄存器，其中f是查询函数(中位数、和等)。

注意，这个算法是不确定的，但是如果您重复使用该算法，则可以知道数据库中的所有信息。考虑最坏的情况，攻击者知道除了一行之外的所有数据库(这就是为什么|D-D'|\leq 1是一个条件)。因此，不能保证所有或部分行/寄存器的隐私。