anonymity 大数据时代下的隐私保护（二）

一.导言

大数据时代，越来越多的服务和产品是围绕用户数据构建的。虽然这带来了个性化服务，提高了服务质量和准确性，但在数据收集、使用和发布过程中，用户隐私不可避免地暴露出来。从历史上看，有很多公共数据暴露用户隐私的案例，比如美国在线和网飞。

我们的第一篇文章差异化隐私可以分为集中式差异化隐私和本地化差异化隐私。两种差异化隐私都可以保证单个用户的ε-差异化需求，但应用场景略有不同。主要回顾了几种典型的隐私保护方法和不足:k-匿名、l-多样性和t-贴近度，并简要介绍了ε-差分隐私。本文主要研究ε-差分隐私的背景和典型应用。从第二章开始，本文主要阐述了差分隐私的定义和典型架构，典型的加噪方法，集中式差分隐私和局域化差分隐私的区别，以及综合定理。接下来，在第三章中，论文主要阐述了差别隐私的定位方法及其在行业中的应用。其中重点介绍了谷歌的RAPPOR差别隐私系统定义2.1。随机函数为任意两个相邻的数据库D和D′以及A的任意输出0提供ε-差分隐私iff，和苹果的差别隐私系统图1:差异化隐私处理流程框架。数据收集器从用户那里收集数据，供数据分析师使用。。

二.差异隐私的背景介绍

2006年，辛西娅·德沃克等人首次提出了差别隐私的概念。与以往的自组织隐私保护方案不同，差分隐私的主要贡献在于提供了个人隐私泄露的数学定义。差异隐私的主要目的是最大化效用的查询结果，保证个人隐私的泄露不超过预设的ε。

2.1集中式和本地化的差异隐私

以上公式只适用于两种选择的ε-LDP。如果有D种选择，此时需要对上面的随机响应算法进行扩展，得到一个更常用的随机响应算法，称为广义随机响应。对于GRR算法，需要两步:扰动统计和校正。对数据集d中的用户输入/采样数据v本地运行扰动统计算法πGRR，得到:

算法运行得到y，并将结果发送到服务器。这里π grr满足ε LDP。在服务器上运行γ grr ，并获得:

其中I _ v = | {j | v = y j} |，即从服务器获取的样本数，相当于前面例子中的m。这样得到的γ grr是正义的，其方差大小为:

2.2.3符合差别隐私的k-匿名

一般认为k-匿名算法不能满足ε-差分隐私要求。这种认知在文献中已被证明是正确的。有趣的是，k-匿名算法通过做一些改进可以满足ε-差分隐私。具体操作步骤如下:

1.β采样。对数据集中的每个元组进行采样，使每个元组都有选择β大小的概率。

2.对采样数据进行独立于数据的归纳。比如每k个相邻年龄合并满足k-匿名。整个算法过程不考虑年龄分布，称为数据独立性。所以有些年龄段合并后可能不符合k匿名的要求。

3.筛选第二步的结果，从最终结果中剔除不符合k-匿名要求的数据。这样剩下的数据既满足k-匿名又满足ε-差分隐私。

整个证明过程可以参考条。

2.3集中式和本地化差异隐私比较

2.3.1可信和不可信数据收集器

集中式差异隐私的一个重要假设是可信的第三方数据收集器。每个用户都将自己的真实数据记录发送给一个可信的数据收集器。数据采集器会主动保护采集到的数据，并利用差分隐私算法为数据分析师提供查询服务。本地化差异隐私中的第三方数据收集器不需要被信任。每个用户根据差分隐私算法在本地处理数据，然后将处理后的数据上传到数据采集器。收据收集器看不到原始数据，因此不需要信任数据收集器。数据收集器接收查询请求并直接响应，无需集中的差异隐私。

2.3.2噪声机制

