k-匿名性

k-匿名性（英語：k-anonymity）是匿名化資料的一種性質。如果一組公開的資料中，任何一個人的資訊都不能和其他至少${\displaystyle k-1}$人區分開，則稱該資料滿足k-匿名性。k-匿名性的概念是由拉坦亞·斯威尼（英語：Latanya Arvette Sweeney）和皮蘭格拉·薩馬拉蒂（英語：Pierangela Samarati）在1998年的一篇論文^[1]中最先提出的，其目的是為了解決如下問題：「給定一組結構化的具體到個人的資料，能否給出一組經過處理的資料，使我們可以證明資料中涉及的個人不能被再辨識（英語：Data re-identification），同時還要保證資料仍具有使用價值。」^[2][3][4]使一組資料滿足k-匿名性的過程稱為k-匿名化（英語：k-anonymization）。

2018年，英國電腦科學家朱納德·阿里（英語：Junade Ali）使用k-匿名性及加密雜湊函數建立了一個通訊協定，可以供人匿名地驗證密碼是否已經洩露、但又不公開所涉及的密碼；k-匿名性因此得到了媒體的廣泛報道。^[5][6]這一協定作為一個公用API部署在了托里·亨特（英語：Tory Hunt）創立的Have I Been Pwned?服務中，且被包括一些密碼管理器^[7][8] 和瀏覽器擴充^[9][10]在內的程式廣泛使用。隨後，谷歌的密碼檢查功能也使用了這一方法。^[11][12][13]

k-匿名化的方法

在k-匿名化問題中，一個資料庫是指一個n行m列的表。表格的每一行表示一條記錄，對應一組物件中的一個。不同行中的記錄可以相同。每列中的值代表物件的一個屬性。下表是一個未經匿名化操作的資料庫，其中包含一些虛構醫療資料。

姓名	年齡	性別	居住地	宗教信仰	疾病
丁一	30	女	北京	佛教	癌症
胡二	24	女	上海	佛教	病毒性疾病
張三	28	女	北京	伊斯蘭教	結核病
李四	27	男	廣東	不信教	無疾病
王五	24	女	上海	基督教	心血管疾病
趙六	23	男	廣東	道教	結核病
孫七	19	男	上海	佛教	癌症
周八	29	男	廣東	佛教	心血管疾病
吳九	17	男	上海	基督教	心血管疾病
鄭十	19	男	上海	基督教	病毒感染

這組資料中有6個屬性、10條記錄。對給定的k，實現k-匿名性有兩個常見的方法。

1. 資料抑制：此種方法將一些屬性的值用星號「*」取代。可以取代一列中的所有值或部分值。在下面的匿名化表格中，我們將「姓名」一欄的所有值、「宗教」一欄的部分值用「*」取代。
2. 資料泛化：此種方法將一些屬性的精確值用更寬泛的類別取代。例如，「年齡」一欄中的「19」可以覆寫為「≤20」，「23」可以覆寫為「20<年齡≤30」，等等。

下表經過了匿名化處理。

識別碼	准識別碼				目標屬性
姓名	年齡	性別	居住地	宗教信仰	疾病
*	20<年齡≤30	女	北京	*	癌症
*	20<年齡≤30	女	上海	*	病毒感染
*	20<年齡≤30	女	北京	*	結核病
*	20<年齡≤30	男	廣東	*	無疾病
*	20<年齡≤30	女	上海	*	心血管疾病
*	20<年齡≤30	男	廣東	*	結核病
*	年齡≤20	男	上海	*	癌症
*	20<年齡≤30	男	廣東	*	心血管疾病
*	年齡≤20	男	上海	*	心血管疾病
*	年齡≤20	男	上海	*	病毒感染

對敵手（英語：Adversary (cryptography)）而言，「年齡」、「性別」和「居住地」雖然單獨不能用於唯一辨識一個個體，但結合起來則可能用於辨識唯一個體的屬性被稱為准識別碼（英語：quasi-identifier）；相應地，「姓名」、「身分證號」等可以唯一辨識一個個體的屬性被稱為識別碼（即ID）。「疾病」、「收入」、「性取向」或其它當事人希望保護的屬性常被稱為「敏感屬性」，也可能成為敵手的「目標屬性」。這組匿名化後的資料對於「年齡」、「性別」和「居住地」三個屬性具有2-匿名性，因為在這組資料中，任意一行在這三列上的值的組合都至少出現了2次。在k-匿名的資料庫中，所有由准識別碼組成的多元組都至少出現k次。^[14]

Meyerson和Williams^[15]的研究表明，求最佳的k-匿名化方案是一個NP困難的問題；然而，利用諸如k-最佳化^[16]的啟發式方法通常也可以得到令人滿意的結果。Kenig和Tassa則提出一個求解k-匿名化問題的${\displaystyle O(\log k)}$近似演算法。^[17]

可能的攻擊

儘管k-匿名化是一個定義簡潔且具有很多可行演算法的手段，可以較好地解決一組資料的匿名化問題，但從其它角度仍然可以攻擊滿足k-匿名性的資料。若攻擊者掌握並利用其它背景知識，這些攻擊甚至可以更有效率。這些攻擊包括：

• 同質性攻擊（英語：Homogeneous attack）：如果目標屬性（攻擊者希望獲知的屬性）在k個條目中的取值都是相同的，則可以進行此種攻擊。這時，就算一組資料已經被k-匿名化，目標屬性在k條記錄中的取值仍然可以被取得。
• 背景知識攻擊（英語：Background knowledge attack）：此種攻擊可以利用目標屬性與准識別碼屬性之間的聯絡來減少目標屬性里可能值的數量。例如，Machanavajjhala等人的研究^[18]表明，利用心臟病在日本人中的發病率較低這一事實，可以在醫療資料庫中縮小一個敏感屬性的取值範圍。

負面影響

由於k-匿名化過程中不包含任何隨機化的因素，攻擊者可以利用這一情況來探知關於個體的資訊。例如在上面的例子中，如果有人已經知道來自上海、19歲的鄭十的資訊包含在上面的資料庫中，則可以可靠地推斷他得了癌症、心血管疾病、或病毒感染中的一種。

k-匿名化方法不適用於高維（即具有很多屬性）資料庫的匿名化。^[19] 例如，有研究^[20]表明，如果給定4個位址，行動電話的時間戳-地點資料庫單一性（英語：Unicity (computer science)）（${\displaystyle {\mathcal {E}}_{4}}$，取${\displaystyle k=1}$的k-匿名性）可能高達95%。

也有研究^[21]表明，如果k-匿名化會不相稱地抑制或泛化不具代表性的屬性，則該過程可能會導致資料庫偏斜。但k-匿名化所使用的抑制或泛化演算法也可以改進，來避免導致資料偏斜的發生。^[22]

基於雜湊的k-匿名化

Junade Ali提出了基於雜湊的k-匿名化方法；這種方法最早是為了進行密碼洩露檢查（英語：Compromised Credential Checking）^[23][5][6]，後來也用於MAC位址的即時匿名化^[24]。

這種方法對一個維度（屬性）的資料進行密碼雜湊化，並截取雜湊碼來使雜湊衝突至少發生${\displaystyle k-1}$次。這個方法可以實現對巨量資料庫（例如密碼洩露資料庫）進行的高效率匿名化檢索。^[25]這種方法還可以將匿名化程度量化，以便使用者在資訊洩露程度和資料的可使用程度之間取捨。^[24][26]

參見

• t-相似性（英語：t-closeness）
• l-多樣性（英語：l-diversity）
• 差分隱私