k-匿名性

✍ dations ◷ 2025-04-26 14:01:43 #k-匿名性

-匿名性(英语:k-anonymity)是匿名化数据的一种性质。如果一组公开的数据中,任何一个人的信息都不能和其他至少 k 1 {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则提出一个求解-匿名化问题的 O ( log k ) {displaystyle O(log k)} -匿名化是一个定义简洁且具有很多可行算法的手段,可以较好地解决一组数据的匿名化问题,但从其它角度仍然可以攻击满足-匿名性的数据。若攻击者掌握并利用其它背景知识,这些攻击甚至可以更有效率。这些攻击包括:

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

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

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

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

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

相关

  • β链2B5I、​2ERJ、​3BPL、​3QAZ、​3QB7、​4GS7356116186ENSG00000147168ENSMUSG00000031304P31785P34902NM_000206NM_013563、NM_001308535、XM_017318396NP_000197NP_0012
  • 露头露头(英语:outcrop)是地球表面突出可见的岩床(英语:bedrock)或表面沉积物(英语:superficial deposits)。
  • 工藤昌祐工藤昌祐(1520年-1582年)是日本战国时代武将。甲斐武田氏的家臣。武田四名臣之一的内藤昌丰(昌秀)的实兄。别名工藤长门守。武田信虎的重臣工藤虎丰的长男。父亲虎丰因为触怒信虎
  • 葡萄糖醛酸内酯葡萄糖醛酸内酯,简称葡醛内酯,是一种自然产生的化学物质,在人的肝脏所产生的葡萄糖代谢物。这是1种重要的结缔组织的组成成分。在某些都市传说中,认为这是越战时期,美军所制作的
  • 豆钱豆钱,是一种民间用来熬粥的豆制品。在制作过程中,首先把黄豆炒至五成熟,然后将其放在碾子上碾压而成。它也经常用来洒在刚刚搬入新房的卧室内,表示“钱多”的寓意。
  • 罗桑崔臣达吉嘉措罗桑崔臣达吉嘉措(藏语:.mw-parser-output .uchen{font-family:"Qomolangma-Dunhuang","Qomolangma-Uchen Sarchen","Qomolangma-Uchen Sarchung","Qomolangma-Uchen Suring",
  • 维森特·鲁宾逊维森特·鲁宾逊(英语:Vinette Robinson,1981年-)是一位英格兰电影、电视和舞台演员。作品包括《天使薇拉卓克》、《飞天大盗》、《异世奇人》和《神探夏洛克》。鲁宾逊出生于布拉
  • 帕莱帕莱(Pale),是印度果阿邦North Goa县的一个城镇。总人口5706(2001年)。该地2001年总人口5706人,其中男性3024人,女性2682人;0—6岁人口592人,其中男306人,女286人;识字率75.08%,其中男性
  • 骆玉明骆玉明(1951年-),祖籍河南洛阳,寄籍江苏建湖。1951年生于上海。1977年复旦大学中文系毕业,毕业后留校,1979年任助教,1995年任复旦大学中文系教授,博士生导师,《辞海》编委。著有《徐文
  • 苦水河 (宁夏)苦水河位与中国宁夏吴忠市境内,为黄河右岸一级支流。源自甘肃省环县花石山沙坡子沟脑,海拔2026m。向北流入宁夏回族自治区盐池县、同心县和吴忠市利通区境,至灵武市新华桥汇入