Apple 的微分隐私（differential privacy）

[geelaw]

今天密码学课上同学的 presentation 是关于 微分隐私 的。众所周知，Apple 从 iOS 10 开始引入微分隐私（最著名的例子是 emoji 统计）。课堂讨论中有一个传闻：

Apple 的 privacy budget 是 44。

如果你不了解 微分隐私，只要明白这个选择让用户在汇报数据的时候几乎没有什么实际的隐私即可。每次数据汇报的隐私参数至少是 2，这也几乎没有给出什么有用的隐私。

根据 Apple 的文档，实际上每天的 privacy budget 是 54。我不清楚这是 per user 还是 per device。

提示 隐私参数、budget 越大就越没有隐私。多次汇报数据时，隐私的消耗是各次汇报的参数之和。所谓 budget 是指一段时间内一个用户（或设备）产生消耗的上界（如果再次汇报会超过 budget，则取消这次可能的汇报）。

单个用户数据 对 噪音化统计数据 的影响（概率的相对误差）的上界随着隐私参数 指数上升。单个用户数据对统计数据的影响越大，隐私越难以保证。

That said, 在微分隐私里，统计数据的准确和用户的隐私有天然的 trade-off 之关系。而且理论上界和实际发生的隐私消耗也不一定很 match。

[sep22]

我很好奇，你为什么要把算每天的 privacy budget。苹果在数据汇报时用 differential privacy 了，不同的 activity 设置不同的 budget 至少是 2。在一定 utitlity 情况下，这么小的 budget 对不同的 activity 来说已经是相当低了。苹果对不同的 activity 进行数据汇报，这些 activity 拥有不同的 database。 你这样把所有 database 的 budget 加起来，算一个总的是没有意义的。

[geelaw]

@ding259336 #1 DP 介绍系列的第一个例子就是 Netflix+IMDb 的匹配，同一个群体（那个例子里是公众，这个例子里是 Apple ）掌握的数据库应该看成一个，隐私消耗需要合并计算。

至于你认为 cost 已经足够小，我说了准确性和隐私之间自带 trade-off。这里的点在于，Apple 的实现没有提供特别有意义的隐私。

[Mirage09]

“ budget 越大就越没有隐私”这句话有歧义吧？

[yuldx]

Really 难以 read。

[lekai63]

那么我是否可以制造假数据（更多的噪音）来加大甚至故意误导服 Apple 对我的隐私分析，从而使结果失真。
如果可行 如何做？

[LxExExl]

@lekai63 每天额外花时间和精力活得不像自己即可

[sep22]

@geelaw 这是因为 Netflix 和 imdb 是电影，属于同一类。而 apple 这边不同的 activity 有不同的 query 结果。如果算总得 privacy budget，要用 parallel composition.

[sep22]

@Mirage09 这话说的 privacy budget 太大对应的是说加的噪声太少，进而隐私保护程度越低。

[sep22]

@lekai63 我觉得 Apple 应该设置了一个 bound，如果你的值相比其他的区别太大，就不使用了。

[chenchangjv]

我一般叫 差分隐私

我觉得并不一定在 netflix 案例中隐私预算是按人分配的，在这个场景下就是如此。
差分隐私的差分，是针对于只有最小差别的数据库经过算法运行出来的结果的相似度做了约束，所以核心的点在于是否保护了在数据库有最小差异的时候，统计数据受影响的情况和概率。
所谓最小差距，就是多一条记录少一条记录的问题。如果苹果把一次上传作为一条记录插入数据库，我觉得每天的隐私预算上限在保护具体数据方面并不重要。毕竟差分隐私的前提，是抹掉任何标志信息，即使是同一个用户上传的数据，在收集者那里理论上应该不具备判断的可能性。在实际上可能会有 IP 地址等记录，所以限制了每天的总预算。

[chenchangjv]

在 netflix 中，每个用户对不同电影的喜好作为一条记录，但这个案例应该并不是如此。

[geelaw]

@lekai63 #5 在没有微分隐私的时候你已经可以这样做了。

我个人并不知道 Apple 是否分析每个人的数据，而且本帖里面的数据 Apple 公开表示的作用是进行统计。而你的个人数据是很难撼动 Apple 得到的用户群体的统计数据的。

@ding259336 #7 在 Netflix + IMDb 和 Apple 的案例之间有一个更大的区别：

- 在 Netflix + IMDb 引出的 MSR 的论文里和教科书初次介绍 DP 的时候，持有数据库的实体是发布统计数据的，噪音是持有数据库的实体增加的，而贡献数据记录的个体是没有进行噪音处理的。防范的是查看统计数据的实体。
- 在 Apple 的使用里，噪音是个体加上去之后提交给 Apple 的。这类似于“抛硬币法调查运动员嗑药率”。连“调查员”都是防范的。

