一文读懂苹果的差分隐私技术

在 2016 年 6 月份的苹果 WWDC 大会上提到了一项差分隐私技术（Differential Privacy），其作用是对用户的数据进行扰动，然后上传到苹果服务器。苹果能通过这些扰动过的数据计算出用户群体的行为模式，但是对每个用户个体的数据却无法解析。

苹果通过采用差分隐私技术，实现了在不得到用户原始数据的前提下，学习用户行为。如果你想知道“数据可用不可见”背后的技术，就跟着我们一起来学习下苹果的差分隐私技术背后的原理吧！

一、简介

差分隐私是一种数据隐私保护技术，它通过在数据中引入随机化扰动的手段来保护隐私。简单来说，扰动后的数据是无法精确地推断出其原始值。同时，它允许对随机化后数据进行统计分析，保证了数据的有用性。差分隐私提供了衡量隐私的严格数学定义，是近些年来业界常见的一种隐私保护技术。

1.1 差分隐私应用场景

苹果使用本地化差分隐私（Local Differential Privacy）技术来收集用户设备上的信息，其部署的产品见下表 [1, 2]。

1.2 本地化差分隐私

在本地化差分隐私框架中，用户在上传的原始数据中添加噪声（扰动），服务器则无法知道用户的真实数据。这项技术最早是由 Warner 提出的随机响应（Randomized response）[3]。

本地化差分隐私技术可用于联合统计，比如计算平均数、中位数、频率直方图等。其算法框架（E-R-A-P）一般分为四个步骤：

用户端进行编码与随机化，保证传输的数据是扰动后的；服务器端进行聚合与后处理，得到相应的统计量。

二、苹果的方案

苹果的本地化差分隐私方案参见 [2, 4, 5]，其中 [4, 5] 是专利。这里介绍 [2] 中方案的简易版本，以统计表情包的频率直方图为例。

2.1 用户端

依照上面提到的 算法框架（E-R-A-P），用户端需要在上传数据之前对做原始数据做 编码(E) 和 随机化(R)。

编码(E)：编码是为了后续的随机化和聚合步骤。苹果的编码采用哈希表的方式，初始表中的元素均为“-1”。然后通过哈希函数hhh将元素ddd（使用频率最高的表情包）映射到位置h(d)h(d)h(d)，并标记“1”。假设哈希表的长度为mmm（聚合时会用到该参数）。

随机化 (R)：随机化是差分隐私中的关键步骤，保证了数据的隐私性。由于编码后的数据都是“1”和“-1”，让每个比特以设定的概率ppp翻转，即“1”变为“-1”或“-1”变为“1”。其中p=1/(1+eϵ/2)p=1/(1+e^{epsilon/2})p=1/(1+eϵ/2)，ϵepsilonϵ称为隐私预算，将在 第 2.4 节阐述。

2.2 服务器端

依照上面提到的 算法框架（E-R-A-P），服务器端需要在接收到数据后对做“扰动”后的数据做 聚合(A) 和 后处理(P)。

聚合 (A)：由于每个用户上传的数据都是扰动后的，聚合可以消除部分噪声的影响。假设共有nnn个用户，服务器收到用户iii的哈希表为v(i)v^{(i)}v(i)。服务器首先计算：

x(i)=cϵv(i)+12x^{(i)}=frac{c_epsilon v^{(i)}+1}{2}x(i)=2cϵ​v(i)+1​，其中cϵ=eϵ/2+1eϵ/2−1c_epsilon=frac{e^{epsilon/2}+1}{e^{epsilon/2}-1}cϵ​=eϵ/2−1eϵ/2+1​

然后将所有xxx的对应位置累加，得到MMM，即

M=∑i=1nx(i)M=sum_{i=1}^n x^{(i)}M=i=1∑n​x(i)

则统计元素ddd的个数f~(d)tilde{f}(d)f~​(d)的公式如下，其中Mh(d)M_{h(d)}Mh(d)​表示MMM在位置h(d)h(d)h(d)的值

f~(d)=mm−1(Mh(d)−nm)tilde{f}(d)=frac{m}{m-1}Big(M_{h(d)}-frac{n}{m}Big)f~​(d)=m−1m​(Mh(d)​−mn​)

