k-匿名性

✍ dations ◷ 2025-04-02 08:56:06 #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} 次。这个方法可以实现对大数据库(例如密码泄露数据库)进行的高效率匿名化检索。这种方法还可以将匿名化程度量化,以便用户在信息泄露程度和数据的可使用程度之间取舍。

相关

  • 满文满文(满语:ᠮᠠᠨᠵᡠᡥᡝᡵᡤᡝᠨ,穆麟德:Manju hergen,太清:Manju hergen,大词典:Manzhu hergen)是满语的文字,1600年前后由蒙古文改造而成,是全音素文字。由上至下竖写,各列由左至右
  • UTC+4UTC+04:00时区比协调世界时快上4小时,使用于以下区域:
  • 塞尔福里奇百货公司Selfridges(官方不使用译名,亦称Selfridge & Co.)是一家英国的高档百货公司,由哈里·戈登·塞尔福里奇于1909年创立,其位于伦敦牛津街的旗舰店在1909年3月15日开业,是目前仅次于哈
  • 诺顿·西蒙博物馆诺顿·西蒙博物馆是一家位于美国加州帕萨迪纳的艺术博物馆。它的前身是帕萨迪纳美术馆和帕萨迪纳艺术博物馆。诺顿·西蒙的藏品包括:欧洲绘画、雕塑和挂毯;亚洲雕塑、绘画和木
  • 棕鬣狗棕鬣狗(学名:Parahyaena brunnea)又称 褐鬣狗、滩狼,是一种生活在南部非洲荒漠地带的鬣狗,也见于草原和海滩,系 棕鬣狗属(Parahyaena)的唯一物种,也有学者将其归入鬣狗属(Hyaena)。外形
  • 马尼尔瓦马尼尔瓦(西班牙语:Manilva),是西班牙安达卢西亚自治区马拉加省的一个市镇。 总面积35平方公里,总人口6303人(2001年),人口密度180人/平方公里。
  • 布鲁诺·马代尔纳布鲁诺·马代尔纳(意大利语:Bruno Maderna,1920年4月21日-1973年11月13日),意大利作曲家、指挥家,曾随马利皮耶罗学作曲,又随舍尔兴学指挥。长期在德国活动。1955年与贝里奥一同创办
  • 熙敬熙敬(?-1900年),全名苏完呢瓜尔佳熙敬,苏完呢瓜尔佳氏,满洲镶黄旗人,清朝政治人物。监生出身。咸丰三年,任工部主事上行走。咸丰六年,升任工部主事。次年,升任工部员外郎。同治三年,任直
  • 东沙织东沙织(日语:東 さおり,4月8日-),日本女性配音员。81 Produce所属。出身于三重县。O型血。※粗体字表示说明饰演的主要角色。表示说明饰演至今的作品系列。
  • 象山 (台北市)坐标:25°01′37″N 121°34′36″E / 25.02690°N 121.57664°E / 25.02690; 121.57664 (象山 (台北市)) 象山位于台北市信义区,位于台北盆地东缘的南港山系西侧,因山形似象而