虽然 Apple 发布了一些用户群体的统计信息，但是这里的隐私模型最应该关注的是：个体的隐私不能泄露给 Apple。而不是：Apple 不能因为发布数据而泄露用户的隐私。前者是一个比后者强得多的条件。

另一个理解 Apple 模型的方式是把每个用户当成响应 query 的角色。

我之前把它们加起来的方式，现在我不知道对不对。因为这个模型的差异使我们需要重新考虑微分隐私的合成。

然而，从直觉上考虑，这里的 privacy budget 放在一起加起来 makes sense，因为 Apple 把单个用户的不同部分的数据拿来混合分析没有数学上的障碍（至于 Apple 发布的统计数据是分离计算的，只能说明查看 Apple 发布数据的实体应该以 parallel composition 来处理，但从 Apple 的角度仍然是 sequential composition ）。

这里的防范对象首先是 Apple 而不是查看 Apple 发布的数据的实体（当然，防范了 Apple 自然也就防范了任何查看 Apple 发布数据的实体，因为隐私合成的缘故）。

Will look into that when I have time.

@chenchangjv #10 你需要注意：

> 我觉得每天的隐私预算上限在保护具体数据方面并不重要。

和

> ... 差分隐私的前提，是抹掉任何标志信息，即使是同一个用户上传的数据，在收集者那里理论上应该不具备判断的可能性。

是矛盾的。或者后面这一句本身 doesn't mean anything. 因为微分隐私“抹去的程度”是 priv. param. 决定的。

如果你只是想说用户发给 Apple 数据的时候不包括任何 PII，这件事情本身和 DP 没关系。我谈论的是 Apple 使用 DP **带来的** 隐私的多寡，抹除 PII 的贡献自然不能算在里面。

[lvybupt]

差分……

[chenchangjv]

差分隐私分为两个场景：
Centralized DP 传统的、存在一个可信的第三方保存所有的真实数据
Local DP （ LDP ） 不存在可信的第三方，用户上传的就是被干扰的数据。

@geelaw #12
差分隐私能够在一定程度上解决 Netflix 所遭遇的问题，但这不是它的初衷或者说主体思想。
你说的不信任 Apple 是差分隐私规则以外的问题。
差分预算并不可以简单相加，因为对每段数据来说差分预算的分配（或者说数据的干扰）都是整体进行的。
仅从物理意义上来讲，差分预算相加变多了，用户的属性（数据的维度）同样变多了，每个维度所泄露的隐私，并没有变化。

[3d3ec7a]

我记得中学数学学过一个调查统计方法: 让对方抛硬币, A 面就回答隐私问题, B 面就回答无关紧要的问题, 调查者不知道对方回答的是哪个问题(答案都是选项). 然后再怎么处理来着, 可以让结果符合统计规律.

[w01230]

……落后时代了~

[geelaw]

@chenchangjv #14 你的话前后矛盾。

> Local DP （ LDP ） 不存在可信的第三方，用户上传的就是被干扰的数据。

> 你说的不信任 Apple 是差分隐私规则以外的问题。

我的讨论假设 Apple 对于数据噪音化的操作是正确实现的，考虑的是用户面对收到数据的 Apple 的隐私问题。

“每个维度泄露的隐私”没有变大，但是“所有维度总体泄露的隐私”是变化的了。因为你可以通过多个维度综合确定一个人。

比如，认为先验是 (0/1/2, 0/1/2) 九种等可能，如果你知道第一个维度的分布应该改变为 7/18 7/18 2/9，则这导致 1.5 倍的概率变化，第二个维度的分布改变为 1/2 1/3 1/6，这导致了第二个维度上 2 倍的概率变化。

第一个维度的 pri. param. 是 log(1.5)，第二个维度的 pri. param. 是 log(2)。

这两个维度可以有相关性，DP 的论证是考虑最坏的 privacy guarantee。如果是独立的维度，联合分布里 (2, 2) 的可能变成了 1/27，概率的变化至少是 3 倍，pri. param. 是 log(3) = log(1.5) + log(2)。

注意：具体的分布和数据里面合成之后的 essential pri. param. 可能比相加要小，但是在一般（数学上的“一半”）情况下可以证明的最小的 pri. param. 是各个的和。

上面这个例子就是说我最开始的最后一句话：

> 而且理论上界和实际发生的隐私消耗也不一定很 match。