可以证明f~(d)tilde{f}(d)f~​(d)为f(d)f(d)f(d)的无偏估计，即E[f~(d)]=f(d)mathbb{E}[tilde{f}(d)]=f(d)E[f~​(d)]=f(d)，其中f(d)f(d)f(d)为元素ddd的真实个数。这意味着估计值的期望与真实值的偏差为零，保证了估计值的无偏性。

后处理 (P)：在不同应用场景中，计算的统计量可能有先验知识，比如取值范围的限制（如大于 0），或者保持加和不变（如统计个数），这时就需要进行后处理操作。差分隐私的性质使得任何后处理操作均不影响其结果的隐私性。

2.3 其他技术

数据隐私保护需要考虑的方面很多，仅使用差分隐私技术无法解决所有的问题。苹果在方案中还使用了其他技术来保护数据隐私，例如数据脱敏、通信加密、访问控制等。

2.4 隐私预算

看到这里大家应该明白了，差分隐私是通过在增加噪声（扰动）来实现隐私保护，但由于扰动增加，聚合的结果会变得不精确（统计量的方差增大）。所以下面介绍平衡算法的隐私性和实用性的隐私预算ϵepsilonϵ。

在差分隐私中隐私预算ϵepsilonϵ的选取会同时影响算法的隐私性与实用性，称为 Privacy-Utility 之间的权衡（trade-off）。较小的隐私预算ϵepsilonϵ意味着较强的隐私保护能力。例如，数据比特随机化扰动的概率p=1/(1+eϵ/2)p=1/(1+e^{epsilon/2})p=1/(1+eϵ/2)，减小ϵepsilonϵ的取值会使得ppp增大，因此隐私泄漏的风险会降低，但此举也会影响结果的精确性。

而且，虽然数据添加了差分隐私扰动，但同一用户会不断地上传新数据，根据差分隐私的串型组合定理，隐私预算ϵepsilonϵ会随着时间累积逐步增加。因此，苹果限制了用户每天上传数据的最大次数，并表示数据最多只会留存三个月。

有研究 [6] 指出，苹果应该解释是如何设置隐私预算ϵepsilonϵ的取值的，告知用户并将其透明化。例如，虽然 Emoji 产品中宣称的隐私预算ϵepsilonϵ取值为 1，但通过代码逆向工程后发现其取值为 2（iOS 10.1.1 和 MacOS 10.12.3 版本的数据）。而且，隐私预算随时间累积也是其方案存在的一个重要问题。

三、方案优化

第 2 节中描述的是方案的简易版，而苹果的方案针对通信、统计量的精确性、场景适配等均做了优化 [2]如下：

四、无偏估计证明

这里依旧是按照 算法框架（E-R-A-P）顺序进行讲解，证明f~(d)tilde{f}(d)f~​(d)是f(d)f(d)f(d)的无偏估计。

4.1 编码

用户iii的哈希表为v(i)v^{(i)}v(i)，元素ddd在表中的映射位置为h(d)h(d)h(d)，其对应编码的取值为vh(d)(i)v^{(i)}_{h(d)}vh(d)(i)​。用户iii上传的元素为d(i)d^{(i)}d(i)，其对应位置的编码值为“1”，哈希表的其余位置为“-1”。因此当d(i)=dd^{(i)}=dd(i)=d时，vh(d)(i)v^{(i)}_{h(d)}vh(d)(i)​的期望为

E[vh(d)(i)]=1mathbb{E}[v^{(i)}_{h(d)}]=1E[vh(d)(i)​]=1

由于哈希表可能会存在碰撞（冲突），即不同元素标记到了同一位置。假设数据映射到不同位置的概率是相同的，则碰撞概率为 1/m1/m1/m。因此当d(i)≠dd^{(i)}neq dd(i)=d时，vh(d)(i)v^{(i)}_{h(d)}vh(d)(i)​ 的期望为

E[vh(d)(i)]=1m⋅ 1+(1−1m)⋅(−1)=2m−1mathbb{E}[v^{(i)}_{h(d)}]=frac{1}{m}cdot 1+Big(1-frac{1}{m}Big)cdot(-1)=frac{2}{m}-1E[vh(d)(i)​]=m1​⋅ 1+(1−m1​)⋅(−1)=m2​−1

