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）
• 差分隱私