数据时代，很多机构需要面向公众或研究者发布其收集的数据。然而，这些数据中可能包含这用户的隐私信息。这要求发布者在发布前进行脱敏处理。本文介绍三种数据脱敏方法/标准：k-anonymity、 l \mathcal{l} l -diversity 和 t-closeness。

考虑如下两张表：

下面一张是某医院收集的病人信息，其中已经抹去了姓名、身份证号等信息。但是，直接发布这样简单处理的数据并不安全。因为接受者（recipient）可能知道其他信息，比如上面一张投票信息表。那么recipient就可以通过比对Birthdate、Sex 和 Zipcode 的值得知 Andre 患有 Flu。这种通过某些属性与外部表连接的攻击称为连接攻击。

数据以表的形式表示，每一行表示一条记录（record），每一列表示一个属性（attribute）。每一个记录与一个特定用户/个体关联。这些属性可以分为三类：

当公开数据表时，应避免用户的敏感数据被公开（disclosure），也即不能让观察者（observer）者将某条记录和一个确定的用户联系起来。信息公开（information disclosure）可以分为两类：

另外需要注意的是，我们应当尽量使观察者无法将记录与用户进行连接，而不是使观察者获得错误的信息。因为即使错误的信息也可能给用户带来困扰（比如一个积极阳光的社会主义好青年，天天被推送小电影，这不是坑害祖国的花朵吗！）。

k-anonymity想法十分简单。其首先做了如下假设：

准标识符假设：

数据持有者可以识别出其所持有数据表中可能出现在外部数据中的属性，因此其可以准确的识别出准标识符集合。

显然这个假设可能不成立：比如持有者误判了哪些属性是连接敏感的并将其公开。然而，由于数据持有者并不清楚观察者知道哪些信息，这个问题并不好在算法上予以解决。我们只能依赖算法以外的东西——政策、合同等。反正k-anonymity认为这一假设是合理的。

k-anonymity要求同一个准标识符至少要有k条记录。因此观察者无法通过准标识符连接记录。

上图table1是原数据，table2满足 3-anonymity，准标识符 Q I = { Z I P C o d e ， A g e } QI=\{ZIP Code，Age\} QI={ZIPCode，Age}。Disease是敏感数据。

我们把拥有相同准标识符的所有记录称为一个等价类（equivalence class）。k-anonymity 即是要求同一等价类中的记录不少于k条。把等价类的大小组成的集合称为频率集（frequency fet）。

等价类是一个多重集（multiset），即其中可以有相同的元素。频率集应该也是多重集？

k-anonymity 使得观察者无法以高于 1 k \frac{1}{k} k1​的置信度通过准标识符来识别用户。

k-anonymity 可以阻止身份公开，但无法防止属性公开。比如其无法抵抗一致性攻击和背景知识攻击。

如果一个等价类里的敏感属性至少有 l \mathcal{l} l个 良表示（well-represented) 的取值，则称该等价类具有 l \mathcal{l} l-diversity。如果一个数据表里的所有等价类都具有 l \mathcal{l} l-diversity，则称该表具有 l \mathcal{l} l-diversity。

良表示有三种定义：

最简单的 l \mathcal{l} l-diversity要求同一等价类中的敏感属性要有至少 l \mathcal{l} l个可区分的取值。但是，如果某一个取值的频率明显高于其他取值，这将使得观察者可以以较高的置信度认为这一等价类中的敏感属性都取这个值。这导致了下面两种良表示定义。

记 S S S为敏感属性的取值集合， p ( E , s ) p(E,s) p(E,s)为等价类 E E E中敏感属性取值 s s s的概率，entropy l \mathcal{l} l-diversity要求下式成立： E n t r o p y ( E ) = − ∑ s ∈ S p ( E , s ) log ⁡ p ( E , s ) ≥ log ⁡ l Entropy(E)=-\sum_{s\in S}p(E,s)\log p(E,s)\ge\log l Entropy(E)=−s∈S∑​p(E,s)logp(E,s)≥logl 若每一等价类都满足Entropy l \mathcal{l} l-diversity，那么整张数据表的熵也必然不小于 log ⁡ l \log l logl。这个要求太严格了，比如敏感属性的取值集合中某些取值的频率较高，这将导致整张表的熵比较低。

设等价类 E E E中敏感属性有 m m m种取值，记 r i r_i ri​为出现次数第 i i i多的取值的频次，如果 E E E满足： r 1 ; c ( r l + r l + 1 + … r m ) r_1;c(r_l+r_{l+1}+\dots r_m) r1​