2.2.3符合差分隐私的k-anonymity
通常大家认为k-anonymity 算法是无法满足 ε-差分隐私需求的。这个认知在文章[5] 里面被证明是正确的。有趣的是,对k-anonymity 算法进行一些改进,就可以使其符合 ε-差分隐私。具体操作步骤如下:
1. β-采样(β-sampling)。对数据集里面的每一个tuple 进行采样,使得每个tuple 都 有 β 大小的概率被选中。对采样后的数据,进行数据无关的泛化(data-independent generalization)。比如每k 个相邻年龄进行合并,使其满足k-anonymity。整个算法过程不考虑年龄分布,也就是 所谓的数据无关。因此会有些年龄段合并之后,可能无法满足k-anonymity 的要求。3. 对第二步产生的结果进。
2.行筛选,把不满足k-anonymity 要求的数据从最终结果中 剔除出去。这样,剩下的数据既满足k-anonymity 又满足 ε-差分隐私。 整个过程的证明过程可以参考文章[5]。
2.3 中心化和本地化差分隐私比较
2.3.1可信与不可信的数据收集者
中心化差分隐私中一个重要的假设是可信第三方数据收集者。每个用户将自己的真实数 据记录发送给可信的数据收集者。数据收集者会主动保护收集的数据,并使用差分隐私 算法向数据分析者提供查询服务。本地化差分隐私中第三方数据收集者不需要可信。每 个用户按照差分隐私算法在本地对数据进行处理,然后把处理之后的数据上传给数据收 集者。收据收集者无法看到原始数据,因此不需要数据收集者可信。数据收集者接收查 询请求,并直接进行响应,无需在进行中心化的差分隐私。
2.3.2噪音机制
为保证算法满足 ε-差分隐私,中心化差分隐私和本地化差分隐私都需要噪声机制。中心 化差分隐私的典型噪音机制是:拉普拉斯噪音机制[3] 和指数噪音机制[3]。其中拉普拉斯噪音机制用来处理连续型数据,而指数噪音机制针对离散型数据。上述两种噪声机制均与查询函数的全局敏感性密切相关,而全局敏感性则是定义在D 和D’ 之上,使 得攻击者无法根据统计结果推测任何一个个体的数据。在本地化差分隐私中,每个用户将自己的数据进行扰动后上传,而任意两个用户之间并不知晓其他人的数据记录。也就是说这个时候的统计数据库D 就只有用户自己的记录。也就是说本地化差分隐私中不 存在全局敏感性的概念,因此拉普拉斯噪音机制和指数噪音机制对本地化差分隐私并不 适用。本地化差分隐私主要采用随机响应技术[3] 来保护隐私。
2.4 合成定理
当我们了解了基础操作的隐私情况,差分隐私的合成定理(Composition Theorem)[4] 可以帮助我们理解和计算一个复杂的算法的隐私。查询次数的上限(Bound on the Number of Queries). 为了保证一定的utility,对于一个统计数据库的查询总会或多 或少的泄露一定程度的个人隐私。因此,这里存在着一个理论上的查询次数上限。根据Dinur Nissim Result 现实,一个拥有n 条记录的数据库,在服务n ×log(n)2 查询之 后, 就可以被重建出来,即使每次查询的结果都有高达O(√n)的噪音。
顺序组合(Sequential Composition). 考虑M1, M2, ..., Mk 是在统计数据库D 跑 的不同的差分隐私算法,而且Mi 满足 εi 差分隐私,这样在顺序执行这些算法之后,总 的隐私泄露仍然满足 ε-差分隐私。这个差分隐私大小为所有算法差分隐私的总和 ε= ε1 + ε2 + ···+ εk。
并行组合(Parallel Composition). 考虑差分隐私算法M1, M2, ..., Mk 分布跑在在相 邻的统计数据库D1,D2,...,Dk 上面,而且Mi 满足 εi 差分隐私,这样在并发执行这些 算法之后,总的隐私泄露仍然满足 ε-差分隐私。 这个差分隐私大小为所有算法差分隐 私中最大的 ε= max{ε1, ε2, . . . , εk}。
后续处理(Postprocessing). 如果Mi 满足 ε-差分隐私,其在统计数据库D 的输出 结果记为Mi(D)。其他任意差分隐私算法Mj 对于Mi 的输出Mj(Mi(D)) 同样满足 ε-差分隐私。
3 差分隐私的典型应用
这章主要讲解差分隐私在工业界的应用: (1)Google 的RAPPOR,和(2)Apple 的差分 隐私。
3.1 RAPPOR 差分隐私系统
单值频数统计是指每个用户只发送一个变量取值的情形, 用户将数据发送给数据收集 者后, 数据收集者根据已有的或统计得到候选值列表, 统计其中每一个候选值的频数并 进行发布。
RAPPOR 方法是Google 提出的一个通用的差分隐私方法。该方法可以采集用户的数 据并保证 ε 的差分隐私。RAPPOR 可以统计连续型数据(比如年龄),也可以统计非连 续型数据(比如国家)。假设总共有n 个用户,第i 个用户Ui 对应某个敏感取值xi ∈X, 且|X|=k,现在希望统计取值xi(1 ≤i ≤k) 的频数。
图5: RAPPOR 应用实例。真实的值经过bloom lter,PRR 和IRR 之后, 汇报给服务器。最后的数据(256bits) 中有145bits 为1。
3.1.1 RAPPOR 算法
RAPPOR 算法需要以下几个参数运行。用户可以根据需要调节这几个参数: •k 为bloom filter 产生的数据大小。图5 的例子中k=256。
h 为hash 函数的个数。图5 的例子中h = 4。
f 决定PRR 中每一个bit 翻转的概率。图5的例子中f=0.5。
p 决定IRR 中bit 为1 的翻转概率。图5 的例子中p=0.75。
q 决定IRR 中bit 为0 的翻转概率。图5 的例子中q=0.5。 当确定参数之后,RAPPOR 算法输入要收集的真实数据v(图5 中v 是68),并执行以 下四个步骤。
1.布隆过滤。对用户的真实数据v,运行h 个hash 函数H = {H1,H2,...,Hh},每个hash 函数输入一个k长的数组[k] = {0, 1, . . . , k−1}.。整合所有输入,得到一个k 长 的数组B。
2/永久性随机响应(Permanent Randomized Response,or PRR)。对生成的数组B 的 每一个bit i (0 ≤i < k),进行随机翻转,生成新的数组Bi′。翻转概率公式如下所示:
这里值得注意的是,以后任何需要使用B 的时候,都需要使用相同的Bi′,否则可能会 有”averaging” 攻击[11]。这一步之后,用户的数据就已经获得 ε-差分隐私保护了。
3.瞬时性随机响应(Instantaneous Randomized Response,or IRR)。
申请一个k 个bit 长的数组S,并把每个bit 初始化为0。然后根据B′ 的每一个bit, 对S 的相应bit 进行初始化:
而且IRR 的结果S 满足对PRR 结果B′ 的postprocessing,即IRR(PRR(v)),使得IRR 的隐私保护同样满足 ε-差分隐私。相对于PRR,IRR 对于保护用户隐私又前进了一 步。(1)IRR 的结果直接隐藏了PRR 的结果B′,使得服务器端很难跟踪PRR 的结果。(2)IRR 允许用户对于短期隐私加入更多噪音,从而获得更强的短期隐私的保护。最后(3),IRR 允许独立的调节短期隐私和长期隐私,使得用户更加灵活的控制自己的隐私。
4.汇报数据。 第三步产生的结果S,提交给服务器
3.1.2 RAPPOR 的典型变种
RAPPOR 还有三种典型的变种来应对不同条件下的差分隐私要求。
One-time RAPPOR. 如果服务器只对用户进行一次数据收集,这个时候就可以跳 过IRR 的步骤,直接报告PRR 的结果。
Basic RAPPOR. 如果用户的数据v 可以确定性的映射到一个bit 串,这个时候RAPPOR 可以跳过第一步,即bloom filter 的阶段,直接进行后面的步骤。比如,对于用 户性别的采样,男性和女性可以分别对应一个 bit。这个时候h 取值为1 即可。Basic One-time RAPPOR. 这个是上面两种模式的简单组合,用于最简单的情况。这个 时候RAPPOR 可以直接跳过第一步和第三步。
RAPPOR 系统已经在Github 上面开源(google/rappor)。根据Wang et al. [10] 的 分析,里面有两套典型的参数,可以命名为RAPPOR-1 和RAPPOR-2。两个系统的 ε 取值不同:RAPPOR-1 里面 ε= 4.39,而RAPPOR-2 里面 ε= 7.78。实际应用当中, 本地化差分隐私 ε 的取值应该避免大于4。当 ε> 4 的时候,用户的隐私会被很大概 率恢复出来。
3.2 苹果差分隐私系统
2016 年6 月,苹果宣布使用本地化差分隐私方法收集用户数据[1, 2], 从而保证用户 信息的隐私性。我们在苹果最近的系统macOS Sierra (10.12)和iOS 10 中都看到了 差分隐私的使用,但是苹果没有公开详细介绍使用本地化差分隐私的细节,比如如何选择 隐私参数,同时保证数据的可用性。
2017 年9 月,来自南加州大学、清华大学、印第安纳大学的Jun Tang 等人在arxiv.org 上发表了一篇深入研究苹果差分隐私实现方法的文章: Privacy Loss in Apple’s Implementation of Differential Privacy on MacOS 10.12 [9]。本篇文章 通过逆向分析macOS Sierra 上的查分隐私框架,发现苹果在使用差分隐私的一些细 节,包括差分隐私预算数值,在哪些地方使用了差分隐私,使用差分隐私的算法有哪些,收 集信息的频率等等详细信息。
3.2.1苹果差分隐私研究概述
这篇文章使用了逆向工程的方法,主要研究了macOS 的以下几个模块:差分隐私框架: /System/Library/PrivateFrameworks/DifferentialPrivacy.frameowrk com.apple.dprivacyd 守护进程(daemon)
存放隐私后数据的数据库,地址在/private/var/db/DifferntialPrivacy
差分隐私框架的配置件:/System/Library/DifferentialPrivacy/Configuration/ 发送给服务器的报告文件,文件名以.dpsub 和.json.anon结尾,存放在/Library/Logs/DiagnosticReports 和/private/var/db/DifferentialPrivacy/Reports/ 目录中
macOS 中控制台的日志信息
通过逆向逻辑,推测苹果在使用差分隐私的细节。目的是想回答以下几个问题:
我们知道隐私数据在进入数据库之前,苹果通过差分隐私的算法使数据隐私化,那么隐私 参数(privacy parameters)是多少?
苹果在收集数据时有多频繁?每次收集多少数据? 对于一个特定的用户,总的隐私损失(privacy loss)是多少,是否有限制? 修改这个差分隐私系统的难度如何?
3.2.2苹果差分隐私系统实现细节
通过逆向之前介绍的几个模块,我们能得到以下表格6 的信息:
图6: 苹果差分隐私详细数据
从表格中我们可以看到,苹果主要收集了输入法的新词语、emoji 的使用频 率,AppDeepLink 的使用数据,健康数据,查询数据。对应的差分隐私算 有 “CountMedianSketch”,“OneBitHistogram”。除此之外,文章还参考了algorithmparameters.plist 和budgetproperties.plist 两个文件。 通过对相关文件 的研究发现,PrivacyParameter的数值规定了用于隐私化数据的隐私参数。文章同时研 究了报告的生成方法和隐私预算的管理,发现SessionAmount 数值规定了有多少记录将被收集，隐私化后传给苹果。同时SessionAmount 也规定了对于一个BudgeKeyName 的剩余隐私预算有多少。 剩余的隐私预算和SessionAmount 用 做决定有多少记录将被写入报告文件中。每隔18 个小时,守护进程将运行一个叫做 “ReportGenerator” 的任务,这个任务会根据SessionAmount 数值以及隐私预算 剩余算出又多少数据将会上报给苹果。同时,有一个不断执行的任务叫 “PrivacyBudgetMaintenance”会提高隐私预算,详细的讲,每隔24 个小时,所有的 隐私预算(除了health 和默认值)将会增加。
通过以上结论,我们能够计算出苹果差分隐私的隐私损失(privacy loss) : 每隔SessionSeconds 损失PrivacyParameter ·SessionAmount 的数量。所以,对于NewWords,AppDeepLink, Search, Emoji, 他 们 的PrivacyParameter 是2,1,1,1,SessionAmounts 是2,10,1,1,SessionSeconds 是864000,所以,每天总的 隐私损失是16。
除了以上结论,文章还讨论了苹果在管理数据库的一些任务,比如说“StorageCulling” 任务每隔24 小时会删除已经报告给苹果的记录。苹果在不同版本的macOS 上使用 的隐私参数也不同,收集的数据也有所不同。
3.2.3苹果差分隐私研究结论
文章最后讨论了苹果这种本地部署差分隐私方式存在的一些缺点:
苹果没有给用户公开差分隐私的参数,这违背了差分隐私的初衷:用户能够了解在收集数 据的过程中有多少隐私泄露出去。 正因为如此,使得苹果有意或无意的滥用差分隐私的功能收集数据,比如说,通过修改某 些隐私参数,苹果可以大大的降低隐私化数据的数量,使数据更精确。 苹果的隐私损失是16/天,这大大高于研究界对于差分隐私损失的合理定义,不仅如此, 隐私损失每天都会补充,长时间会影响总的隐私损失。 因为苹果数据库的结构,用户的某些隐私还是会被泄露,比如说用户的使用语言,地域,键 盘偏好等等。 总结来讲,这篇文章通过逆向苹果差分隐私框架,详细的了解了苹果在实现差分隐私当中 的细节,发现了一些实现上的问题,使得隐私损失不断变大。文章并没有对于苹果的差分 隐私算法做过多的讨论,比如说 “CountMedianSketch”,“OneBitHistogram”。根 据名称,我们还是能够推测可能是使用了sketch 的相关统计学算法。差分隐私虽然在 理论上讨论的比较充分, 在工业界的使用才刚刚开始,每个细节的错误使用都会对用户 的隐私造成巨大的影响。
4 结论
本文首先介绍了差分隐私的基础概念,典型算法和典型的差分隐私模型的区别。差分隐 私能够从理论上准确的限定隐私泄露的上限,这也是它优于传统的隐私保护方案(k-anonymity,l-diversity 和t-closeness)的主要特点。 随后文章重点讲解两个工业 界的差分隐私的例子:Google 的RAPPOR系统和苹果的差分隐私。这两个差分隐私 系统都是本地化差分隐私(LDP),所使用的 ε 对用户隐私的保护还不尽如人意(尤其是苹果的差分隐私)。希望以后有更多的学者和企业加入到差分隐私的研究和应用当中,全 面提高差分隐私的保护效果和算法效率。
参考文献
[1] Apple. Engineering privacy for your users. https://developer. apple.com/videos/play/wwdc2016/709/.
[3] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of di erential privacy. Foundations and Trends® in Theoretical Computer Science, 9(3–4) :211–407, 2014
[4] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for di erential privacy. In Proceedings of the 32Nd International Conference on International Conference on Machine Learning - Volume 37, ICML’15, pages 1376–1385. JMLR.org, 2015.
[5] Ninghui Li, Wahbeh H. Qardaji, and Dong Su. Provably private data anonymization: Or, k-anonymity meets di erential privacy. abs/1101.2604, 01 2011.
[6] Sun Mingshen and Wei Tao. 大数据时代下的隐私保护. August 2017.
[7] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sen- sitivity and sampling in private data analysis. In Proceedings of the Thirty-ninth Annual
ACM Symposium on Theory of Computing, STOC ’07, pages 75–84, New York, NY, USA, 2007. ACM
[8] Kobbi Nissim, Thomas Steinke, Alexandra Wood, Micah Altman, Aaron Bembenek, Mark Bun, Marco Gaboardi, David O’Brien, and Salil Vadhan. Di erential privacy: A primer for a non-technical audi- ence (preliminary version), 2017.
[9] Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and XiaoFeng Wang. Privacy loss in apple’s implementation of di erential privacy on macos 10.12. CoRR, abs/1709.02753, 2017.
[10] Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. Lo- cally di erentially private protocols for frequency estimation. In 26th USENIX Security Symposium (USENIX Security 17), pages 729–745, Vancouver, BC, 2017. USENIX Association.
[11] úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Ran- domized aggregatable privacy-preserving ordinal response. In Proceed- ings of the 21st ACM Conference on Computer and Communications Security, Scottsdale, Arizona, 2014.
来源：百度开发者中心