大数据时代下的隐私保护(二）

 本文介绍了学术界和工业界对于用户隐私保护的努力成果，其中主要讲到了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 属性，那么通过李雷的信息查询出来的结果 中，工资的分布就和整体的分布类似，进而很难推断出李雷工资的高低。

 

160

最后，如果保证了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 是可以互换的，所以更加严格的讲，他们的比值也要大于 。

无论查询是什么，两个相邻的数据库返回的结果总是近似的。 要达到数据的差分隐私有四种方法:
1. 输出结果变换
2. 输入查询变换

3. 中间值变换
   4. 抽样和聚合数据

本文接下来主要介绍输出结果变换的方法，这种方法主要针对查询结果是数值或者数值 向量的情况，通过加入噪声使输出结果达到 ε-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)的方法 保护用户的原始数据不被泄露，随机应答的流程如下:

1. 当用户需要上报个人数据的时候，首先“抛硬币”决定是否上报真实数据。如果 是正面，则上报真实数据。如果不是，就上报一个随机的数据，再“抛一次硬币”决定 随机数据的内容。
   2. 服务器收到所有的数据后，因为知道“抛硬币”是正面的概率，服务器就能够判 断返回的数据是正确的概率。

这种“随机应答”的方法在理论上也被证明是服从 ε-差分隐私的。对于用户来说，隐 私数据在上报给服务器之前就已经加了噪声，从而具有一定保证。对于公司来说，也能 收集到有效的数据。

RAPPOR 使用“随机应答”的方法克服了之前只能回答简单查询语句的限制，现在可

以上报包含字符串这类更加复杂的回答。RAPPOR 在上报字符串信息的时候首先使用 “布隆过滤器”(bloom filter)算法把字符串哈希到一个数组中，然后再加入噪声传 给服务器。布隆过滤器不需要存储元素本身，并可以用于检索一个元素是否在一个集合 中。通过使用这种方法，就可以对字符串数据添加噪音，保护用户的隐私。

苹果在2016 年的世界开发者大会(WWDC)上也宣布使用差分隐私的方法收集用户 数据。虽然苹果没有透露具体的细节，我们从官方的描述中也可以推测出苹果也使用了 在客户端上做匿名化再传输到服务器的方法。

Differentialprivacy is a research topic in the areas of statistics and data analytics thatuses hashing, subsampling and noiseinjection to 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/designdocuments/rappor
• -  http://static.googleusercontent.com/media/research.google.com/en/us/p ubs/archive/42852.pdf

- Provably Private Data Anonymization: Or,k-Anonymity Meets Differential Privacy