檢視 K-匿名性的原始碼

'''_ k _-匿名性'''（英語：k-anonymity）是匿名化資料的一種性質。若是一組公開的資料內底，任何一个人的訊息攏袂使佮其他至少 $ k 影一 $ 人區分開，講的這个資料滿足 _ k _-匿名性。_ k _-匿名性的概念是由拉坦亞 ・ 斯威尼佮皮蘭格拉 ・ 薩馬拉蒂佇一九九八年的一篇論文中上先提出的，其目的就是欲為著欲解決如下的問題：「 予定一組結構化的具體到個人的資料，敢會當予出一組經過處理的資料，予咱會當證明資料當中牽涉著的個人袂當予人閣辨識，同時閣愛保證資料猶原有使用的價值。」使一組的資料滿足 _ k _-匿名性的過程講號做'''_ k _-匿名化'''（英語：k-anonymization）。

二空一八年，英國電腦科學家朱納德 ・ 阿里使用 _ k _-匿名性佮加密雜鬥函數建立了一个通訊協定，會當予人無頭路驗證密碼是毋是已經泄露、但是閣無公開所牽涉著的密碼；_ k _-匿名性所致得著媒體的廣泛報導。這一協定做一个公用 API 部署佇托里 ・ 亨特創立的 Have I Been Pwned ? 服務中，而且予包括一寡密碼管理器佮瀏覽器擴充在內的程式廣泛使用。隨後，Google 的密碼檢查功能嘛使用矣這一方法。

==_ k _-無頭路的方法==

佇咧 _ k _-匿名化問題中，一个資料庫是講一个 _ n _ 走 _ m _ 列的表。表格的每一行表示一條記錄，對應一組物件內底的一个。無仝途中的記錄會當仝款。每列中的值代表物件的一个屬性。下表是一个未經匿名化操作的資料庫，其中包括一寡虛構醫療資料。

這組資料當中有六個屬性、十條記錄。著予定的 _ k _，實現 _ k _-匿名性有兩个定定看著的方法。

一 .'''資料或者制'''：這種方法將一寡屬性的值用星號「\ *」取代。會當取代一列中的所有值抑是部份值。佇下跤的匿名化表格中，阮共「姓名」一欄的所有值、「 宗教」一欄的部份值用「\ *」取代。
二 .'''資料泛化'''：這種方法共一寡屬性的精確值用閣較闊的類別取代。比如講，「 年齡」一欄中的「十九」會當寫為啥物「≤ 二十」，「 二十三」會當寫為啥物「二十 < 年齡 ≤ 三十」，等咧。

下表經過矣無頭路處理。

對敵手來講，「 年齡」、「 性別」和「咧蹛的所在」雖然單獨袂當致使唯一辨識一个個體，但結合起來是可能會用於辨識唯一个體的屬性予人號做准識別碼；相應的喔，「 姓名」、「 身份證號」等會當唯一辨識一个個體的屬性予人號做是識別碼（即 ID）。「病疼」、「 收入」、「 性取向」抑是其他的當事人望保護的屬性定予人號做「敏感屬性」，嘛是會當變做敵手的「目標屬性」。 這組無頭路的資料對「年齡」、「 性別」和「咧蹛的所在」三个屬性有二-匿名性，因為佇這組資料當中，任意一走佇這三列頂懸的值的組合攏上無出現兩擺。佇咧 _ k _-匿名的資料庫內底，所有的由准識別碼組成的多元組攏至少出現 _ k _ 次。

Meyerson 和 Williams 的研究表明，求上好的 _ k _-匿名化方案是一个 NP 困難的問題；毋過，利用諸如 _ k _-最佳化的啟發式方法通常嘛會當得著予人滿意的結果。Kenig 和 Tassa 提出一个求解 _ k _-匿名化問題的 $ O ( \ log k ) $ 近近演算法。

==可能的攻擊==

就算講 _ k _-無頭路是一个定義義簡潔而且有真濟會當演算法的手段，會使較好解決一組資料的匿名化問題，毋過其他的角度會當攻擊予滿足 _ k _-無頭的這个資料。若攻擊者掌握閣利用其他的背景智識，遮的攻擊甚至會當閣較有效率。遮的攻擊包括：

* 同質性攻擊（英語：Homogeneous attack）： 若目標屬性（攻擊者向望知影的屬性）佇咧 _ k _ 條目中的取值攏是相仝的，會當進行這款的攻擊。這陣，就算一組的資料已經予人 _ k _-匿名化，目標屬性佇咧 _ k _ 條記錄中的取值猶原會當予人取得。
* 背景智識攻擊（英語：Background knowledge attack）： 這款的攻擊會當利用目標屬性佮准識別碼屬性之間的聯絡來減少目標屬性里可能值的數量。比如講，Machanavajjhala 等人的研究表明，利用心臟病佇日本人內底的發病率較低這事實，會當佇醫療資料庫縮小一个敏感屬性的取值範圍。

==負面影響==

因為 _ k _-無頭路的過程當中無包含任何隨機化的因素，攻擊者會當利用這一狀況來探知關於一个訊息。比如講佇頂懸的比如講中間，若有人已經知影來自上海、十九歲的鄭十的訊息包含佇頂懸的資料庫中，著癌症會當靠地推斷伊著癌、心血管疾病、抑是病毒感染中的一種。

_ k _-匿名化方法無適用佇高維（即具有誠濟屬性）資料庫的匿名化。比如講，有研究表明，若予定四个位址，行動電話的時間揬-地點資料庫單一性（$ { \ mathcal { E } } _ { 四 } $，號 $ k=一 $ 的 _ k _-匿名性）可能到九十五。

原仔有研究表明，若是 _ k _-匿名化會不相稱地或制或泛化不具代表性的屬性，過程可能會致使資料庫歪斜。猶毋過 _ k _-匿名化所使用的壓制抑是泛化演算法嘛會當改進，來避免致使資料偏趨的發生。

==因為雜鬥的 _ k _-匿名化==

Junade Ali 提出了基於雜鬥的 _ k _-匿名化方法；這種方法上早是為著欲進行密碼泄露檢查，尾仔嘛用於著 MAC 位址的即時匿名化。

這種方法對一个維度（屬性）的資料進行密碼雜鬥化，並且提雜鬥碼來使雜鬥衝突至少發生 $ k 影一 $ 次。這个方法會當實現對大數據庫（比如講密碼泄露資料庫）進行的高效率覕名化檢索。這種方法閣會使共無頭路的程度量化，通好使用者佇咧訊息泄露程度佮資料的通使用程度之間取捨。

==參見==

* _ t _-相仝性
* _ l _-多樣性
* 差分隱私

==參考資料==

[[分類: 待校正]]