混合差分隐私下的多个属性

Question

符号: eps_c (epsilon )，eps_l (epsilon )，n(用户数)，d(属性数)。单个属性A_i的|A_i|=r值可能与1，d中的i值不同。

让我们假设每个用户都持有d个离散属性(例如，A_1 =性别与2个值，A_2 =年龄范围与r_2值，A_d =小时在线24个值)。

一些像1这样的论文为广义随机反应模型提供了放大。如果是eps_c <=1，即中心隐私必须等于或小于1，这样才能放大eps_l (本地)。

如果我们想收集许多属性(d>1)：

1. 我们可以设置eps_split = eps_c /d <= 1吗？根据eps_split和d的值，这将意味着大于1的“总体”中心隐私。
2. 或者，对于人口n来说，eps_c = d*eps_split <=1是绝对必要的吗？这意味着，无论您想收集多少属性，只有当中央隐私保证保持在1以下或等于1时，放大才有效。

在同样的意义上，如果(2)成立的话，如果我们不对每个属性分割eps_c/d，而是随机抽取每个用户的单个属性，并将整个eps_c花在它上。放大使用n(假设完全随机抽样技术的用户总数)还是n/d (回答每个属性的用户数)？

1 Balle，B.，Bell，J.，Gascón，A.和Nissim，K.，2019年8月。洗牌模式的隐私毯子。在年度国际密码学会议上(第638至667页)。施普林格，查姆。

谢谢你在这个问题上的时间和帮助。

Answer 1

你所指的文件中的定理只假定\varepsilon<1，因为它简化了分析&无论\varepsilon的值如何，都会发生证明放大。如果你仔细看一下这个证明(第10页)，你会发现一个更严格的公式:结果适用于任何\varepsilon和\delta，比如\mathbb{P}\left[\frac{N_1}{N_2}\geq e^\varepsilon\right]\le\delta，其中N_1和N_2是从\text{Bin}\left(n-1,\frac{\gamma}{k}\right)抽样的自变量。

如果没有使用Chernoff界和关于\varepsilon的假设来限制这个量，而是用数值来估计它，那么得到的\varepsilon和\delta的值要小得多，这表明无论\varepsilon的值如何，都会发生放大。在我和他合著的论文中，我们就是这样做的；问题是不同的，但数学结果是一样的。这是定理3，您可以看到封闭形式公式与图2中的数值估计之间的比较。