目录

1.隐私分析

2.语义隐私

3.差分隐私

4.语义隐私和差分隐私的关系

1.隐私分析

假如我们现在有一个学生表，有三个字段：姓名、性别、考试通过情况。

其中姓名和性别是可以公开的，考试通过情况是个人隐私。我们开放这个数据的查询，但是不想暴露个人的隐私信息——考试通过情况。

现在有人想访问一些关于这个数据的信息：

（1）查询“Orhan的成绩”：这个查询会直接返回隐私信息，要拒绝这种形式的查询。

（2）查询“多少个学生通过了这个考试”：这种查询涉及到的是总体的信息，没有涉及到个人的隐私信息，可以响应这个查询。

（3）查询“有多少个女生没通过这个考试”：表面上看好像没有泄露敏感信息，但是在上面这  个数据例子中，是会泄露的，因为只有两个女生（这个信息是公开的），查询响应会是2，能够推导出Aisha和Erica没有通过。

因此，如果我们的数据库管理员总是说实话，那么我们必须拒绝单条记录的查询，但只是拒绝单条记录的查询也不一定能保护好隐私，如上面的（3）所示，并且还存在一种攻击手法叫差分攻击

攻击者想知道Aisha是否通过考试，于是进行了两步查询：

1.查询所有人中通过考试的人数

2.查询除Aisha以外的人通过考试的人数

然后做差，如果是0则Aisha没通过考试，如果是1则Aisha通过考试，隐私泄露了！

差分攻击的核心做法就是找两个只差一条记录的数据集，分别做查询，再比较结果的差异，来获取两个集合所相差的记录的敏感信息.。 所以我们最直接的想法也就是，通过随机化的查询（即管理员不能总说实话），使得攻击者无法区分只差一条记录的两个集合。这便是差分隐私.

所以我们需要一种机制，能够对用户查询提供有用的响应，又能够保护数据中的个人隐私。然而现实是，又提供完全精确的查询响应，又能够完全保护隐私，这种条件成立的场景很少见。但是，我们可以通过随机化或近似查询的响应，放松一点精确性，但是数据有较好的隐私性。

结合上面第一个例子，我们可以设计一种随机机制，当张三对数据发起请求查询q，我们不返回给他一个真实的响应A，而是返回A+N，这里N是一个随机变量，它有如下PMF（概率质量函数：离散随机变量在各特定取值上的概率）：

如果查询q的真实响应是A，返回给张三的结果也是A的概率是25%，返回范围在[A-1, A+1]内的概率是55%（25%+30%），返回范围在[A-2, A+2]内的概率是73%，以此类推。 

当张三发起请求“有多少个女生没通过这个考试”，我们通过以上机制返回响应1，那张三就比较难断定真实的响应是0，1还是2。

假如张三在发起查询前，通过查询整体的通过率，可以认为每个人未通过考试的概率是40%，这个是张三现在对这个数据的认识。那返回给他有1个女生没有通过考试的结果后，张三的认识会有什么变化呢，比如，张三可以认为Aisha未通过考试的概率是多少呢？

让AF和EF分别表示Aisha和Erica未通过考试，我们想要计算

由贝叶斯公式

其中

通过平均AF和BF的各种情况，得到

最终得到 

我们可以从以上的计算中看到，张三知道“有多少个女生没通过这个考试”的近似查询结果后，认为Aisha未通过考试的概率从原来的40%变化为了43%。我们可以认为在查询前后，张三对数据中个人隐私的“认知”或者“知识”几乎没有发生变化，对精确的查询结果加上随机变量噪声的近似方式，加强了数据的隐私性。

2.语义隐私

首先我们约定一些语义隐私相关符号：

 是一个集合，数据库的每一行在这个集合里取值，比如是所有的三元组（姓名，性别，考试通过情况）组成的集合。我们固定数据库的行数为 ，那么一个数据库  是幂集（的所有子集组成的集合）中的一个元素。查询是一个函数  ，输入数据库，输出某些值。

