编者按

　　随着隐私成为大数据应用领域的焦点，百度安全实验室的安全专家孙茗珅和韦韬专门撰写了一个隐私保护技术方面的综述。本文介绍了学术界和工业界对于用户隐私保护的努力成果，其中主要讲到了k-anonymity（k-匿名化）、l-diversity（l-多样化）、t-closeness和ε-differential privacy（差分隐私），并对它们的优缺点进行了分析。

大数据时代下的隐私保护

数据和隐私

　　在大数据的时代，数据成为了科学研究的基石。人们在享受着推荐算法、语音识别、图像识别、无人车驾驶等智能的技术带来的便利的同时，数据在背后担任着驱动算法不断优化迭代的角色。在科学研究、产品开发、数据公开的过程中，算法需要收集、使用用户数据，在这过程中数据就不可避免地暴露在外。历史上就有很多公开的数据暴露了用户隐私的案例。

　　美国在线（AOL）是一家美国互联网服务公司，也是美国最大的互联网提供商之一。2006年8月，为了学术研究，AOL公开了匿名的搜索记录，其中包括65万个用户的数据，总共20M条查询记录。在这些数据中，用户的姓名被替换成了一个个匿名的ID，但是《纽约时报》通过这些搜索记录，找到了ID匿名为4417749的用户在真实世界中对应的人。ID4417749的搜索记录里有关于“60岁的老年人”的问题、

　　“Lilburn地方的风景”、还有“Arnold”的搜索字样。通过上面几条数据，纽约时报发现Lilburn只有14个人姓Arnold，最后经过直接联系这14个人确认ID4417749是一位62岁名字叫Thelma Arnold的老奶奶。最后AOL紧急撤下数据，发表声明致歉，但是已经太晚了。因为隐私泄露事件，AOL遭到了起诉，最终赔偿受影响用户总额高达五百万美元。

　　同样是2006年，美国最大的影视公司之一——Netflix，举办了一个预测算法的比赛（Netflix Prize），比赛要求在公开数据上推测用户的电影评分。Netflix把数据中唯一识别用户的信息抹去，认为这样就能保证用户的隐私。但是在2007年来自The University of Texasat Austin的两位研究人员表示通过关联Netflix公开的数据和IMDb（互联网电影数据库）网站上公开的记录就能够识别出匿名后用户的身份。三年后，在2010年，Netflix最后因为隐私原因宣布停止这项比赛，并因此受到高额罚款，赔偿金额总计九百万美元。近几年各大公司均持续关注用户的隐私安全。例如苹果在2016年6月份的WWDC大会上就提出了一项名为DifferentialPrivacy的差分隐私技术。苹果声称他能通过数据计算出用户群体的行为模式，但是却无法获得每个用户个体的数据。那么差分隐私技术又是怎么做的呢？在大数据时代，如何才能保证我们的隐私呢？

隐私保护的方法

　　从信息时代开始，关于隐私保护的研究就开始了。随着数据不断地增长，人们对隐私越来越重视。我们在讨论隐私保护的时候包括两种情况。

　　第一种是公司为了学术研究和数据交流开放用户数据，学术机构或者个人可以向数据库发起查询请求，公司返回对应的数据时需要保证用户的隐私。

　　第二种情况是公司作为服务提供商，为了提高服务质量，主动收集用户的数据，这些在客户端上收集的数据也需要保证隐私性。学术界提出了多种保护隐私的方法和测量隐私是否泄露的工具，例如k-anonymity（k-匿名化）、l-diversity（l-多样化）、t-closeness、ε-differential privacy（差分隐私）、同态加密（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提出的一种数据匿名化方法。

　　先看一下表1，我们把表格中的公开属性分为以下三类：

　　Key attributes：一般是个体的唯一标示，比如说姓名、地址、电话等等，这些内容需要在公开数据的时候删掉。

　　Quasi-identifier：类似邮编、年龄、生日、性别等不是唯一的，但是能帮助研究人员关联相关数据的标示。

　　Sensitive attributes：敏感数据，比如说购买偏好、薪水等等，这些数据是研究人员最关心的，所以一般都直接公开。

　　简单来说，k-anonymity的目的是保证公开的数据中包含的个人信息至少k-1条不能通过其他个人信息确定出来。也就是公开数据中的任意quasi-identifier信息，相同的组合都需要出现至少k次。

　　举个例子，假设一个公开的数据进行了2-anonymity保护。如果攻击者想确认一个人（小明）的敏感信息（购买偏好），通过查询他的年龄、邮编和性别，攻击者会发现数据里至少有两个人是有相同的年龄、邮编和性别。这样攻击者就没办法区分这两条数据到底哪个是小明了，从而也就保证了小明的隐私不会被泄露。

　　表2就是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也无法避免隐私泄露。

　　我们知道李雷的信息，图1中有两条对应的数据，但是他们的购买偏好都是电子产品。因为这个敏感属性缺乏多样性，所以尽管是2-anonimity匿名化的数据，我们依然能够获得李雷的敏感信息。

