(公众号:)按:本文讲解了学术界和工业界对于用户隐私维护的希望成果,其中主要谈到了k-anonymity(k-电子邮件化),l-diversity(l-多样化),t-closeness 和 ε-differential privacy(差分隐私),并对它们的优缺点展开了分析。数据v.s.隐私在大数据的时代,数据沦为了科学研究的基石。
我们在享用着引荐算法、语音辨识、图像识别、无人车驾驶员等智能的技术带给的便捷的同时,数据在背后兼任着驱动算法大大优化递归的角色。在科学研究、产品开发、数据公开发表的过程中,算法必须搜集、用于用户数据,在这过程中数据就不可避免的曝露独自。历史上就有很多公开发表的数据曝露了用户隐私的案例。
美国在线(AOL)是一家美国互联网服务公司,也是美国仅次于的互联网提供商之一。在2006年8月,为了学术研究,AOL公开发表了电子邮件的搜寻记录,其中还包括65万个用户的数据,总共20M条查找记录。在这些数据中,用户的姓名被替换成了一个个电子邮件的ID,但是纽约时报通过这些搜寻纪录,寻找了ID 电子邮件为4417749的用户在真实世界中对应的人。ID 4417749的搜寻记录里有关于“60岁的老年人”的问题、“Lilburn地方的风景”、还有“Arnold”的搜寻字样。
通过上面几条数据,纽约时报找到Lilburn只有14个人姓氏Arnold,最后经过直接联系这14个人证实ID 4417749是一位62岁名字叫Thelma Arnold的老奶奶。最后AOL应急删除数据,发表声明道歉,但是早已太晚了。
因为隐私泄漏事件,AOL遭了控告,最后赔偿金不受影响用户总额低约五百万美元。某种程度是2006年,美国仅次于的影视公司之一Netflix,举行了一个预测算法的比赛(Netflix Prize),比赛拒绝在公开发表数据上推断用户的电影评分。
Netflix把数据中唯一辨识用户的信息抹去,指出这样就能确保用户的隐私。但是在2007年来自The University of Texas at Austin的两位研究人员回应通过关联Netflix公开发表的数据和IMDb(互联网电影数据库)网站上公开发表的纪录就需要辨识出有电子邮件后用户的身份。三年后,在2010年,Netflix最后因为隐私原因宣告暂停这项比赛,并因此受到高额罚款,赔偿金金额总计九百万美元。
近几年各大公司皆持续注目用户的隐私安全性。例如苹果在2016年6月份的WWDC大会上就明确提出了一项取名为Differential Privacy的差分隐私技术。
苹果声称他能通过数据计算出来出有用户群体的不道德模式,但是却无法取得每个用户个体的数据。那么差分隐私技术又是怎么做的呢?在大数据时代,如何才能确保我们的隐私呢?要问这个问题,我们首先要告诉什么是隐私。什么是隐私?我们常常谈论到隐私外泄、隐私维护,那么什么是隐私呢?荐个例子,居住于在海淀区五道口的小明常常在网上出售电子产品,那小明的姓名、出售偏爱和居住于地址算不算是隐私呢?如果某购物网站统计资料了用户的购物偏爱并公开发表部分数据,公开发表的数据中表明北京海淀区五道口的用户更加爱人卖电子产品,那么小明的隐私否被外泄了呢?要弄清楚隐私维护,我们再行要讨论一下到底什么是隐私。对于隐私这个词,科学研究上广泛拒绝接受的定义是“单个用户的某一些属性”,只要合乎这一定义都可以被看作是隐私。
我们在托“隐私”的时候,更为特别强调的是“单个用户”。那么,一群用户的某一些属性,可以指出不是隐私。我们拿刚才的例子来看,针对小明这个单个用户,“出售偏爱”和“居住于地址”就是隐私。如果公开发表的数据说道住在五道口的小明爱人卖电子产品,那么这似乎就是隐私外泄了。
但是如果数据中只包括一个区域的人的出售偏爱,就没泄漏用户隐私。如果更进一步谈,大家都告诉小明住在海淀区五道口,那么是不是小明就爱人买点此产品了呢?这种情况算不算事隐私外泄呢?答案是远比,因为大家只是通过这个趋势推断,数据并不表明小明一定爱人卖电子产品。
所以,从隐私维护的角度来说,隐私是针对单个用户的概念,公开发表群体用户的信息远比是隐私外泄,但是如果能从数据中能精确推断出有个体的信息,那么就算是隐私外泄。隐私维护的方法从信息时代开始,关于隐私维护的研究就开始了。随着数据大大地快速增长,人们对隐私更加推崇。
我们在辩论隐私维护的时候还包括两种情况。第一种是公司为了学术研究和数据交流对外开放用户数据,学术机构或者个人可以向数据库发动查找催促,公司回到对应的数据时必须确保用户的隐私。第二种情况是公司作为服务提供商,为了提升服务质量,主动搜集用户的数据,这些在客户端上搜集的数据也必须确保隐私性。
学术界明确提出了多种维护隐私的方法和测量隐私否泄漏的工具,例如k-anonymity(k-电子邮件化)、l-diversity(l-多样化)、t-closeness、ε-differentialprivacy(差分隐私)、同态加密(homomorphic encryption)、零科学知识证明(zero-knowledge proof)等等。今天主要讲解k-anonymity(k-电子邮件化),l-diversity(l-多样化),t-closeness和ε-differential privacy(差分隐私)。这些方法再行从直观的角度去取决于一个公开发表数据的隐私性,再行到用于密码学、统计学等工具保证数据的隐私性。
下面我们一一理解这四种隐私维护的方法:k-anonymity(k-电子邮件化)k-anonymity是在1998年由Latanya Sweeney和Pierangela Samarati明确提出的一种数据电子邮件化方法。我们再行看一下下面的这个表格:我们把要表格中的公开发表属性分成以下三类:- Key attributes:一般是个体的唯一标明,比如说姓名、地址、电话等等,这些内容必须在公开发表数据的时候删去。
- Quasi-identifier:类似于邮编、年龄、生日、性别等不是唯一的,但是能协助研究人员关联涉及数据的标明。- Sensitive attributes:敏感数据,比如说出售偏爱、薪水等等,这些数据是研究人员最关心的,所以一般都必要公开发表。非常简单来说,k-anonymity的目的是确保公开发表的数据中包括的个人信息最少k-1条无法通过其他个人信息确认出来。
也就是公开发表数据中的给定quasi-identifier信息,完全相同的人组都必须经常出现最少k次。荐个例子,假设一个公开发表的数据展开了2-anonymity维护。
如果攻击者想要证实一个人(小明)的脆弱信息(出售偏爱),通过查找他的年龄、邮编和性别,攻击者不会找到数据里最少有两个人是有完全相同的年龄、邮编和性别。这样攻击者就没有办法区分这两条数据究竟哪个是小明了,从而也就确保了小明的隐私会被泄漏。下面这个表格就是2-anonymization过的信息:k-anonymity的方法主要有两种,一种是移除对应的数据佩,用星号(*)替换。
另外一种方法是用总结的方法使之无法区分,比如把年龄这个数字总结成一个年龄段。对于邮编这样的数据,如果移除所有邮编,研究人员不会丧失很多有意义的信息,所以可以自由选择移除最后一位数字。从这个表中,即使我们告诉小明是男性、24岁、邮编是100083,却依然无法告诉小明的出售偏爱。
而研究人员仍然可以根据这些数据统计资料出有一些有意义的结果,这样既顾及了个人的隐私,又能为研究获取有效地的数据。k-anonymity能确保以下三点:1.攻击者无法告诉某个人否在公开发表的数据中2.等价一个人,攻击者无法证实他否有某项脆弱属性3.攻击者无法证实某条数据对应的是哪个人(这条假设攻击者除了quasi-identifier信息之外对其他数据一无所知,荐个例子,如果所有用户的偏爱都是出售电子产品,那么k-anonymity也无法确保隐私没泄漏)反击方法并未排序给定反击(unsorted matching attack):当公开发表的数据记录和原始记录的顺序一样的时候,攻击者可以说出电子邮件简化的记录是归属于谁。例如如果攻击者告诉在数据中小明是位列小白前面,那么他就可以证实,小明的出售偏爱是电子产品,小白是家用电器。
解决问题方法也很非常简单,在公开发表数据之前再行被打乱原始数据的顺序就可以防止这类的反击。补足数据反击(complementary release attack):假如公开发表的数据有多种类型,如果它们的k-anonymity方法有所不同,那么攻击者可以通过关联多种数据推断用户信息。
除此之外,如果脆弱属性在同一类quasi-identifiers中缺少多样性,或者攻击者有其它的背景科学知识,k-anonymity也无法防止隐私泄漏。我们告诉李雷的信息,表中有两条对应的数据,但是他们的出售偏爱都是电子产品。
因为这个脆弱属性缺少多样性,所以尽管是2-anonimity电子邮件简化的数据,我们仍然需要取得李雷的脆弱信息。如果我们告诉小绿的信息,并且告诉她不讨厌出售护肤品,那么从表中,我们仍可以证实小绿的出售偏爱是厨具。l-diversity(l-多样化)通过上面的例子,我们引向了多样化的概念。
非常简单来说,在公开发表的数据中,对于那些quasi-identifier完全相同的数据中,脆弱属性必需具备多样性,这样才能确保用户的隐私无法通过背景科学知识等方法推断出来。l-diversity确保了完全相同类型数据中最少有l种内容有所不同的脆弱属性。例如在右图的例子中,有10条完全相同的类型的数据,其中8条的出售偏爱是电子产品,其他两条分别是图书和家用电器。那么在这个例子中,公开发表的数据就符合3-diversity的属性。
除了以上讲解的非常简单l-diversity的定义,还有其他版本的l-diversity,引进了其他统计资料方法。比如说:基于概率的l-diversity (probabilistic l-diversity):在一个类型中经常出现频率最低的值的概率不小于1/l。
基于墒的l-diversity (entropy l-diversity):在一个类型中敏感数据产于的墒最少是log(l)。迭代(c,l)-diversity (recursive (c, l)-diversity):非常简单来说就是确保最经常出现的值的经常出现频率不要太高。
l-diversity也有其局限性:脆弱属性的性质要求即使确保了一定概率的diversity也很更容易泄漏隐私。例如,医院公开发表的艾滋病数据中,脆弱属性是“艾滋病阳性”(经常出现概率是1%)和“艾滋病阴性”(经常出现概率是99%),这两种值的敏感性有所不同,导致的结果也有所不同。有些情况下l-diversity是没意义的:比如说艾滋病数据的例子中仅有所含两种有所不同的值,确保2-diversity也是没意义的。
l-diversity很难达成协议:例如,我们想要在10000条数据中确保2-diversity,那么有可能最多必须10000* 0.01 = 100个完全相同的类型。这时有可能通过之前讲解的k-anonymity的方法很难超过。斜向性反击(Skewness Attack):假如我们要确保在同一类型的数据中经常出现“艾滋病阳性”和经常出现“艾滋病阴性”的概率是完全相同的,我们虽然确保了diversity,但是我们泄漏隐私的可能性不会变小。
因为l-diversity并没考虑到脆弱属性的总体的产于。l-diversity没考虑到脆弱属性的语义,比如说下面的例子,我们通过李雷的信息从公开发表数据中关联到了两条信息,通过这两条信息我们能得出结论两个结论。第一,李雷的工资比较较低;第二,李雷讨厌卖电子电器涉及的产品。t-closeness上面最后一个问题就引向了t-closeness的概念,t-closeness是为了确保在完全相同的quasi-identifier类型组中,脆弱信息的产于情况与整个数据的脆弱信息产于情况相似(close),不多达阈值t。
如果刚才的那个数据确保了t-closeness属性,那么通过李雷的信息查找出来的结果中,工资的产于就和整体的产于类似于,进而很难推断出李雷工资的强弱。最后,如果确保了k-anonymity,l-diversity和t-closeness,隐私就会泄漏了么?答案并不是这样,我们看下面的例子:在这个例子中,我们确保了2- anonymity , 2-diversity , t-closeness(产于近似于),工资和出售偏爱是脆弱属性。攻击者通过李雷的个人信息寻找了四条数据,同时告诉李雷有很多书,这样就能很更容易在四条数据中寻找李雷的那一条,从而导致隐私泄漏。有可能有些读者不会有疑惑,通过背景科学知识反击k-anonymity 的前提是不是假设理解quasi-identifier?并不是这样,针对脆弱属性的背景反击对k-anonymity 也限于,所以无论经过哪些属性确保,隐私泄漏还是很难防止。
差分隐私(differential privacy)除了之前我们讲解的针对k-anonymity, l-diversity,t-closeness三种隐私维护方法的反击之外,还有一种叫作差分反击( differential attack )。荐个例子,购物公司公布了购物偏爱的数据,说道我们有100个人的购物偏爱数据,其中有10个人喜好出售汽车用品,其他90个喜好出售电子产品。如果攻击者告诉其中99个人是喜好汽车用品还是电子产品,就可以告诉第100个人的购物偏爱。这样通过较为公开发表数据和既有的科学知识推断出有个人隐私,就叫作差分反击。
在2009年,微软公司研究院的Cynthia Dwork明确提出差分隐私的概念,差分隐私就是为了避免差分反击,也就是说尽管攻击者告诉公布的100个人的个人以信息和其中99个人的信息,他也没有办法通过核对这两个信息取得第100个人的信息。非常简单来说,差分隐私就是用一种方法使得查找100个信息和查找其中99个的信息获得的结果是比较完全一致的,那么攻击者就无法通过较为(差分)数据的有所不同找到第100个人的信息。这种方法就是重新加入随机性,如果查找100个记录和99个记录,输入某种程度的值的概率是一样的,攻击者就无法展开差分反击。
更进一步说道,对于差异只有一条记录的两个数据集D和D (neighboring datasets),查找他们取得结果完全相同的概率十分相似。留意,这里并无法确保概率完全相同,如果一样的话,数据就必须几乎的随机化,那样公开发表数据也就没意义。
所以,我们必须尽量相似,确保在隐私和可用性之间寻找一个均衡。ε-差分隐私(ε-differential privacy,ε-DP)可以用下面的定义来回应:其中M是在D上做到给定查找操作者,对查找后的结果重新加入一定的随机性,也就是给数据特噪音,两个datasets再加同一随机噪音之后查找结果为C的概率比大于一个特定的数。这样就能确保用户隐私泄漏的概率有一个数学的上界,比起传统的k-anonymity,差分隐私使隐私维护的模型更为明晰。
我们用一个例子说明差分隐私的定义:上图中D1和D2是两个neighboring datasets,他们只有一条记录不完全一致,在攻击者查找“20-30岁之间有多少人偏爱出售电子产品”的时候,对于这两个数据库获得的查找结果是100的概率分别是99%和98%,他们的比值大于某个数。如果对于给定的查找,都能符合这样的条件,我们就可以说道这种随机方法是符合ε-差分隐私的。
因为D1和D2是可以交换的,所以更为严苛的讲,他们的比值也要小于。无论查找是什么,两个邻接的数据库回到的结果总是近似于的。要超过数据的差分隐私有四种方法:输入结果转换输出查找转换中间值转换取样和单体数据本文接下来主要讲解输入结果转换的方法,这种方法主要针对查找结果是数值或者数值向量的情况,通过重新加入噪声使输入结果超过ε-DP。
输入结果转换:重新加入噪声在差分隐私中,避免隐私泄漏的最重要因素是在查找结果中加噪音,对于数值的查找结果,一种少见的方法就是对结果展开数值转换。要说明如何重新加入噪音,我们再行看一下下面的这个例子:假如某公司公开发表了数据,并且对外获取了查找数据的模块f(x),针对有所不同的查找x,服务器都会输入一个查找结果f(x) +噪声,重新加入噪声就是为了确保ε-差分隐私。那么如何自由选择噪声呢?差分隐私方法中,作者精妙的利用了拉普拉斯产于的特性,寻找了适合的噪声方法。
针对数值或向量的查找输入,M(x) = f(x) +噪声。我们能得出结论以下结论:其中Lap是拉普拉斯产于,GS回应global sensitivity:详尽的证明可以参照差分隐私的涉及文章。我们有了这个结论,想对某个查找模块f(x)确保ε-DP的话,只必须在查找结果上重新加入Lap(GS/e)的噪声就可以了。
拉普拉斯产于和其概率密度函数如下:(ε,δ)-differential privacy, (ε, δ)-DPε-DP是一种“严苛”的隐私维护确保,当在数据库中加到和移除一条数据时候,确保所有查找的输入都类似于。但是(ε, δ)-DP在ε-DP的确保中容许了一定概率的错误再次发生,比如说,用户在(ε, δ)-DP的维护持续性有δ概率的隐私泄漏。
基于这些的概念,差分隐私在机器学习算法中也需要用于,少见的算法,比如说PCA、logistic regression、SVM都有对应的差分隐私化算法。差分隐私在数据的实用性和隐私性之间超过了均衡,使用者可以通过原作自己的“隐私支出”(privacy budget)来调整数据的实用性和隐私性。但是差分隐私也不是万能的,其中重新加入噪声的很多算法必须在大量的数据集上才简单。除此之外,什么才是“隐私支出”的合理原作也是一个问题。
这些都是差分隐私面对的问题和挑战。并且由于差分隐私对于“背景科学知识”的拒绝过分强劲,所以必须在结果中重新加入大量随机化,造成数据的可用性(utility)急剧下降。但是差分隐私作为一个十分高雅的数学工具,是隐私维护的研究在未来的一个发展方向。
差分隐私用严苛的数学证明告诉他人们一个电子邮件简化的公开发表数据到底能维护用户多少的隐私。k-电子邮件简化与 ε-差分隐私的关系我们前面分别分开讲解了k-电子邮件简化和ε-差分隐私,k-电子邮件化比较较为更容易解读和实践中,差分隐私更加看起来从理论上证明了隐私维护的边界。虽然方法的分析角度几乎有所不同,但是它们之间却具有密切的联系。普渡大学的Ninghui Li教授在Provably PrivateData Anonymization: Or, k-Anonymity Meets Differential Privacy文章中详细分析了k-电子邮件简化和ε-差分隐私之间的关系。
文章证明了在用于k-电子邮件化“得宜”的情况下,可以符合一定条件的(ε, δ)-differentialprivacy。同时也明确提出了一种k-anonymity的变形:β-Sampling+ Data-independent _Generalization + k-Suppression (k, β)-SDGS,通过变形后的 k-anonymity 就可以使之符合差分隐私。
通过用于差分隐私这种工具,我们就能准确的取决于前人明确提出的 k-anonymity,在理论研究上具备最重要意义。实际案例在实际应用于中用于差分隐私时必须考虑到的问题还有很多,我们在讲解差分隐私的时候假设所有的查找操作者都由可靠的数据库处置,数据库里存储着用户的原始数据。
那么如果数据库被反击了,包括用户隐私的原始数据就泄漏了。如果不搜集用户的原始数据,在客户端上再行做到差分隐私,再行上传授给服务器,这个问题就解决问题了。最近Google首度用于RAPPOR系统在Chrome浏览器上通过这种方法搜集用户的用于情况数据。RAPPOR基于“随机接收者”(randomized response)的方法维护用户的原始数据不被泄漏,随机接收者的流程如下:当用户必须请示个人数据的时候,首先“抛硬币”要求否请示现实数据。
如果是正面,则请示现实数据。如果不是,就请示一个随机的数据,再行“抛一次硬币”要求随机数据的内容。
服务器接到所有的数据后,因为告诉“抛硬币”是正面的概率,服务器就需要辨别回到的数据是准确的概率。这种“随机接收者”的方法在理论上也被证明是遵从ε-差分隐私的。对于用户来说,隐私数据在请示给服务器之前就早已特了噪声,从而具备一定确保。
对于公司来说,也能搜集到有效地的数据。RAPPOR用于“随机接收者”的方法解决了之前不能问非常简单查找语句的容许,现在可以请示包括字符串这类更为简单的问。RAPPOR在请示字符串信息的时候首先用于“布隆过滤器”(bloom filter)算法把字符串哈希到一个数组中,然后再行重新加入噪声传授给服务器。
布隆过滤器不必须存储元素本身,并可以用作检索一个元素否在一个子集中。通过用于这种方法,就可以对字符串数据加到噪音,维护用户的隐私。苹果在2016年的世界开发者大会(WWDC)上也宣告用于差分隐私的方法搜集用户数据。
虽然苹果没透漏明确的细节,我们从官方的叙述中也可以推断出有苹果也用于了在客户端上做到电子邮件简化再行传输到服务器的方法。Differentialprivacy is a research topic in the areas of statistics and data analytics thatuseshashing, subsampling and noiseinjectionto enable...crowdsourced learning while keeping the data ofindividual users completely private. Apple has been doing some super-importantwork in this area to enable differential privacy to be deployed at scale.我们刚才讲解的Google和Apple的模型都是再行在本地做到差分隐私,然后再行请示给服务器,我们把这种方法叫作本地模式(local mode)。
这种差分隐私的作法在请示数据可以互相关联的情况下还是不存在隐私外泄。Google的RAPPOR虽然解决问题了对同一个数据的多次请示的隐私泄漏问题,但并没解决问题多个涉及数据请示后产生的隐私泄漏问题。对于这一问题,Apple也没得出详尽的说明。除了Google和苹果在内部产品中用于差分隐私方法,哈佛大学公开发表了一个取名为PSI (Ψ)的项目,获取了一个便利的差分隐私工具。
使用者通过上载数据,调整差分隐私的参数,就可以取得符合差分隐私的数据集。总结本文讲解了学术界和工业界对于用户隐私维护的希望成果。我们首先讲解了k-anonymity,即通过转换隐私数据,确保完全相同特性的用户在数据库经常出现的次数最少是k次。
然后,为了避免攻击者通过隐私数据的背景科学知识推断用户身份,明确提出用于l-diversity,确保完全相同特征的用户中,隐私数据完全相同的个数小于l。除此之外,我们也辩论了t-closeness。
最后我们详尽讲解了差分隐私的概念,以及实际应用于中不应如何用于差分隐私。从最开始的k-anonymity, l-diversity , t-closeness到现在的ε-差分隐私,都是为了既保证用户的个人隐私,也能对实际应用于和研究获取有价值的数据。在大数据的时代中,期望各公司在利用数据获取更佳的服务的同时,能维护好用户的个人隐私。
这是法律的拒绝,也是安全性行业的执着。我们坚信隐私维护技术不会更加受到重视,并从学术理论很快投放工业界空战应用于。参照文章-https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf-https://www.cs.cmu.edu/~yuxiangw/docs/Differential%20Privacy.pdf-https://blog.cryptographyengineering.com/2016/06/15/what-is-differential-privacy/-https://www.chromium.org/developers/design-documents/rappor-http://static.googleusercontent.com/media/research.google.com/en/us/pubs/archive/42852.pdf-Provably Private Data Anonymization: Or,k-Anonymity Meets Differential Privacy特约稿件,予以许可禁令刊登。
下文闻刊登须知。
本文来源:新葡萄最新官网-www.theninjaapproved.com