大数据时代下的隐私保护(一）
1 引言在大数据的时代,越来越多的服务和产品是围绕用户数据(隐私)建立的。这样虽然带来了 个性化的服务,提高了服务质量和精度,但是在数据收集、使用以及公布的过程中,用户隐 私不可避免的暴露在外。历史上就有很多公开的数据暴露了用户隐私的案例,比如AOL 和Netflix 隐私泄露事件。
我们的第一篇文章 主要回顾了几种典型的保护隐私的方法和不足:k- anonymity(k- 匿 名 化),l-diversity(l- 多 样 化),t-closeness, 并 简 单 介 绍 了 ε-differential privacy(差分隐私)。这篇文章,我们着重讲解 ε-differential privacy(差 分隐私) 的背景和典型应用。文章从第二章开始,主要讲解差分隐私的定义和典型架构, 典型的噪音添加方法,中心化差分隐私和本地化差分隐私的区别,以及合成定理。接下来, 文章在第三章主要讲解本地化差分隐私的方法和在工业界的应用。其中重点讲解Google的RAPPOR 差分隐私系统 和苹果的差分隐私系统。
2 差分隐私背景介绍
差分隐私的概念最早由Cynthia Dwork 等人在2006 年提出。区别以往的ad-hoc 隐私保护方案(比如k-anonymity,l-diversity,t-closeness)，差分隐私的主要贡献就是提供了个人隐私泄露的数学的定义。差分隐私的主要目的就是提供最大化utility 的查 询结果的同时还保证个人隐私的泄露不超过预先设定的 ε。
差分隐私分为中心化差分隐私和本地化差分隐私。两种差分隐私都可以保障单一用户的 ε-差分要求,但应用的场景略有不同。
2.1 中心化和本地化差分隐私
图1: (中心化)差分隐私处理流程框架。数据收集者从用户那里收集数据, 供数据分析者使用。
中心化差分隐私. 概况来讲,差分隐私就是保证一个统计数据库的查询结果不会受到任 何单一用户的隐私数据的影响。因此,攻击者就无法推测任何单一用户的数据。通常模 型里面会考虑两个相邻的数据库(neighboring databases)D 和D′,其中只有一个用 户的数据不同(增加或者删减一个记录)。ε-差分隐私(ε-DP)的定义如下:
Definition 2.1. ε-Differefial Privacy (ε-DP) A randomized function Agives ε-differential privacy iff for any two neighboring databases D and D′and for any output O of A
这里的随机函数A 是运行在服务器上面的,本地用户不需要运行任何差分隐私算法。ε 可以看做是隐私预算,它用来量化一个用户隐私泄露的风险。ε 的值越大,隐私泄露的风 险就越大,反之,ε 越小,隐私泄露的风险就越小。在现实中,个人用户的隐私还会有随着查 询的次数增加的风险。这个问题就是所谓的组合定理。
一个典型的差分隐私的架构由三部分组成(见图 2 ) : (1)数据源,一般为拥有数据的个人用 户;(2)数据收集者,一般为大型组织或公司;和(3) 数据分析者,包含任何对数据有兴趣的 个体和组织。这样的差分隐私又称作中心化差分隐私。图2: 本地化差分隐私的处理流程框架。区别于中心化差分隐私需要可信的 数据收集者,本地化差分隐私不需要可信 的数据收集者。
本地化差分隐私. 与中心化差分隐私对应的就是本地化差分隐私。ε-本地化差分隐私(ε-LDP)的定义如下:
Definition 2.2. ε-Local Differefial Privacy (ε-LDP) A randomized function A gives ε-differential privacy iff for any two inputs x and x′and for any output y of A,
这里的随机函数A 是单独运行在每一个用户本地,中央数据库不需要运行任何差分隐 私算法。本地化差分隐私没有数据库D 和相邻数据库D′的概念。因此需要特定的噪 音算法来应对 ε-LDP 的要求(算法见2.2 章节)。
2.2 典型算法
概况来讲,差分隐私的主要方法就是扰动(perturbation)和采样(sampling)。对于扰动方 案,就是对输入数据(input),中间数据(intermediate)或者输出数据(output) 进行扰 动,加入噪音(见图3),使其满足 ε-差分隐私。对于输入数据扰动的典型方案就是随机响 应(Randomized Response), 对于输出数据扰动的典型方案就是拉普拉斯算法(Laplace algorithm)。中间数据可以看做前面一个子阶段的输出,也可以看做是后面子 阶段的输入,因此可以灵活选择输入或者输出扰动的算法。图3: 扰动方法加入噪音的三种位置:1)输入数据(input),2)中间数据(intermediate),和3)输出数据(output)。
对于采样方法,典型的算法分为两步。假设查询函数为f。
1. 把数据分成k 份,对每份数据运行查询函数f,得到查询结果f(d1),f(d2),...,f(dk)。
2. 对查询结果应用任何一个满足 ε-差分隐私的算法(例如拉普拉斯算法 或随机响应), 得到最后结果。
这样做的好处就是最后 ε-差分隐私的算法运行在一个较小的数据集f (d1 ), f (d2 ), . . . , f (dk )上面,可以提高差分隐私的运行效率。详细资料可以参考文章。
2.2.1 拉普拉斯算法
拉普拉斯算法(Laplace algorithm)是最典型的中心化差分隐私算法。简单来说,拉普拉 斯算法(如图4) 就是在真实答案(比如f(D))的基础上加上符合拉普拉斯分布的噪音。噪 音 η 的取值公式为:其中GS_f 的是函数f 的GS(global sensitivity)。GS_f 取值为:对于拉普拉斯算法,他的mean 为0,variance 是2 ∗ (GS_f)2。variance 越小,说明 处理之后的数据集的utility 越高。但是,从variance 的公式我们可以得知variance 和 ε 成反比,也就是说 ε 和utility 成反比。因此,单纯的追求隐私保护或高utility 都 会损坏另外一方。在实际需求中,我们需要寻找一个平衡点。图4: 拉普拉斯噪音算法示意图。
拉普拉斯算法只能处理连续型数据。对于非连续型数据,比如性别、种族等,拉普拉斯会 输出无效的数据。对于这样的非连续型数据,我们需要借助于指数算法(Exponential algorithm)。这里就不详细描述了,可以阅读了解细节。
2.2.2随机响应算法
随机响应算法(Randomized Response)是最典型的本地化差分隐私算法。最早于1965年被Warner 提出,用于对隐私保护。随机响应技术主要包括两个步骤:扰动性统 计和校正。为帮助理解扰动性统计,我们考虑存在一枚非均匀的硬币,其正面向上的概率 为p,反面向上的概率为q,且p+q = 1。 规则是若正面向上则回答真实答案,反面向上 则回答相反的答案。利用上述扰动方法对n 个用户进行是否换艾滋病统计,在抛n 次硬币之后,可以得到艾滋病患者人数为m,没有得病的人为n −m。其中我们假设真实 的患病人数比例为r,我们可以得到扰动后的统计概率:上述统计比例并非真实比例的无偏估计,因此需要对统计结果进行校正。N 表示统计得 到的艾滋病人数估计值:根据总人数n,回答“是”的人数m 和扰动概率p,即可得到真实患病人数的统计值。 为保证其满足 ε- 本地化差分隐私,根据定义,隐私预算 ε 为:上面公式是适用于只有两种选择情况下的 ε-LDP。如果选择种类有d 种,这时候,我们 就需要扩展上面的随机响应算法,得到一个更普遍使用的随即响应算法,记为Generalized Randomized Response (GRR)。对于GRR 算法,同样需要两个步骤:扰动 性统计(π) 和校正(Γ)。针对用户的输入/采样数据为v 在数据集D,本地运行扰动统 计算法 πGRR(v),得到:算法运行得到y,并把结果发送给服务器。这里 πGRR(·) 满足 ε −LDP 。服务器端运 行 ΓGRR(v),得到:
其中I_v = |{j|v = y^j}|,也就是服务器上面获得的采样数,和前面例子中的m 相当。这 样获得的 ΓGRR() ̇ 是公正的,其variance 大小为:2.2.3符合差分隐私的k-anonymity
通常大家认为k-anonymity 算法是无法满足 ε-差分隐私需求的。这个认知在文章 里面被证明是正确的。有趣的是,对k-anonymity 算法进行一些改进,就可以使其符合 ε-差分隐私。具体操作步骤如下:
1. β-采样(β-sampling)。对数据集里面的每一个tuple 进行采样,使得每个tuple 都 有 β 大小的概率被选中。对采样后的数据,进行数据无关的泛化(data-independent generalization)。比如每k 个相邻年龄进行合并,使其满足k-anonymity。整个算法过程不考虑年龄分布,也就是 所谓的数据无关。因此会有些年龄段合并之后,可能无法满足k-anonymity 的要求。3. 对第二步产生的结果进。
2.行筛选,把不满足k-anonymity 要求的数据从最终结果中 剔除出去。这样,剩下的数据既满足k-anonymity 又满足 ε-差分隐私。 整个过程的证明过程可以参考文章。
2.3 中心化和本地化差分隐私比较
2.3.1可信与不可信的数据收集者
中心化差分隐私中一个重要的假设是可信第三方数据收集者。每个用户将自己的真实数 据记录发送给可信的数据收集者。数据收集者会主动保护收集的数据,并使用差分隐私 算法向数据分析者提供查询服务。本地化差分隐私中第三方数据收集者不需要可信。每 个用户按照差分隐私算法在本地对数据进行处理,然后把处理之后的数据上传给数据收 集者。收据收集者无法看到原始数据,因此不需要数据收集者可信。数据收集者接收查 询请求,并直接进行响应,无需在进行中心化的差分隐私。
2.3.2噪音机制
为保证算法满足 ε-差分隐私,中心化差分隐私和本地化差分隐私都需要噪声机制。中心 化差分隐私的典型噪音机制是:拉普拉斯噪音机制 和指数噪音机制。其中拉普拉斯噪音机制用来处理连续型数据,而指数噪音机制针对离散型数据。上述两种噪声机制均与查询函数的全局敏感性密切相关,而全局敏感性则是定义在D 和D’ 之上,使 得攻击者无法根据统计结果推测任何一个个体的数据。在本地化差分隐私中,每个用户将自己的数据进行扰动后上传,而任意两个用户之间并不知晓其他人的数据记录。也就是说这个时候的统计数据库D 就只有用户自己的记录。也就是说本地化差分隐私中不 存在全局敏感性的概念,因此拉普拉斯噪音机制和指数噪音机制对本地化差分隐私并不 适用。本地化差分隐私主要采用随机响应技术 来保护隐私。
2.4 合成定理
当我们了解了基础操作的隐私情况,差分隐私的合成定理(Composition Theorem) 可以帮助我们理解和计算一个复杂的算法的隐私。查询次数的上限(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长的数组 = {0, 1, . . . , k−1}.。整合所有输入,得到一个k 长 的数组B。
2/永久性随机响应(Permanent Randomized Response,or PRR)。对生成的数组B 的 每一个bit i (0 ≤i < k),进行随机翻转,生成新的数组Bi′。翻转概率公式如下所示:这里值得注意的是,以后任何需要使用B 的时候,都需要使用相同的Bi′,否则可能会 有”averaging” 攻击。这一步之后,用户的数据就已经获得 ε-差分隐私保护了。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. 的 分析,里面有两套典型的参数,可以命名为RAPPOR-1 和RAPPOR-2。两个系统的 ε 取值不同:RAPPOR-1 里面 ε= 4.39,而RAPPOR-2 里面 ε= 7.78。实际应用当中, 本地化差分隐私 ε 的取值应该避免大于4。当 ε> 4 的时候,用户的隐私会被很大概 率恢复出来。
3.2 苹果差分隐私系统
2016 年6 月,苹果宣布使用本地化差分隐私方法收集用户数据, 从而保证用户 信息的隐私性。我们在苹果最近的系统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 。本篇文章 通过逆向分析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),所使用的 ε 对用户隐私的保护还不尽如人意(尤其是苹果的差分隐私)。希望以后有更多的学者和企业加入到差分隐私的研究和应用当中,全 面提高差分隐私的保护效果和算法效率。
参考文献 Apple. Engineering privacy for your users. https://developer. apple.com/videos/play/wwdc2016/709/. Apple. Wwdc 2016 keynote. https://www.apple.com/apple-events/ june-2016/. 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 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. Ninghui Li, Wahbeh H. Qardaji, and Dong Su. Provably private data anonymization: Or, k-anonymity meets di erential privacy. abs/1101.2604, 01 2011. Sun Mingshen and Wei Tao. 大数据时代下的隐私保护. August 2017. 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
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. 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. 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. ú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. 来源：百度开发者中心
页:
[1]