　　如果我们知道小紫的信息，并且知道她不喜欢购买护肤品，那么从图2中，我们仍可以确认小紫的购买偏好是厨具。

　　l-diversity（l-多样化）

　　通过上面的例子，我们引出了多样化的概念。简单来说，在公开的数据中，对于那些quasi-identifier相同的数据中，敏感属性必须具有多样性，这样才能保证用户的隐私不能通过背景知识等方法推测出来。

　　l-diversity保证了相同类型数据中至少有l种内容不同的敏感属性。

　　例如在图3的例子中，有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没有考虑敏感属性的语义，比

　　如说下面图4的例子，我们通过李雷的信息从公开数据中关联到了两条信息，通过这两条信息我们能得出两个结论。第一，李雷的工资相对较低；第二，李雷喜欢买电子电器相关的产品。

 

　　t-closeness

 

　　上面最后一个问题就引出了t-closeness的概念，t-closeness是为了保证在相同的quasi-identifier类型组中，敏感信息的分布情况与整个数据的敏感信息分布情况接近（close），不超过阈值t。

　　如果刚才的那个数据保证了t-closeness属性，那么通过李雷的信息查询出来的结果中，工资的分布就和整体的分布类似，进而很难推断出李雷工资的高低。

　　最后，如果保证了k-anonymity，l-diversity和t-closeness，隐私就不会泄露了么？答案并不是这样，我们看图5的例子，在这个例子中，我们保证了2-anonymity，2-diversity，t-closeness（分布近似），工资和购买偏好是敏感属性。攻击者通过李雷的个人信息找到了四条数据，同时知道李雷有很多书，这样就能很容易在四条数据中找到李雷的那一条，从而造成隐私泄露。可能有些读者会有疑问，通过背景知识攻击k-anonymity的前提是不是假设了解quasi-identifier？并不是这样，针对敏感属性的背景攻击对k-anonymity也适用，所以无论经过哪些属性保证，隐私泄露还是很难避免。

　　差分隐私（differentialprivacy）

　　除了之前我们介绍的针对k-anonymity，l-diversity，t-closeness三种隐私保护方法的攻击之外，还有一种叫做差分攻击（differential attack）。举个例子，购物公司发布了购物偏好的数据，说我们有100个人的购物偏好数据，其中有10个人偏爱购买汽车用品，其他90个偏爱购买电子产品。如果攻击者知道其中99个人是偏爱汽车用品还是电子产品，就可以知道第100个人的购物偏好。这样通过比较公开数据和既有的知识推测出个人隐私，就叫做差分攻击。

　　在2009年，微软研究院的CynthiaDwork提出差分隐私的概念，差分隐私就是为了防止差分攻击，也就是说尽管攻击者知道发布的100个人的个人以信息和其中99个人的信息，他也没办法通过比对这两个信息获得第100个人的信息。

　　简单来说，差分隐私就是用一种方法使得查询100个信息和查询其中99个的信息得到的结果是相对一致的，那么攻击者就无法通过比较（差分）数据的不同找出第100个人的信息。这种方法就是加入随机性，如果查询100个记录和99个记录，输出同样的值的概率是一样的，攻击者就无法进行差分攻击。进一步说，对于差别只有一条记录的两个数据集D和D‘（neighboring datasets），查询他们获得结果相同的概率非常接近。注意，这里并不能保证概率相同，如果一样的话，数据就需要完全的随机化，那样公开数据也就没有意义。所以，我们需要尽可能接近，保证在隐私和可用性之间找到一个平衡。

　　ε-差分隐私（ε-differential privacy，ε-DP）可以用下面图6的定义来表示：

　　其中M是在D上做任意查询操作，对查询后的结果加入一定的随机性，也就是给数据加噪音，两个datasets加上同一随机噪音之后查询结果为C的概率比小于一个特定的数。这样就能保证用户隐私泄露的概率有一个数学的上界，相比传统的k-anonymity，差分隐私使隐私保护的模型更加清晰。

　　我们用图7的例子解释差分隐私的定义：图7中D1和D2是两个neighboring datasets，他们只有一条记录不一致，在攻击者查询“20-30岁之间有多少人偏好购买电子产品”的时候，对于这两个数据库得到的查询结果是100的概率分别是99%和98%，他们的比值小于某个数。如果对于任意的查询，都能满足这样的条件，我们就可以说这种随机方法是满足ε-差分隐私的。因为D1和D2是可以互换的，所以更加严格地讲，他们的比值也要大于e-ε。

　　无论查询是什么，两个相邻的数据库返回的结果总是近似的。

　　要达到数据的差分隐私有四种方法：

　　1.输出结果变换

　　2.输入查询变换

　　3.中间值变换

　　4.抽样和聚合数据

