前言 

本文介绍了学术界和工业界对于用户隐私保护的努力成果，其中主要讲到了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的方法很难达到。

•         偏斜性攻击