为了保证算法满足ε-差分隐私，集中式差分隐私和本地化差分隐私都需要噪声机制。集中式差分隐私的典型噪声机制有拉普拉斯噪声机制和指数噪声机制。拉普拉斯噪声机制用于处理连续数据，指数噪声机制针对离散数据。以上两种噪声机制与查询函数的全局敏感度密切相关，全局敏感度定义在D和D’之上，使得攻击者无法根据统计结果猜测任何个体的数据。在本地化的差异隐私中，每个用户都扰动自己的数据并上传，而任何两个用户都不知道别人的数据记录。也就是说，此时统计数据库d只有用户自己的记录。也就是说，局部差分隐私没有全局敏感的概念，所以拉普拉斯噪声机制和指数噪声机制不适用于局部差分隐私。本地化差异隐私主要利用随机响应技术来保护隐私。

2.4合成定理

当我们理解基本运算的隐私时，差分隐私的合成理论可以帮助我们理解和计算一个复杂算法的隐私。限制查询数量。为了保证一定的效用，一个统计数据库的查询总是会透露出一定程度的个人隐私。因此，查询次数有一个理论上限。根据Dinur Nissim Result的现实，一个有n条记录的数据库，在服务n × log2的查询后，即使每个查询的结果有O那么大的噪声，也可以重构。

顺序合成...

考虑到、、…、Mk是运行在统计数据库D中的不同的差分隐私算法，Mi满足εi差分隐私，这些算法依次执行后，总的隐私泄露仍然满足ε-差分隐私。这个差分隐私的大小是所有算法的差分隐私之和ε = ε 1+ε 2+...+ε k。

平行构图。

考虑到差分隐私算法m1、m2，...，MK分布在相邻的统计数据库D1，D2，...、DK和Mi满足εi差分隐私，这些算法并行执行后，总的隐私泄露仍然满足ε-差分隐私。这个差异隐私的大小最大ε = max{ε1，ε2，...，εk}在所有算法中。

后处理。

如果Mi满足ε-微分隐私，则其在统计数据库D中的输出结果记录为Mi。其他任意差分隐私算法Mj也满足Mi的输出mj )的ε-差分隐私。

三、差分隐私的典型应用

这一章主要阐述了差别隐私在行业中的应用:谷歌的RAPPOR，苹果的差别隐私。

3.1 RAPPOR差异隐私系统

单值频率统计是指每个用户只发送一个变量值的情况。用户将数据发送到数据采集器后，数据采集器根据已有的or统计得到候选值列表，统计每个候选值出现的频率并发布。

RAPPOR方法是Google提出的一种通用的差分隐私方法。这种方法可以收集用户的数据，保证ε的差异化隐私。RAPPOR可以统计连续数据或不连续数据。假设总共有n个用户，第I个用户Ui对应一个敏感值xi ∈X，并且| x |X|=k k，现在我们要统计值xi的频率。

此外，内部收益率结果s满足PRR结果B’的后处理，即内部收益率)，因此内部收益率的隐私保护也满足ε-微分隐私。与PRR相比，内部评级法在保护用户隐私方面向前迈进了一步。IRR结果直接隐藏PRR结果B’，使得服务器很难跟踪PRR结果。IRR允许用户给短期隐私添加更多的噪声，从而获得更强的短期隐私保护。最后， IRR允许短期隐私和长期隐私的独立调整，使用户在控制隐私时更加灵活。

4.报告数据。

第三步中生成的结果被提交给服务器。

3 . 1 . 2 rapper的典型品种

RAPPOR有三种典型的变体来处理不同条件下的不同隐私要求。

一次性RAPPOR。如果服务器只从用户那里收集一次数据，它可以跳过内部收益率步骤，直接报告PRR的结果。

基本RAPPOR。如果用户的数据V可以被确定性地映射到一个位串，RAPPOR可以跳过第一步，即bloom filter阶段，直接进行下面的步骤。例如，对于用户性别的采样，男性和女性可以分别对应一位。此时，h可以取值1。

基本一次性RAPPOR。这是以上两种模式的简单组合，用于最简单的情况。此时，RAPPOR可以直接跳过第一步和第三步。