因此vh(d)(i)v^{(i)}_{h(d)}vh(d)(i)​的期望为

E[vh(d)(i)]=I{d(i)=d}+(2m−1)I{d(i)≠d}mathbb{E}[v^{(i)}_{h(d)}]=mathbb{I}{d^{(i)}=d}+Big(frac{2}{m}-1Big)mathbb{I}{d^{(i)}neq d}E[vh(d)(i)​]=I{d(i)=d}+(m2​−1)I{d(i)=d}

4.2 随机化

随机化时比特翻转的概率为p=1/(1+eϵ/2)p=1/(1+e^{epsilon/2})p=1/(1+eϵ/2)。假设随机变量B∈{−1,1}Bin{-1,1}B∈{−1,1}，Pr⁡(B=−1)=pPr(B=-1)=pPr(B=−1)=p。

E[B]=p⋅(−1)+(1−p)⋅ 1=1−2p=eϵ/2−1eϵ/2+1=1cϵmathbb{E}[B]=pcdot(-1)+(1-p)cdot 1=1-2p=frac{e^{epsilon/2}-1}{e^{epsilon/2}+1}=frac{1}{c_epsilon}E[B]=p⋅(−1)+(1−p)⋅ 1=1−2p=eϵ/2+1eϵ/2−1​=cϵ​1​，其中cϵ=eϵ/2+1eϵ/2−1c_epsilon=frac{e^{epsilon/2}+1}{e^{epsilon/2}-1}cϵ​=eϵ/2−1eϵ/2+1​

用户iii随机化后的哈希表为Bv(i)Bv^{(i)}Bv(i)，元素ddd在表中的编码值为Bvh(d)(i)Bv^{(i)}_{h(d)}Bvh(d)(i)​。

E[Bvh(d)(i)]=E[B]⋅E[vh(d)(i)]=1cϵE[vh(d)(i)]mathbb{E}[Bv^{(i)}_{h(d)}]=mathbb{E}[B]cdotmathbb{E}[v^{(i)}_{h(d)}]=frac{1}{c_epsilon}mathbb{E}[v^{(i)}_{h(d)}]E[Bvh(d)(i)​]=E[B]⋅E[vh(d)(i)​]=cϵ​1​E[vh(d)(i)​]

4.3 聚合

服务器对随机化后的哈希表进行转换，即计算xxx。元素ddd在用户iii哈希表转换后映射位置的编码值为xh(d)(i)x^{(i)}_{h(d)}xh(d)(i)​，

xh(d)(i)=cϵ Bvh(d)(i)+12x^{(i)}_{h(d)}=frac{c_epsilon B v^{(i)}_{h(d)}+1}{2}xh(d)(i)​=2cϵ​ Bvh(d)(i)​+1​

当d(i)=dd^{(i)}=dd(i)=d时，E[cϵ Bvh(d)(i)]=1mathbb{E}[c_epsilon Bv^{(i)}_{h(d)}]=1E[cϵ​ Bvh(d)(i)​]=1，故

E[xh(d)(i)]=1mathbb{E}[x^{(i)}_{h(d)}]=1E[xh(d)(i)​]=1

当d(i)≠dd^{(i)}neq dd(i)=d时，E[cϵ Bvh(d)(i)]=2m−1mathbb{E}[c_epsilon Bv^{(i)}_{h(d)}]=frac{2}{m}-1E[cϵ​ Bvh(d)(i)​]=m2​−1，故

E[xh(d)(i)]=1mmathbb{E}[x^{(i)}_{h(d)}]=frac{1}{m}E[xh(d)(i)​]=m1​

因此xh(d)(i)x^{(i)}_{h(d)}xh(d)(i)​的期望为

E[xh(d)(i)]=I{d(i)=d}+1mI{d(i)≠d}mathbb{E}[x^{(i)}_{h(d)}]=mathbb{I}{d^{(i)}=d}+frac{1}{m}mathbb{I}{d^{(i)}neq d}E[xh(d)(i)​]=I{d(i)=d}+m1​I{d(i)=d}

