局部差分隐私实现的广义随机响应

Question

我的任务是实施本地（非交互式）差分隐私机制。我正在处理一个大型人口普查数据数据库。唯一的敏感属性是 "Number of children"，它是一个介于 0 到 13 之间的数值。

我决定采用广义随机响应机制，因为它看起来是最直观的方法。 here and presented here.

描述了这种机制

将每个值加载到数组后（暂时忽略其他属性），我按如下方式执行扰动。

d = 14 # values may range from 0 to 13

eps = 1 # epsilon level of privacy

p = (math.exp(eps)/(math.exp(eps)+d-1))
q = 1/(math.exp(eps)+d-1)

p_dataset = []

for row in dataset:
    coin = random.random()
    if coin <= p:
        p_dataset.append(row)
    else:
        p_dataset.append(random.randint(0,13))

除非我误解了定义，否则我相信这将保证 p_dataset 上的 epsilon 差分隐私。

但是，我很难理解聚合器必须如何解释此数据集。按照上面的 presentation，我尝试实现一种方法来估计回答特定值的人数。

v = 0 # we are estimating the number of individuals in the dataset who answered 0
nv = 0 # number of users in the perturbed dataset who answered the value

for row in p_dataset:
    if row == v:
        nv += 1

Iv = nv * p + (n - nv) * q
estimation = (Iv - (n*q)) / (p-q)

我不知道自己是否正确实现了描述的方法，因为我不完全理解它在做什么，也找不到明确的定义。

不管怎样，我用这个方法估计了回答数据集中每个值的个人总数，epsilon 值为 1 到 14，然后将其与实际值进行比较。结果如下（请原谅格式）。

如您所见，数据集的效用因 epsilon 值较低而受到很大影响。此外，当多次执行时，估计偏差相对较小，即使对于小的 epsilon 值也是如此。

例如，当估计回答 0 的参与者人数并使用 1 的 epsilon 时，所有估计似乎都以 1600 为中心，估计之间的最大距离为 100。考虑到此查询的实际值是5969，我被引导相信我可能实施了错误的东西。

这是广义随机响应机制的预期行为，还是我在实施过程中犯了错误？

Answer 1

max_v = 13
min_v = 0

for row in dataset:   #row就是dataset里的真实值
    coin = random.random()
    if coin <= p:
        p_dataset.append(row)
    else:
        ans = []
        if row == min_v:
            ans = np.arange(min_v + 1, max_v + 1).tolist()
        elif row == max_v:
            ans = np.arange(min_v, max_v).tolist()
        else:
            a = np.arange(min_v, row).tolist()
            b = np.arange(row + 1, max_v + 1).tolist()
            [ans.append(i) for i in a]
            [ans.append(i) for i in b]
        p_dataset.append(random.sample(ans, 1))  # 这其实有一点问题  应该是真实值以外的其他值 这样写还包括真实值

Answer 2

我觉得当得到假答案时，我们不能直接使用p_dataset.append(random.randint(0,13))，因为它包含真答案

局部差分隐私实现的广义随机响应

Generalized Random Response for local differential privacy implementation

python

data-mining

data-security