为附加到查询的随机机制，输入一个数据库，得到一个随机化的查询结果（对应上个例子的A+N这个操作）

 为数据库随机变量，表示数据库第  行内容

 为定义在数据库行上的映射，比如输出考试通过情况

表示概率分布

语义隐私定义：一个定义域为的机制，如果对于每个，每个数据库，每种，每种可能的 的输出 ，都满足

则说机制M满足ε-语义隐私。

我们来看一个极端的设定，当 ，得到

也就是说在得到 的查询响应前后，在第行上的概率是完全相同的，也可以说在第

行上的先验概率和后验概率是相同的，观察的响应后不会揭露第行任何的附加信息。满足这种情况的机制有极好的隐私性，但是也不会提供关于这个数据库的任何信息了。所以，一般让 取一个比较小的数，比如0.05，让满足这种条件就可以了，前后的概率仍然相似，又能通过获得一些有用的信息。

3.差分隐私

首先我们约定一些差分隐私相关符号与定义：

 ：数据全体（类比于前面隐私符号中的）

：数据集（类比于前面隐私符号中的），为的子集，当仅为一个记录时，。当有多条记录时（也就是多维的），我们为了讨论方便，可以表示数据库为一个向量， 每个分量  代表全集中的一种记录出现的次数，所以，表示所有非负整数的集合。

邻近集：只相差一条记录的一对数据集. 即（后面会详细讲）

查询：映射函数 ：，它表示的是数据集到一个维空间的映射关系 

机制：附加到查询的随机机制，输入一个数据库，得到一个随机化的查询结果（对                    应 + 噪声 这个操作）

差分隐私定义：若机制对于任一输出集合和任意邻近集，总有：

则称  满足   -(近似)差分隐私. 当=0时，称为-差分隐私. 其中称为隐私预算。

我们来看一个极端的设定，当 ， = 0，得到

然后调换D和D&＃39;的角色，我们可以得到另一个方向的不等式，结合通过这两个不等式得到

因为这个等式对输出集合中任意值都成立，只有和输入没半毛钱关系才行，也就是说独立于输入，那这个查询自然不会反映这一对输入的数据库的信息。也是一般让  取一个比较小的数，得到一些折中。

通过调换D和D&＃39;的角色，我们也能得到

直白地说，就是任意邻近的两个数据库，进行查询机制后，这两个数据库分别得到的结果有相似的概率分布。

 -差分隐私保证了机制在每对相邻数据库上的输出在概率上几乎相同。-差分隐私则对-差分隐私进行了一定的松弛。那  具体是怎么进行松弛的呢，我们先引入隐私损失（privacy loss）的定义

上式为隐私损失的定义。这个损失可以是正的（当在数据库 D 下事件的概率比在数据库D&＃39;下更大），也可以是负的（当在数据库 D&＃39; 下事件的概率比在数据库 D 下更大）。

（1）( ε, 0 )-差分隐私保证了：对于所有相邻的数据库D,D&＃39;，隐私损失的绝对值将小于等于 

（2）( ε, δ )-差分隐私保证了：对于所有相邻的数据库 D,D&＃39;，隐私损失的绝对值将以1-的概率小于等于（所以又叫失败概率）

上面（1）很容易证明，​​​​​​​，（2）的证明将在后面的文章讨论。使用隐私损失也可以定量地去比较不同的差分隐私技术

4.语义隐私和差分隐私的关系

语义隐私与差分隐私的关系：

​​​​​​​可以证明，如果是满足ε-差分隐私的，则是满足ε-语义隐私

而且使用差分隐私的定义比语义隐私要更方便，要验证一个机制是满足差分隐私，我们只需要证明对于每一对临近的数据库，这个机制不能充分区分它们，而不是像语义隐私，要考虑每个数据库、每一行、每种  的先验和后验概率。