K-匿名性

来自testwiki
跳转到导航 跳转到搜索

Template:DISPLAYTITLE Template:NoteTA k-匿名性（Template:Lang-en）是匿名化数据的一种性质。如果一组公开的数据中，任何一个人的信息都不能和其他至少k−1人区分开，则称该数据满足k-匿名性。k-匿名性的概念是由Template:Tsl和Template:Tsl在1998年的一篇论文[1]中最先提出的，其目的是为了解决如下问题：“给定一组结构化的具体到个人的数据，能否给出一组经过处理的数据，使我们可以证明数据中涉及的个人不能被Template:Tsl，同时还要保证数据仍具有使用价值。”[2][3][4]使一组数据满足k-匿名性的过程称为k-匿名化（Template:Lang-en）。

2018年，英国计算机科学家Template:Tsl使用k-匿名性及加密散列函数创建了一个通讯协议，可以供人匿名地验证密码是否已经泄露、但又不公开所涉及的密码；k-匿名性因此得到了媒体的广泛报道。[5][6]这一协议作为一个公用API部署在了Template:Tsl创立的Have I Been Pwned?服务中，且被包括一些密码管理器[7][8] 和浏览器扩展[9][10]在内的程序广泛使用。随后，谷歌的密码检查功能也使用了这一方法。[11][12][13]

k-匿名化的方法

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

姓名 年龄 性别 居住地 宗教信仰 疾病
丁一 30 女 北京 佛教 癌症
胡二 24 女 上海 佛教 病毒性疾病
张三 28 女 北京 伊斯兰教 结核病
李四 27 男 广东 不信教 无疾病
王五 24 女 上海 基督教 心血管疾病
赵六 23 男 广东 道教 结核病
孙七 19 男 上海 佛教 癌症
周八 29 男 广东 佛教 心血管疾病
吴九 17 男 上海 基督教 心血管疾病
郑十 19 男 上海 基督教 病毒感染

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

  1. 数据抑制：此种方法将一些属性的值用星号“*”取代。可以取代一列中的所有值或部分值。在下面的匿名化表格中，我们将“姓名”一栏的所有值、“宗教”一栏的部分值用“*”取代。
  2. 数据泛化：此种方法将一些属性的精确值用更宽泛的类别取代。例如，“年龄”一栏中的“19”可以改写为“≤20”，“23”可以改写为“20<年龄≤30”，等等。

下表经过了匿名化处理。

标识符 准标识符 目标属性
姓名 年龄 性别 居住地 宗教信仰 疾病
* 20<年龄≤30 女 北京 * 癌症
* 20<年龄≤30 女 上海 * 病毒感染
* 20<年龄≤30 女 北京 * 结核病
* 20<年龄≤30 男 广东 * 无疾病
* 20<年龄≤30 女 上海 * 心血管疾病
* 20<年龄≤30 男 广东 * 结核病
* 年龄≤20 男 上海 * 癌症
* 20<年龄≤30 男 广东 * 心血管疾病
* 年龄≤20 男 上海 * 心血管疾病
* 年龄≤20 男 上海 * 病毒感染

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

Meyerson和Williams[15]的研究表明，求最优的k-匿名化方案是一个NP困难的问题；然而，利用诸如k-优化[16]的启发式方法通常也可以得到令人满意的结果。Kenig和Tassa则提出一个求解k-匿名化问题的O(log⁡k)近似算法。[17]

可能的攻击

尽管k-匿名化是一个定义简洁且具有很多可行算法的手段，可以较好地解决一组数据的匿名化问题，但从其它角度仍然可以攻击满足k-匿名性的数据。若攻击者掌握并利用其它背景知识，这些攻击甚至可以更有效率。这些攻击包括：

  • 同质性攻击（Template:Lang-en）：如果目标属性（攻击者希望获知的属性）在k个条目中的取值都是相同的，则可以进行此种攻击。这时，就算一组数据已经被k-匿名化，目标属性在k条记录中的取值仍然可以被获取。
  • 背景知识攻击（Template:Lang-en）：此种攻击可以利用目标属性与准标识符属性之间的联系来减少目标属性里可能值的数量。例如，Machanavajjhala等人的研究[18]表明，利用心脏病在日本人中的发病率较低这一事实，可以在医疗数据库中缩小一个敏感属性的取值范围。

负面影响

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

k-匿名化方法不适用于高维（即具有很多属性）数据库的匿名化。[19] 例如，有研究[20]表明，如果给定4个地址，移动电话的时间戳-地点数据库Template:Tsl（ℰ4，取k=1的k-匿名性）可能高达95%。

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

基于散列的k-匿名化

Junade Ali提出了基于散列的k-匿名化方法；这种方法最早是为了进行Template:Tsl[23][5][6]，后来也用于MAC地址的实时匿名化[24]。

这种方法对一个维度（属性）的数据进行密码散列化，并截取散列码来使散列冲突至少发生k−1次。这个方法可以实现对大数据库（例如密码泄露数据库）进行的高效率匿名化检索。[25]这种方法还可以将匿名化程度量化，以便使用者在信息泄露程度和数据的可使用程度之间取舍。[24][26]

参见

参考资料

Template:Reflist

  1. ↑ Template:Cite web
  2. ↑ P. Samarati. Protecting Respondents' Identities in Microdata Release Template:Wayback. IEEE Transactions on Knowledge and Data Engineering archive Volume 13 Issue 6, November 2001.
  3. ↑ Template:Cite web
  4. ↑ L. Sweeney. k-anonymity: a model for protecting privacy Template:Wayback. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10 卌, 2002; 557-570.
  5. ↑ 5.0 5.1 Template:Cite news
  6. ↑ 6.0 6.1 Template:Cite web
  7. ↑ Template:Cite news
  8. ↑ Template:Cite news
  9. ↑ Template:Cite news
  10. ↑ Template:Cite news
  11. ↑ Template:Cite web
  12. ↑ Template:Cite web
  13. ↑ Template:Cite web
  14. ↑ Template:Cite web
  15. ↑ Template:Cite book
  16. ↑ Template:Cite book
  17. ↑ Template:Cite journal
  18. ↑ Template:Cite journal
  19. ↑ Template:Cite conference
  20. ↑ Template:Cite journal
  21. ↑ Template:Cite web
  22. ↑ Template:Cite journal
  23. ↑ Template:Cite arxiv
  24. ↑ 24.0 24.1 Template:Cite journal
  25. ↑ Template:Cite book
  26. ↑ Template:Cite journal
检索自“https://zh.wiki.beta.math.wmflabs.org/w/index.php?title=K-匿名性&oldid=12011”