将所有的xxx累加，计算MMM，元素ddd在MMM中映射位置的编码值为Mh(d)M_{h(d)}Mh(d)​，

Mh(d)=∑i=1nxh(d)(i)M_{h(d)}=sum_{i=1}^n x^{(i)}_{h(d)}Mh(d)​=i=1∑n​xh(d)(i)​

计算其期望，其中f(d)f(d)f(d)是元素ddd的真实个数

E[Mh(d)]=E[∑i=1nxh(d)(i)] =∑i=1nI{d(i)=d}+1m∑i=1nI{d(i)≠d} =f(d)+1m(n−f(d))=m−1mf(d)+nmbegin{aligned}
mathbb{E}[M_{h(d)}]&=mathbb{E}Big[sum_{i=1}^n x^{(i)}_{h(d)}Big] \
&=sum_{i=1}^nmathbb{I}{d^{(i)}=d}+frac{1}{m}sum_{i=1}^nmathbb{I}{d^{(i)}neq d} \
&=f(d)+frac{1}{m}Big(n-f(d)Big) \
&=frac{m-1}{m}f(d)+frac{n}{m}
end{aligned}E[Mh(d)​]​=E[i=1∑n​xh(d)(i)​] =i=1∑n​I{d(i)=d}+m1​i=1∑n​I{d(i)=d} =f(d)+m1​(n−f(d))=mm−1​f(d)+mn​​

由于f~(d)tilde{f}(d)f~​(d)是元素ddd个数的统计值，其计算公式为

f~(d)=mm−1(Mh(d)−nm)tilde{f}(d)=frac{m}{m-1}Big(M_{h(d)}-frac{n}{m}Big)f~​(d)=m−1m​(Mh(d)​−mn​)

所以

E[f~(d)]=f(d)mathbb{E}[tilde{f}(d)]=f(d)E[f~​(d)]=f(d)

即f~(d)tilde{f}(d)f~​(d)是f(d)f(d)f(d)的无偏估计。

统计量的方差小才意味着估计的精确性高。关于统计量f~(d)tilde{f}(d)f~​(d)方差的证明请参考。

以上通过数据推导的方式证明了苹果采用的「差分隐私」算法的准确性，可以实现在“数据可用不可见”的情况下实现统计计算。

五、最后

看似“高不可攀”的差分隐私技术，其实早已走进了我们的日常生活和工作中，为我们的个人隐私保驾护航。

本文通过通俗易懂的图文和严谨的公式推导，讲解了苹果的差分隐私技术原理，希望能够勾起你对隐私计算技术的兴趣。最后，如果你还有什么想了解的隐私计算相关技术，欢迎留言告诉我们！

PrimiHub 一款由密码学专家团队打造的开源隐私计算平台。我们专注于分享数据安全、密码学、联邦学习、同态加密等隐私计算领域的技术和内容。

参考文献

[1] Apple Differential Privacy Technical Overview. www.apple.com/privacy/doc…

[2] Differential Privacy Team, Apple. "Learning with privacy at scale." (2017). docs-assets.developer.apple.com/ml-research…

[3] Warner, Stanley L. "Randomized response: A survey technique for eliminating evasive answer bias." Journal of the American Statistical Association 60, no. 309 (1965): 63-69. www.jstor.org/stable/2283…

[4] Thakurta, Abhradeep Guha, Andrew H. Vyrros, Umesh S. Vaishampayan, Gaurav Kapoor, Julien Freudiger, Vivek Rangarajan Sridhar, and Doug Davidson. "Learning new words." Granted US Patents 9645998 (2017). patents.google.com/patent/US96…

[5] Thakurta, Abhradeep Guha, Andrew H. Vyrros, Umesh S. Vaishampayan, Gaurav Kapoor, Julien Freudinger, Vipul Ved Prakash, Arnaud Legendre, and Steven Duplinsky. "Emoji frequency detection and deep link frequency." Granted US Patents 9705908 (2017). patents.google.com/patent/US97…

[6] Tang, Jun, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and Xiaofeng Wang. "Privacy loss in apple's implementation of differential privacy on macos 10.12." arXiv preprint arXiv:1709.02753 (2017). arxiv.org/pdf/1709.02…