RAPPOR系统已经在Github上开通。根据王等人的分析，有两组典型参数，可以命名为RAPPOR-1和RAPPOR-2。两个系统的ε值不同:RAPPOR-1中ε = 4.39，RAPPOR-2中ε = 7.78。在实际应用中，应避免局部差分隐私ε的值大于4。当ε >: 4时，用户隐私大概率恢复。

3.2苹果差异化隐私系统

2016年6月，苹果宣布使用本地化的差异隐私方法收集用户数据，从而保证了用户信息的隐私性。我们在苹果最近的系统macOS Sierra 和iOS 10中看到了使用差异隐私，但是苹果并没有公开介绍使用本地化差异隐私的细节，比如如何选择隐私参数，保证数据的可用性。

2017年9月，南加州大学、清华大学、印第安纳大学的唐俊等人发表了一篇关于苹果差别隐私实现方式的深入研究:苹果在MAC OS 10.12上实现差别隐私时的隐私损失。本文通过对macOS Sierra上的评分隐私框架进行逆向分析，找到苹果使用差别隐私的一些细节，包括差别隐私预算值，在哪里使用差别隐私，使用什么算法使用差别隐私，多久收集一次信息。

3.2.1苹果差异化隐私研究概述

本文采用逆向工程的方法，主要研究了macOS的以下模块:

差异隐私框架:/system/library/private framework/different privacy . frame owrk

Com.apple.dprivacyd守护程序

隐私后存储数据的数据库，位于/private/var/db/differential privacy

差异隐私框架配置文件:/system/library/差异隐私/configuration/

发送到服务器的报告文件以结尾。dpsub和。并存储在/library/logs/diagnostic reports和/private/var/db/differential privacy/reports/directory中

macOS中控制台的日志信息

通过逆向逻辑，推测苹果是在利用差异化隐私的细节。目的是回答以下问题:

我们知道在隐私数据进入数据库之前，苹果使用差分隐私算法使数据隐私化，那么隐私参数是什么？

苹果多久收集一次数据？一次收集多少数据？

特定用户的隐私总损失是多少，有什么限制吗？

修改这个差别隐私制度有多难？

3.2.2苹果差异化隐私系统实施细节

通过颠倒前面的模块，我们可以在表6中获得以下信息:

图6:苹果差异化隐私细节

从表中可以看出，苹果主要收集了输入法新词、表情符号使用频率、AppDeepLink的使用数据、健康数据和查询数据。对应的差异化隐私是“countmediansketch”和“one bit直方图”。此外，本文还引用了两个文件:algorithmparameters.plist和budgetproperties.plist..通过对相关文献的研究，发现PrivacyParameter的值规定了用于隐私数据的隐私参数。同时研究了报表生成方法和隐私预算管理，发现SessionAmount值指定了隐私后会收集多少条记录并发送给Apple。

同时，SessionAmount还为一个BudgeKeyName指定了剩余的隐私预算。剩余的隐私预算和会话安装用于确定将有多少记录写入报告文件。每隔18小时，守护进程将运行一个名为“报告生成器”的任务，该任务将根据会话安装值和剩余的隐私预算来计算向苹果报告多少数据。同时还有一个正在进行的任务叫做“PrivacyBudgetMaintenance”，会增加隐私预算。详细来说，每24小时，所有隐私预算都会增加。

通过以上结论，我们可以计算出苹果差分隐私的隐私损失:每会话秒损失的隐私参数数和会话量。因此，对于生词，appdeeplink，search，emoji，它们的PrivacyParameter是2，1，1，1，SessionSeconds是2，10，1，1 2，10，1，SessionSeconds是864000，所以每天的隐私总损失是16。

除了以上结论，本文还讨论了Apple在数据库管理中的一些任务，比如“StorageCulling”任务每24小时删除一次已经上报给Apple的记录。苹果使用不同的隐私参数，在不同版本的macOS上收集不同的数据。