　　本文接下来主要介绍输出结果变换的方法，这种方法主要针对查询结果是数值或者数值向量的情况，通过加入噪声使输出结果达到ε-DP。

　　输出结果变换：加入噪声

　　在差分隐私中，防止隐私泄露的重要因素是在查询结果中加噪音，对于数值的查询结果，一种常见的方法就是对结果进行数值变换。要解释如何加入噪音，我们先看一下图8的这个例子：假如某公司公开了数据，并且对外提供了查询数据的接口f（x），针对不同的查询x，服务器都会输出一个查询结果f（x）+噪声，加入噪声就是为了保证ε-差分隐私。

 

　　那么如何选择噪声呢？

 

　　差分隐私方法中，作者巧妙地利用了拉普拉斯分布的特性，找到了合适的噪声方法。针对数值或向量的查询输出，M（x）=f（x）+噪声。我们能得出以下结论：

　　我们有了这个结论，想要对某个查询接口f（x）保证ε-DP的话，只需要在查询结果上加入Lap（GS/e）的噪声就可以了。

　　拉普拉斯分布和其概率密度函数如图9：

　　（ε，δ）-differential privacy，（ε，δ）-DPε-DP是一种“严格”的隐私保护保证，当在数据库中添加和删除一条数据时候，保证所有查询的输出都类似。但是（ε，δ）-DP在ε-DP的保证中允许了一定概率的错误发生，比如说，用户在（ε，δ）-DP的保护下会有δ概率的隐私泄露。

　　基于这些的概念，差分隐私在机器学习算法中也能够使用，常见的算法，比如说PCA、logisticregression、SVM都有对应的差分隐私化算法。

　　差分隐私在数据的实用性和隐私性之间达到了平衡，使用者可以通过设定自己的“隐私预算”（privacy budget）来调整数据的实用性和隐私性。但是差分隐私也不是万能的，其中加入噪声的很多算法需要在大量的数据集上才实用。除此之外，什么才是“隐私预算”的合理设定也是一个问题。这些都是差分隐私面临的问题和挑战。并且由于差分隐私对于“背景知识”的要求过于强，所以需要在结果中加入大量随机化，导致数据的可用性（utility）急剧下降。但是差分隐私作为一个非常优雅的数学工具，是隐私保护的研究在未来的一个发展方向。差分隐私用严格的数学证明告诉人们一个匿名化的公开数据究竟能保护用户多少的隐私。

　　k-匿名化与ε-差分隐私的关系

　　我们前面分别单独介绍了k-匿名化和ε-差分隐私，k-匿名化相对比较容易理解和实践，差分隐私更像是从理论上证明了隐私保护的边界。虽然方法的分析角度完全不同，但是它们之间却有着紧密的联系。普渡大学的NinghuiLi教授在Provably Private Data Anonymization：Or，k-Anonymity Meets Differential Privacy文章中详细分析了k-匿名化和ε-差分隐私之间的关系。文章证明了在使用k-匿名化“得当”的情况下，可以满足一定条件的（ε，δ）-differentialprivacy。同时也提出了一种k-anonymity的变形：β-Sampling+Data-independent_Generalization+k-Suppression（k，β）-SDGS，通过变形后的k-anonymity就可以使之满足差分隐私。通过使用差分隐私这种工具，我们就能精确地衡量前人提出的k-anonymity，这在理论研究上具有重要意义。

　　总结

　　本文介绍了学术界和工业界对于用户隐私保护的努力成果。首先介绍了k-anonymity，即通过变换隐私数据，保证相同特性的用户在数据库出现的次数至少是k次。然后，为了防止攻击者通过隐私数据的背景知识推测用户身份，提出使用l-diversity，保证相同特征的用户中，隐私数据相同的个数大于l。除此之外，我们也讨论了t-closeness。最后详细介绍了差分隐私的概念，以及实际应用中应如何使用差分隐私。

　　从最开始的k-anonymity，l-diversity，t-closeness到现在的ε-差分隐私，都是为了既保证用户的个人隐私，也能对实际应用和研究提供有价值的数据。在大数据的时代中，希望各公司在利用数据提供更好的服务的同时，能保护好用户的个人隐私。这是法律的要求，也是安全行业的追求。我们相信隐私保护技术会越来越受到重视，并从学术理论迅速投入工业界实战应用（责编：杨洁）

　　（作者单位为百度安全实验室）

　　参考文章

　　1.https：//www.cis.upenn.edu/～aaroth/Papers/privacybook.

　　pdf

　　2..https：//www.cs.cmu.edu/～yuxiangw/docs/Differential%20Privacy.pdf

　　3.https：//blog.cryptographyengineering.com/2016/06/15/what-is-differential-privacy/

　　4.https：//www.chromium.org/developers/design-documents/rappor

　　5.http：//static.googleusercontent.com/media/research.google.com/en/us/pubs/archive/42852.pdf

　　6.ProvablyPrivateDataAnonymization：Or，k-AnonymityMeetsDifferentialPrivacy