本文介绍了学术界和工业界对于用户隐私保护的努力成果，其中主要讲到了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 没有考虑敏感属性的语义，比如说下面的例子，我们通过李雷的信息从公开数据中关联到了两条信息，通过这两条信息我们能得出两个结论。第一，李雷的工资相对较低;第二，李雷喜欢买电子电器相关的产品。
