k-匿名性

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

相关

  • 铜合金铜合金是以铜为主的合金,它们能有效地抵抗腐蚀。最多人知道的种类是青铜(铜为主要,锡为次要)和黄铜(铜为主要,锌为次要)。在古代欧洲“青铜”和“黄铜”术语常混用,所以现在欧洲(尤其
  • 里克·佩里詹姆斯·理查德·“里克”·佩里(英语:James Richard "Rick" Perry,1950年3月4日-)是美国共和党政治人物,第14任美国能源部长。2000年-2015年,担任德克萨斯州的州长。1984年,他曾以民
  • 度支使度支使为中国古代官制。“度支”原意是量入为出。唐制,户部的度支司掌管国家的财政收支,郎中和员外郎分别掌管收入和支出,户部侍郎则检查押署帐目。开元时,使用他官判度支。安史
  • 传输线传输线是电子工程中的专用电缆或者其他结构,用于传输无线电频率的交变电流,也就是说,电流的频率高到一定程度时必须考虑它们波的性质。传输线一般用于连接发送器与接收器的天线
  • 氯化锶氯化锶(SrCl2)是锶和氯的盐。这是一种典型的盐,水溶液为中性。与其他锶化合物类似,氯化锶在火焰下呈红色,因此它被用于制造红色烟火。其化学性质介于氯化钡(毒性更强)和氯化钙间。
  • 昆士兰阿胡虾虎鱼昆士兰阿胡虾虎鱼(学名:),为辐鳍鱼纲鲈形目虾虎鱼亚目虾虎鱼科阿胡虾虎鱼属下的一个种,为热带淡水鱼,分布于澳洲昆士兰及新几内亚淡水水域,体长可达18公分,栖息在受潮汐影响、沙泥底
  • 巴彦扎格巴彦扎格(蒙古语:Баянзаг 或 Улаан Эрэг)俗称烈火危崖 ,位于蒙古国南戈壁省的戈壁地区,以在此地发现大量恐龙化石而闻名于世。美国探险家安得思和他的团队在20世
  • 2010年代SBS歌谣大战节目列表《2010年代SBS歌谣大战节目列表》主要列出韩国SBS电视台于2010年至2019年年末举办的K-Pop汇演节目《SBS歌谣大战》的节目内容,包括节目主题、出演歌手及演唱曲目等资讯。
  • 神舟十三号神舟十三号(简称神十三)是中国“神舟”系列飞船的第十三次飞行任务,也是中国载人航天工程的第二十一次任务与第八次载人飞行任务,于2021年10月16日在酒泉卫星发射中心使用长征二号F运载火箭发射升空。神舟十三号在同年6月份神舟十二号发射前早已在地面待命做整备。本次任务计划把三名航天员送到天宫空间站,并将在轨驻留6个月。此后,6个月的驻留就是航天员乘组在轨的常态。前次任务:天舟三号· 下次任务:天舟四号
  • 阿坂城阿坂城(日语:阿坂城/あざかじょう ),又称白米城(日语:白米城/はくまいじょう )或椎之木城(日语:椎之木城/しいのきじょう ),是伊势国一志郡阿坂(现三重县松阪市大阿坂町)曾经存在的一座山城(日语:山城)。城池是伊势国司及后成为战国大名的北畠氏在伊势北部的重要据点。在南北朝时,城池乃南朝北畠氏的势力范围,在称光天皇即位后北畠氏在城池举兵,并且与足利幕府军队交战,虽然最终战败,但是以米洗马的传说却流存至今。尽管,北畠氏在阿坂城战况失利,但最终成功与幕府和解而存续下来。进入战国时代后,织田氏家臣泷川一益曾