欢迎来到 黑吧安全网 聚焦网络安全前沿资讯,精华内容,交流技术心得!

差分隐私保护:从入门到脱坑

来源:本站整理 作者:佚名 时间:2018-09-10 TAG: 我要投稿

差分隐私(Differential Privacy)是密码学中的一种手段,旨在提供一种当从统计数据库查询时,最大化数据查询的准确性,同时最大限度减少识别其记录的机会。简单地说,就是在保留统计学特征的前提下去除个体特征以保护用户隐私。
0×00 背景
随着数据挖掘技术的普遍应用,一些厂商通过发布用户数据集的方式鼓励研究人员进一步深入挖掘数据的内在价值,在数据集发布的过程中,就存在安全隐患,可能导致用户隐私的泄露。2016年欧盟通过《一般数据法案》(General Data Protection Regulation, GDPR),规定了个人数据保护跨越国界,明确了用户对个人数据的知情权和被遗忘权。数据集中通常包含着许多个人的隐私数据,例如医疗诊断记录、个人消费习惯和使用偏好等,这些信息会由于数据集的发布而泄露。尽管删除数据的身份标识符(例如姓名、ID号等)能够在一定程度上保护个人隐私,但是以下案例表明,这种操作并不能保证隐私信息的安全性。
2006年10月,Netflix提出一笔100万美元的奖金,作为将其推荐系统改进达10%的奖励。Netflix还发布了一个训练数据集供竞选开发者训练其系统。在发布此数据集时,Netflix提供了免责声明:为保护客户的隐私,可识别单个客户的所有个人信息已被删除,并且所有客户ID已用随机分配的ID[sic]替代。由于Netflix不是网络上唯一的电影评级门户网站,其他网站还有很多,包括IMDb。个人可以在IMDb上注册和评价电影,并且可以选择匿名化自己的详情。德克萨斯州大学奥斯汀分校的研究员Arvind Narayanan和Vitaly Shmatikov将Netflix匿名化的训练数据库与IMDb数据库(根据用户评价日期)相连,能够部分反匿名化Netflix的训练数据库,危及到部分用户的身份信息。[1]
此外,卡内基梅隆大学的Latanya Sweeney的将匿名化的GIC数据库(包含每位患者的出生日期、性别和邮政编码)与选民登记记录相连后,可以找出马萨诸塞州州长的病历。[2]
差分隐私是Dwork在2006年针对统计数据库的隐私泄露问题提出的一种新的隐私定义。在此定义下,对数据库的计算处理结果对于具体某个记录的变化是不敏感的,单个记录在数据集中或者不在数据集中,对计算结果的影响微乎其微。所以,一个记录因其加入到数据集中所产生的隐私泄露风险被控制在极小的、可接受的范围内,攻击者无法通过观察计算结果而获取准确的个体信息。[3,4]
目前,一些企业已经开展了相关的工程实践。Google利用本地化差分隐私保护技术从Chrome浏览器每天采集超过1400万用户行为统计数据。[5]在2016年WWDC主题演讲中,苹果工程副总裁Craig Federighi宣布苹果使用本地化差分隐私技术来保护iOS/MacOS用户隐私。根据其官网披露的消息,苹果将该技术应用于Emoji、QuickType输入建议、查找提示等领域。例如,Count Mean Sketch算法(CMS)帮助苹果获得最受欢迎的Emoji表情用来进一步提升Emoji使用的用户体验,图1展示了利用该技术获得的US English使用者的表情使用倾向。图2展示了该技术的具体流程。

图1

图2
0×01 形式化定义
基本定义
对于一个有限域Z,z∈Z为Z中的元素,从Z中抽样所得z的集合组成数据集D,其样本量为n, 属性的个数为维度d。
对数据集D的各种映射函数被定义为查询(Query),用F={f1, f2, ······}来表示一组查询,算法M对查询F的结果进行处理,使之满足隐私保护的条件,此过程成为隐私保护机制。
设数据集D与D’,具有相同的属性结构,两者的对称差记作DΔD’,|DΔD’|表示DΔD’中记录的数量。若|DΔD’|=1,则称D和D’为邻近数据集。
差分隐私
设有随机算法M,PM为M所有可能的输出构成的集合。对于任意两个邻近数据集D和D’以及PM的任何子集SM,若算法M满足:Pr[M(D)∈SM],则称算法M提供ε-差分隐私保护,其中参数ε称为隐私保护预算。
其中,Pr[]表示发生某一事件的概率。如图1所示,算法M通过对输出结果的随机化来提供隐私保护,同时通过参数ε来保证在数据集中删除任一记录时,算法输出统一结果的概率不发生显著变化。

图3
相关概念
隐私保护预算
从差分隐私保护的定义可知,隐私保护预算ε用于控制算法M在邻近数据集上获得相同输出的概率比值,反映了算法M所的隐私保护水平,ε越小,隐私保护水平越高。在极端情况下,当ε取值为0时,即表示算法M针对D与D’的输出的概率分布完全相同,由于D与D’为邻近数据集,根据数学归纳法可以很显然地得出结论,即当ε=0时,算法M的输出结果不能反映任何关于数据集的有用的信息。因此,从另一方面,ε的取值同时也反映了数据的可用性,在相同情况下,ε越小,数据可用性越低。
敏感度
差分隐私保护可以通过在查询函数的返回值中加入噪声来实现,但是噪声的大小同样会影响数据的安全性和可用性。通常使用敏感性作为噪声量大小的参数,表示删除数据集中某一记录对查询结果造成的影响。在此,我们不再介绍敏感度的详细定义,感兴趣的读者可以参考相关文献。
实现机制
在实践中,通常使用拉普拉斯机制(Laplace Machanism)和指数机制(Exponential Mechanism)来实现差分隐私保护。其中,拉普拉斯机制用于数值型结果的保护,指数机制用于离散型结果的保护。
拉普拉斯机制
拉普拉斯机制通过向确切的查询结果中加入服从拉普拉斯分布的随机噪声来实现ε-差分隐私保护。记位置参数为0、尺度参数为b的拉普拉斯分布为Lap(b),那么其概率密度函数为:p(x)=exp(-|x|/b)/2b,

[1] [2]  下一页

【声明】:黑吧安全网(http://www.myhack58.com)登载此文出于传递更多信息之目的,并不代表本站赞同其观点和对其真实性负责,仅适于网络安全技术爱好者学习研究使用,学习中请遵循国家相关法律法规。如有问题请联系我们,联系邮箱admin@myhack58.com,我们会在最短的时间内进行处理。
  • 最新更新
    • 相关阅读
      • 本类热门
        • 最近下载