3.2.3苹果差异化隐私的研究结论

最后，文章讨论了苹果本地部署差异化隐私的一些不足之处:

苹果没有向用户披露差异化隐私的参数，违背了差异化隐私的初衷:用户可以知道在数据采集过程中泄露了多少隐私。

正因为如此，苹果有意无意滥用差别隐私的功能来收集数据。比如通过修改一些隐私参数，苹果可以大大减少隐私数据量，使数据更加准确。

苹果隐私损失16/天，远高于研究领域对差异化隐私损失的合理定义。而且隐私损失会每天补充，长期影响总隐私损失。

由于苹果数据库的结构，用户的一些隐私还是会被泄露，比如用户的语言、地域、键盘偏好等等。

综上所述，本文通过反转苹果的差异化隐私框架，对苹果实施差异化隐私的细节有了详细的了解，发现了实施中的一些问题，使得隐私的损失越来越大。文章并没有过多讨论苹果的差分隐私算法，比如“CountMediansketch”和“one bit直方图”。根据名字，我们还是可以推测，可能会用到素描的相关统计算法。虽然理论上对差别隐私进行了充分的讨论，但在行业中刚刚开始使用，每一个细节的误用都会对用户的隐私造成很大的影响。

四.结论

本文首先介绍了差分隐私的基本概念，以及典型算法和典型差分隐私模型的区别。差分隐私理论上可以精确限制隐私泄露上限，这也是差分隐私相对于传统隐私保护方案的主要特点。然后文章重点介绍了行业内差异化隐私的两个例子:谷歌的RAPPOR系统和苹果的差异化隐私。这两个差异化隐私系统是本地化的差异化隐私，用来保护用户隐私的ε并不尽如人意。希望未来有更多的学者和企业加入到差分隐私的研究和应用中来，全面提高差分隐私的保护效果和算法效率。

引用

苹果。用户的工程隐私。https://developer。apple.com/videos/play/wwdc2016/709/.

苹果。Wwdc 2016主题演讲。2016年6月，https://www.apple.com/apple-events/。

辛西娅·德沃克，亚伦·罗斯，等。数字隐私的算法基础。理论计算机科学基础与趋势，9:211–407，2014。

彼得·凯鲁兹、苏翁·奥和普拉蒙德·维斯瓦纳。数字隐私的合成定理。《第32届国际机器学习会议论文集——第37卷，ICML’15，第1376-1385页。JMLR.org，2015年。

李宁辉，瓦尔达吉和苏东。可证明的私人数据匿名化:或者，k-匿名符合个人隐私。abs/1101.2604，01 2011。

孙、、。大数据时代的隐私保护。2017年8月。

Kobbi Nissim，Sofya Raskhodnikova，Adam Smith。私有数据分析中的平滑感知和采样。《第三十九届计算机理论年会论文集》，STOC 07年，第75-84页，美国纽约州纽约市，2007年。ACM。

考比·尼西姆、托马斯·斯坦克、亚历山德拉·伍德、弥迦·奥特曼、亚伦·本贝内克、马克·邦、马尔科·加博阿迪、大卫·奥布赖恩和萨里尔·瓦丹。《个人隐私:非技术应用入门》，2017年。

，科洛洛娃，白小龙，，王，。苹果在macos 10.12上实施个人隐私的隐私损失。CoRR，abs/1709.02753，2017。

王天浩、耶利米·布洛克、李宁辉和萨默什·贾。频率估计的本地专用协议。第26届USENIX安全研讨会，第729-745页，不列颠哥伦比亚省温哥华，2017年。USENIX协会。

乌尔法·埃尔林松、瓦西尔·皮胡尔和亚历山大·科罗洛娃。rappor:Ran-domined可聚合隐私保护顺序响应。在2014年亚利桑那州斯科茨代尔举行的第21届美国计算机学会计算机与通信安全会议的进程中。

*作者:程跃强、孙、、，请注明他们是人