如果这个例子有点难想，你可以这么理解：考虑两个向量的和的长度，它不超过两个向量长度的和。

这里每个向量可以看作一个 pri. param.，“和”的操作可以理解为 composition。我们能做的是去证明这个 bound。但是对于具体的向量（也就是具体的噪音叠加），这个 bound 不一定是紧的。

[chenchangjv]

@geelaw #17

对不起我没太理解您的数学证明，也只是从您上面的回复里大概理解了您的问题。

我对您的问题的理解，就是用户上传了多维数据，通过多维数据的联合可以得到更多的信息量。

先说矛盾：
Apple 有明确说明会把所有的数据聚合在一起去做用户画像吗？
在 Apple 描绘的应用差分隐私的场景中，每一个独立的 database 都是符合差分隐私的吧？
您考虑的是 Apple 在收集以后把多维数据聚合起来，这是因为 Apple 作为一个收集者，承担了多个差分隐私过程中的收集者的角色，是这样吗？
如果我理解的没有问题，那么这能发生并不是差分隐私的问题。Apple 能够达到您所说的攻击的前提是能够将同一用户的不同维度数据聚合起来，这是因为她拥有差分隐私所要发布的信息以外的内容。

再说问题：
差分隐私已经不是最新的标准，确实存在问题，隐私保护也在探索之中。

我目前在做的只是差分隐私下的一些复杂数据的处理，在差分的缺陷方面无法帮助您。

另：
我无法理解您计算出隐私参数的问题，隐私参数一般是人为指定的，使用例如 Lap （ privacy param ）等方式加噪音到数据上。
我的理解：隐私参数是用来决定是否传递正确信息的一个概率，从信息的角度来说，是从原始数据中所要去除的信息量。

[geelaw]

@chenchangjv #18

> 我对您的问题的理解，就是用户上传了多维数据，通过多维数据的联合可以得到更多的信息量。

正确。

> Apple 有明确说明会把所有的数据聚合在一起去做用户画像吗？

隐私研究的目的是从数学或计算资源上保证坏事不会发生，而不是依靠信任。我没说 Apple 要去把数据合起来做画像，我甚至没说 Apple 要做任何画像。

你去考虑 Apple 是否值得信任、是否会做这件事，是完全背离该项研究的——这研究的目的是为了让人不需要考虑这个问题。

换成密码学更容易理解，加密是为了不需要保证没人窃听，而是有人窃听也可以。

> 在 Apple 描绘的应用差分隐私的场景中，每一个独立的 database 都是符合差分隐私的吧？

Apple 的文档里每个内容都是符合 DP 的，我的点在于这样的参数选取不带来实际的隐私保证。

> 如果我理解的没有问题，那么这能发生并不是差分隐私的问题。Apple 能够达到您所说的攻击的前提是能够将同一用户的不同维度数据聚合起来，这是因为她拥有差分隐私所要发布的信息以外的内容。

并不是，只是 DP 的参数选取问题。

> 我目前在做的只是差分隐私下的一些复杂数据的处理，在差分的缺陷方面无法帮助您。

我没有寻求你的帮助。

> 我无法理解您计算出隐私参数的问题，隐私参数一般是人为指定的，使用例如 Lap （ privacy param ）等方式加噪音到数据上。

你真的不是看了 Laplace mechanism 之后背公式吗？

数据库 curator 的模型下，形式化的表述是这样的：若 D 是一个数据库，F, G 分别是 D 上的 a/b-diff. priv. mechanism，则 (f, g) 是 (a+b)-diff. priv. 的。

这个命题 **并没有** 说 (f, g) 不是 (a+b-1)-diff. priv. 的。我不能理解这么一个简单的不等式放缩为什么会有问题。

再用向量举例子：u, v 的长度都是 1，这相当于你选择每个你支持的 query 的时候 priv. param. 是 1 ；接着你把 u 和 v 相加，在不引入其他条件下我们能说的最准确的话是“ u+v 的长度不超过 2 ”，但这不代表 u+v 的长度不可以是 1.1 ；同理，当你 compose 两个 priv. param. 是 1 的 mechanisms 之后，你得到的是一个 2-diff. priv. 的 mechanism，但这不代表这个新的 mechanism 一定不是 1.1-diff. priv.。

如果你有一个 1-diff. priv. 的 mechanism，它当然也是 2-diff. priv. 的。

[geelaw]

@geelaw #19

> 换成密码学更容易理解，加密是为了不需要保证没人窃听，而是有人窃听也可以。

应该是

> 换成密码学更容易理解，加密是为了不需要保证没人窃听，即使有人窃听也不会有什么损失。