0. 隐私数据泄露类型
隐私数据泄露可以分为多种类型,根据不同的类型,通常可以采用不同的隐私数据泄露风险模型来衡量防止隐私数据泄露的风险,以及对应不同的数据脱敏算法对数据进行脱敏.
一般来说,隐私数据泄露类型包括:
- 个人标识泄露.当数据使用人员通过任何方式确认数据表中某条数据属于某个人时,称为个人标识泄露.个人标识泄露最为严重,因为一旦发生个人标识泄露,数据使用人员就可以得到具体个人的敏感信息.
- 属性泄露.当数据使用人员根据其访问的数据表了解到某个人新的属性信息时,称为属性泄露.个人标识泄露肯定会导致属性泄露,但属性泄露也有可能单独发生.
- 成员关系泄露.当数据使用人员可以确认某个人的数据存在于数据表中时,称为成员关系泄露.成员关系泄露相对风险较小,个人标识泄露与属性泄露肯定意味着成员关系泄露,但成员关系泄露也有可能单独发生.
1. 传统隐私保护方法
保护隐私的方法包括k-anonymity(k-匿名化),l-diversity(l-多样化),t-closeness, ε-differentialprivacy(差分隐私),同态加密(homomorphic encryption),零知识证明(zero-knowledge proof)等等.
1.1 k-匿名化
1.1.1 什么是k-匿名化
表格中的公开属性分为以下三类:
- Key attributes:一般是个体的唯一标示,比如说姓名,地址,电话等等,这些内容需要在公开数据的时候删掉.
- Quasi-identifier:类似邮编,年龄,生日,性别等不是唯一的,但是能帮助研究人员关联相关数据的标示.
- Sensitive attributes:敏感数据,比如说购买偏好,薪水等等,这些数据是研究人员最关心的,所以一般都直接公开.
k-anonymity的目的是保证公开的数据中包含的个人信息至少 k-1 条不能通过其他个人信息确定出来.也就是公开数据中的任意 quasi-identifier信息,相同的组合都需要出现至少 k 次.
举个例子,假设一个公开的数据进行了 2-anonymity 保护.如果攻击者想确认一个人(小明)的敏感信息(购买偏好),通过查询他的年龄,邮编和性别,攻击者会发现数据里至少有两个人是有相同的年龄,邮编和性别.这样攻击者就没办法区分这两条数据到底哪个是小明了,从而也就保证了小明的隐私不会被泄露.
1.1.2 k-匿名化具体做法
k-anonymity的方法主要有两种:
- 删除对应的数据列,用星号(*)代替.
- 用概括的方法使之无法区分,比如把年龄这个数字概括成一个年龄段.对于邮编这样的数据,如果删除所有邮编,研究人员会失去很多有意义的信息,所以可以选择删除最后一位数字.
从这个表中,即使我们知道小明是男性,24岁,邮编是100083,却仍然无法知道小明的购买偏好.而研究人员依然可以根据这些数据统计出一些有意义的结果,这样既兼顾了个人的隐私,又能为研究提供有效的数据.
1.1.3 该方案的攻击方法
- 未排序匹配攻击(unsorted matching attack):当公开的数据记录和原始记录的顺序一样的时候,攻击者可以猜出匿名化的记录是属于谁.例如如果攻击者知道在数据中小明是排在小白前面,那么他就可以确认,小明的购买偏好是电子产品,小白是家用电器.解决方法也很简单,在公开数据之前先打乱原始数据的顺序就可以避免这类的攻击.
- 补充数据攻击(complementary release attack):假如公开的数据有多种类型,如果它们的 k-anonymity 方法不同,那么攻击者可以通过关联多种数据推测用户信息.如A数据里返回7条记录,其中有个购物偏好的属性,攻击者从其它数据源知道了小明还喜欢护肤品,正好这7条记录里只有一条购物偏好是护肤品,那么攻击者就能识别出小明了.
- 数据源问题:如某个查询返回了7条记录,但是这7条记录的敏感信息(购物偏好)都是电子产品,那么攻击者不用知道具体是谁,也能知道他们目标对象的购物偏好了.
1.2 l-多样化
1.2.1 什么是l-多样化
基于上面的数据源问题,这里引出了多样化的概念.简单来说,在公开的数据中,对于那些quasi-identifier 相同的数据中,敏感属性必须具有多样性,这样才能保证用户的隐私不能通过背景知识等方法推测出来.
更具体地说,任意一组能表示用户的查询,返回记录中至少包含l个不同的隐私记录.如检索”性别 年龄 城市”返回10条记录,隐私记录是购物偏好,这10条里包含3种不同的购物偏好,那么就说满足3-多样化
除了以上介绍的简单 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):简单来说就是保证最经常出现的值的出现频率不要太高.
1.2.2 存在的问题
- 概率差异较大的属性:如艾滋病阳性(1%)和艾滋病阴性(99%),要实现l-多样化较难.如果属性之间概率差异较大,那么实现l-多样化很难
- 偏斜性攻击:如果在艾滋病阴性阳性的例子中我们实现了2-多样化,但是返回结果中阳性的概率>>1%,攻击者有信息去认为目标用户是阳性的概率比较大
- 对返回结果汇总还是能得到信息:我们通过李雷的信息从公开数据中关联到了两条信息,通过这两条信息我们能得出两个结论.第一,李雷的工资相对较低;第二,李雷喜欢买电子电器相关的产品.
1.3 t-closeness(分布近似)
1.3.1 t-closeness的目标
上面最后一个问题就引出了 t-closeness 的概念,t-closeness 是为了保证在相同的quasi-identifier类型组中,敏感信息的分布情况与整个数据的敏感信息分布情况接近(close),不超过阈值 t.
如果上面的那个数据保证了 t-closeness 属性,那么通过李雷的信息查询出来的结果中,工资的分布就和整体的分布类似,进而很难推断出李雷工资的高低.如下图.
1.3.2 问题分析
最后,如果保证了 k-anonymity,l-diversity 和 t-closeness,隐私就不会泄露了么?答案并不是这样,可以继续参考上面的图.
在这个例子中,我们保证了 2- anonymity , 2-diversity , t-closeness(分布近似),工资和购买偏好是敏感属性.攻击者通过李雷的个人信息找到了四条数据,同时知道李雷有很多书,这样就能很容易在四条数据中找到李雷的那一条,从而造成隐私泄露.
这种情况属于针对敏感属性的背景攻击.
2. 差分隐私
2.1 差分攻击与差分隐私
攻击者想知道LZC的泛函成绩,于是进行了两步查询:
- 求1-8所有人(有LZC)的泛函成绩之和. SUM(1, 8).
- 求1-7所有人(无LZC)的泛函成绩之和. SUM(1, 7).
- 然后做差,就得到了LZC的泛函成绩. SUM(1, 8) - SUM(1, 7).
隐私泄露了,这种局面当然不是我们希望看到的,于是我们需要一些机制来抵御这种”差分攻击”.
差分攻击的核心做法就是找两个只差一条记录的数据集,分别做查询,再比较结果的差异,来获取两个集合所相差的记录的敏感信息. 所以我们最直接的想法也就是,通过随机化的查询(即管理员不能总说实话),使得攻击者无法区分只差一条记录的两个集合. 差分隐私就是为了防止差分攻击.
2.2 如何做到差分隐私
差分隐私核心思想:查询结果里加入随机性.
任何一种方法,只要用在数据集上能满足差分隐私的核心思想,那这个方法就是满足差分隐私的.所以最常用的方法是在结果上加满足某种分布的噪音,使查询结果随机化.
目前常用的有两种方法:
- Laplace机制.在查询结果里加入Laplace分布的噪音,适用于数值型输出.例如:zhihu里有多少人是985大学毕业的? 假如结果是2000人,那么每一次查询得到的结果都会稍稍有些区别,比如有很高的概率输出2001,也有较高概率输出2010, 较低概率输出1990,等等.
- 指数机制. 在查询结果里用指数分布来调整概率,适用于非数值型输出.例如:中国top 3大学是哪一所.很高概率输出 浙江大学,较高概率输出上海交大,较低概率输出武汉大学,很低概率输出蓝翔技校,等等.
2.3 差分隐私的弱点
差分隐私的弱点其实很明显:由于对于背景知识的假设过于强,需要在查询结果中加入大量的随机化,导致数据的可用性急剧下降.特别对于那些复杂的查询,有时候随机化结果几乎掩盖了真实结果.这也是导致目前应用不多的一个原因.
但差分隐私作为一个非常漂亮的数学工具,为隐私研究指明了一个发展的方向.在早期,人们很难证明我的方法保护了隐私,更无法证明究竟保护了多少隐私.现在差分隐私用严格的数学证明告诉人们,只要你按照我的做,我就保证你的隐私不会泄露.
