Chap.7 隐私保护技术

7.1 隐私 / 隐私保护

7.1.1 隐私的范围

个人隐私在定义中通常分以下两种:

• 已经识别出来的数据: 指可以用来确认某个自然人的数据
• 可以识别出来的数据: 指那些与自然人间接相关, 通过分析推理能够确定某个自然人的数据

通常会涉及到四个参与方:

• 个人用户
• 数据采集 / 发布者
• 数据使用者
• 攻击者

因此, 隐私保护主要针对以下三方面:

• 身份隐私: 降低从数据直接推断出特定用户的可能性
• 属性隐私: 对用户属性信息进行有针对性地处理
• 社交关系隐私: 节点对应的社交关系应当匿名处理

7.1.2 隐私保护技术

当前主要存在的隐私保护技术分以下两类:

• 基于等价类的隐私保护
  • 通过对数据进行泛化 / 抑制, 使得每条记录都与一定数量的记录不可区分.
• 基于差分隐私的隐私保护
  • 在查询结果中加入噪声, 使攻击者无法确认某个记录是否存在

常见的手段包括:

• 抑制: 数据置空
• 泛化: 降低数据精度
• 置换: 改变数据属主
• 扰动: 添加噪声
• 裁剪: 数据分散发布
• 密码学: 使用加密等手段

7.2 关系型数据隐私保护

7.2.1 链接攻击与身份匿名

最简单的方式是将数据库中能够唯一标识个人的信息去除(匿名化).
但这种方式意味着如果攻击者有背景知识(了解攻击目标的其他信息), 就仍然能够快速定位到某个具体的攻击目标.

7.2.2 k匿名

指的是对表内的某些属性进行 泛化 操作, 使得每一条经过泛化的查询记录在表内至少有k个对应表项.

泛化 指的是对数据的模糊化:

当你把表中的很多数据都泛化时, 就会发现符合条件的表项变多了, 那自然攻击者也无法精准的找到某一个具体的角色了.

这种方式能够做到:

• 攻击者无法知道个人是否在公开的数据中
• 给定一个人, 攻击者无法确认他是否有其它的敏感属性
• 攻击者无法确认某一个具体表项指的是哪个人

当然, 这种情况下本质上是将一个人的查询结果变成了一群人, 但攻击者还是可以通过一些手段得知这个人具体的信息的, 只不过难度会稍高一些.

• 同质化攻击: 某一组内对应的敏感信息完全相同, 这时候就无所谓哪个是哪个了:

• 未排序攻击: 即公开的数据记录跟原始记录一致, 那也可以很简单的猜出匿名化的记录的属主

• 补充数据攻击: 即表格的筛选项多种多样时, 可以通过不同的筛选策略一并对比得到一些条目

7.3 差分隐私

7.3.1 差分隐私的具体流程

显然, 上面的k匿名能起到一定作用, 但在涉及到大量数据以及比较特殊的情况时, 我们会发现还是有个别的数据被泄露了.

因此差分隐私的思路被提出:
通过随机算法对发布的信息作随机扰动, 如果攻击者无法判别信息来自于哪个数据集, 则可以说明数据集内的角色隐私受到了保护.

本质上相当于是对统计数据增加了 噪声干扰 , 而这个具体的噪声干扰大小, 是随机的.

给出 敏感度 这一概念:
两个相邻数据集D, D’, 一个查询函数最大的变化范围.

啥意思呢, 就是要被保护的那个个体给这个数据集查询值带来的最大扰动.

公式为: $ \Delta f = max_{D, D’} | | f(D)-f(D’) | | = \frac{personal \ max - personal \ min}{total \ count} $

举个例子, 比如统计你们公司的人均工资水平, 你们公司的总人数100人, 工资分布从 0 ~ 10000.

那 $ \Delta f = \frac{10000 - 0}{100} = 100 $

就是你能给你们公司统计值带来的最大变化量.

然后这个噪声值Y, 我们就从这里面取, 具体取值是一个分布函数, 叫拉普拉斯随机噪声, 与一个参量值 $ \epsilon $ 相关, 这个参量越大, 噪声越小, 反之则越大.

$$ Y \sim L(0, \frac{\Delta f}{\epsilon}) $$

最后在统计数据里面加上这个噪声Y即可:

$$ M(D) = f(D) + Y $$

7.3.2 两类差分隐私

差分隐私也分位置:

• 中心化差分隐私: 认为第三方可信, 在服务器上集中差分隐私
• 本地化差分隐私: 认为第三方不可信, 直接在本地差分隐私完之后上传假数据

7.4 社会网络数据保护

社会的网络数据通常以 图 的形式来展现, 因此, 图的节点自然有些特征, 有时攻击者能通过一些图的特征来确认节点的含义, 进一步对其发动隐私攻击.

图的节点最基本的特征是? 度数 .

7.4.1 k度匿名

相当于不让图中产生度数唯一的节点, 每一个度数至少有k个节点.

那这有问题, 如果人就是很少, 度数就是唯一, 咋办呢?
有个算法叫 K-means聚类算法

它的核心思路是这样:

• K是你要分成的组数. 设总节点数 N
• 在你的节点中找到两个作为收敛中心点
• 将全部节点根据距离左右两个中心点的距离来分组(比如有一个中心节点度数为1, 另一个中心节点度数为7, 那度数为6的节点就要归到7那一组).
• 将分组之后的节点重新计算中心节点度数, 重复上述过程, 直到最终度数稳定为止

7.4.2 子图攻击

子图攻击相当于针对某个特定信息的节点对全图进行子图搜索, 并找到一个符合预设结构的子图.

我们给出一个定义 d层子图 :
在图G中, 由其中某个节点v以及与该节点距离不超过d的节点构成的子图

因此, 最好的方式是构造一个 d-k匿名社会网络 :

保证对于任意一个节点, 至少有其余k-1个节点, 它们的d层子图同构

这样的话, 攻击者就只能找到k个子图结构, 但是不知道到底哪个是被攻击的目标.

这种算法的思路是:

• 提取出所有节点的d层子图, 然后用迭代哈希对所有的子图进行映射编码.
• 最后将k个节点的子图匿名成同构结构.达到对于图的修正目的