一文读懂K匿名算法（Ⅰ）：匿名化的发展

科技的发展总是超乎人们想象

区块链技术不仅已成为时代浪潮里的坚实着陆地

更是未来可以承载巨大变革的基础

【能链科技】将持续更新区块链百科专栏

围绕热点问题进行深入浅出地解读

与你共话技术发展 点亮数字未来

“数据的共享开放”是科学和技术进步的基础，也是研究和开发新应用的必要条件。然而，无论是个人还是企业用户，数据的共享需要考虑适当的保护措施，特别是包含隐私数据时。K匿名算法便是一种保护隐私的数据挖掘方法，然而其发展几经波折。

区块链百科No.57：K匿名算法（Ⅰ）

大数据时代，人们对隐私的定义仍然缺乏共识。

这一事实导致了许多完全不同保护隐私的数据挖掘方法的激增，所有这些方法都有一个共同的目标：在不公开隐私数据的情况下生成一个有效的挖掘模型。

K匿名算法便是通过数据匿名化的处理方式来保护个人数据的隐私。所谓“匿名化”就是在共享数据集内容之前先将其中的隐私信息进行剔除或脱敏处理，以降低数据敏感度和减少个人隐私风险的技术措施。

然而，“匿名化”真的能保护我们的数据隐私吗？

早在1981年，美国计算机科学家Dorothy E. Denning曾在她的一篇关于数据库安全的科学论文中指出，在处理数据时，可能永远无法完全确保不泄露敏感信息。

2008年，科学家Arvind Naranayan和Vitaly Shmatikov发表了他们关于Netflix去匿名化事件的研究。研究人员成功地重新识别了Netflix发布的据称匿名的数据集。

2009年8月，Paul Ohm的论文《违反隐私承诺：回应匿名化的惊人失败》发表。他的最后结论是：“数据要么有用，要么完全匿名，但永远不能两者兼而有之。”

历史似乎在不断重演。这就透出一个大问题：

为什么经过几十年的深入研究和成千上万的科学出版物，还没有开发出一种通用的数据匿名化技术?

为了回答这个问题，我们需要深入研究过去。

让我们在一个广阔的背景下看看匿名化的发展。

我们知道最早大规模使用数据的机构之一，便是美国联邦统计局-人口普查局（Census Bureau）。

19世纪初，美国定期进行人口普查，以确定众议院席位需要如何重新分配、每个州应该征收哪些税以及在发生战争时，国家的军事潜力等。

在此期间，数据保护几乎没有发挥作用。在人口普查的前50年里，人们对隐私并不关心。

这种情况在1850年左右发生了变化，当时人口普查问题的数量和敏感性都有所增加。作为一项安全措施，人口普查局开始从公开的人口普查数据中删除个人数据。

接下来的几十年里，该局使用了各种技术来降低个人在公开数据中被识别的风险。这些技术包括舍入、随机噪声、聚集、单元抑制、单元交换和采样等。

20世纪50年代，人口普查局开始使用电脑制作数据表格，而后上面提到的匿名化技术已经实现了自动化。计算机使分析人员能够“交叉制表”。这极大地提高了分析数据的能力，但也为分析师指定唯一标识个人的查询提供了可能性。

关于数据保护的争论始于20世纪60年代初。

当时，肯尼迪政府计划建立国家数据中心，以进一步完善国家信息系统。公众认为这是对宪法的严重干涉。该项目虽然失败，但引发了对处理个人数据的法律依据的要求。

最终结果是1974年通过了《隐私法》，该法为联邦当局引入了数据处理规则，其中包含了数据保护的基本原则：必要性、安全性和透明度。

美国的辩论在欧洲再次上演。1970年，《黑森数据保护法》出台，被认为是世界上最早的数据保护法。它规定了德国黑森州公共行政部门何时可以处理个人数据，以及在处理时必须遵守哪些要求。

在公众对数据保护讨论的基础上，对匿名化的研究也在加强。但这只是一个仍在持续循环的开始：

最初，人们只发布简单的数据。但随着时间的推移，越来越复杂的数据被发布。为了保护这些数据，人们发明了新的匿名方法，但研究人员总能找到。

直至，1972年统计学家Fellegi提出了一个重要概念——增加噪音，以能够处理更复杂和多样性的数据。当然，噪音必须是不可预测的，即随机的。但在基于查询的系统上下文中，这造成了一个困难。如果产生的每个答案都有一个新的零均值随机噪声样本，那么分析师只需重复该查询多次，然后取平均值来消除噪声。

随后，研究人员Dorothy E. Denning提出在随机数生成器中插入查询本身的内容。但就连她也认识到，这种方法很容易被击破，也未进一步研究过这个问题，完全停止了数据匿名的工作。

事实上，到20世纪80年代中期，整个计算机科学界已经对数据匿名失去了兴趣。这部分是因为它是一个困难的问题，但主要是因为研究界有更紧迫的问题需要解决。而K匿名化算法的提出，重启了“数据匿名化”的复兴。