k-匿名性

-匿名性（英语：k-anonymity）是匿名化数据的一种性质。如果一组公开的数据中，任何一个人的信息都不能和其他至少${\displaystyle k-<!--\; -\; -->1}$-匿名性。-匿名性的概念是由拉坦亚·斯威尼（英语：Latanya Arvette Sweeney）和皮兰格拉·萨马拉蒂（英语：Pierangela Samarati）在1998年的一篇论文中最先提出的，其目的是为了解决如下问题：“给定一组结构化的具体到个人的数据，能否给出一组经过处理的数据，使我们可以证明数据中涉及的个人不能被再识别（英语：Data re-identification），同时还要保证数据仍具有使用价值。”使一组数据满足-匿名性的过程称为-匿名化（英语：k-anonymization）。

2018年，英国计算机科学家朱纳德·阿里（英语：Junade Ali）使用-匿名性及加密散列函数创建了一个通讯协议，可以供人匿名地验证密码是否已经泄露、但又不公开所涉及的密码；-匿名性因此得到了媒体的广泛报道。这一协议作为一个公用API部署在了托里·亨特（英语：Tory Hunt）创立的Have I Been Pwned?（英语：Have I Been Pwned?）服务中，且被包括一些密码管理器 和浏览器扩展在内的程序广泛使用。随后，谷歌的密码检查功能也使用了这一方法。

在-匿名化问题中，一个数据库是指一个行列的表。表格的每一行表示一条记录，对应一组对象中的一个。不同行中的记录可以相同。每列中的值代表对象的一个属性。下表是一个未经匿名化操作的数据库，其中包含一些虚构医疗数据。

这组数据中有6个属性、10条记录。对给定的，实现-匿名性有两个常见的方法。

下表经过了匿名化处理。

对敌手（英语：Adversary (cryptography)）而言，“年龄”、“性别”和“居住地”虽然单独不能用于唯一识别一个个体，但结合起来则可能用于识别唯一个体的属性被称为准标识符（英语：quasi-identifier）；相应地，“姓名”、“身份证号”等可以唯一识别一个个体的属性被称为标识符（即ID）。“疾病”、“收入”、“性取向”或其它当事人希望保护的属性常被称为“敏感属性”，也可能成为敌手的“目标属性”。这组匿名化后的数据对于“年龄”、“性别”和“居住地”三个属性具有2-匿名性，因为在这组数据中，任意一行在这三列上的值的组合都至少出现了2次。在-匿名的数据库中，所有由准标识符组成的多元组都至少出现次。

Meyerson和Williams的研究表明，求最优的-匿名化方案是一个NP困难的问题；然而，利用诸如-优化的启发式方法通常也可以得到令人满意的结果。Kenig和Tassa则提出一个求解-匿名化问题的${\displaystyle O(\log <!--\; \; -->k)}$-匿名化是一个定义简洁且具有很多可行算法的手段，可以较好地解决一组数据的匿名化问题，但从其它角度仍然可以攻击满足-匿名性的数据。若攻击者掌握并利用其它背景知识，这些攻击甚至可以更有效率。这些攻击包括：

由于-匿名化过程中不包含任何随机化的因素，攻击者可以利用这一情况来探知关于个体的信息。例如在上面的例子中，如果有人已经知道来自上海、19岁的郑十的信息包含在上面的数据库中，则可以可靠地推断他得了癌症、心血管疾病、或病毒感染中的一种。

-匿名化方法不适用于高维（即具有很多属性）数据库的匿名化。 例如，有研究表明，如果给定4个地址，移动电话的时间戳-地点数据库单一性（英语：Unicity (computer science)）（${\displaystyle {\mathcal{E}}_4}$-匿名性）可能高达95%。

也有研究表明，如果-匿名化会不相称地抑制或泛化不具代表性的属性，则该过程可能会导致数据库偏斜。但-匿名化所使用的抑制或泛化算法也可以改进，来避免导致数据偏斜的发生。

Junade Ali提出了基于散列的-匿名化方法；这种方法最早是为了进行密码泄露检查（英语：Compromised Credential Checking），后来也用于MAC地址的实时匿名化。

这种方法对一个维度（属性）的数据进行密码散列化，并截取散列码来使散列冲突至少发生${\displaystyle k-<!--\; -\; -->1}$次。这个方法可以实现对大数据库（例如密码泄露数据库）进行的高效率匿名化检索。这种方法还可以将匿名化程度量化，以便用户在信息泄露程度和数据的可使用程度之间取舍。