k-匿名性

本頁使用了標題或全文手工轉換
維基百科，自由的百科全書

k-匿名性（英語：k-anonymity）是匿名化數據的一種性質。如果一組公開的數據中，任何一個人的資訊都不能和其他至少人區分開，則稱該數據滿足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?（英語：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-匿名化問題的近似演算法。[17]

可能的攻擊

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

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

負面影響

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

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

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

基於雜湊的k-匿名化

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

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

參見

參考資料

  1. ^ Samarati, Pierangela; Sweeney, Latanya. Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression (PDF). Harvard Data Privacy Lab. 1998 [2017-04-12]. （原始內容存檔 (PDF)於2021-03-11）. 
  2. ^ P. Samarati. Protecting Respondents' Identities in Microdata Release （頁面存檔備份，存於互聯網檔案館）. IEEE Transactions on Knowledge and Data Engineering archive Volume 13 Issue 6, November 2001.
  3. ^ L. Sweeney. Database Security: k-anonymity. [2014-01-19]. （原始內容存檔於2014-06-16）. 
  4. ^ L. Sweeney. k-anonymity: a model for protecting privacy （頁面存檔備份，存於互聯網檔案館）. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10 卌, 2002; 557-570.
  5. ^ 5.0 5.1 Find out if your password has been pwned—without sending it to a server. Ars Technica. [2018-05-24]. （原始內容存檔於2021-06-13） （美國英語）. 
  6. ^ 6.0 6.1 1Password bolts on a 'pwned password' check – TechCrunch. techcrunch.com. [2018-05-24]. （原始內容存檔於2021-01-17） （美國英語）. 
  7. ^ 1Password Integrates With 'Pwned Passwords' to Check if Your Passwords Have Been Leaked Online. [2018-05-24]. （原始內容存檔於2021-03-20） （英語）. 
  8. ^ Conger, Kate. 1Password Helps You Find Out if Your Password Is Pwned. Gizmodo. [2018-05-24]. （原始內容存檔於2021-07-08） （美國英語）. 
  9. ^ Condon, Stephanie. Okta offers free multi-factor authentication with new product, One App. ZDNet. [2018-05-24]. （原始內容存檔於2021-03-11） （英語）. 
  10. ^ Coren, Michael J. The world's biggest database of hacked passwords is now a Chrome extension that checks yours automatically. Quartz. [2018-05-24]. （原始內容存檔於2021-02-17） （美國英語）. 
  11. ^ Wagenseil I, Paul. Google's New Chrome Extension Finds Your Hacked Passwords. www.laptopmag.com. [2021-08-11]. （原始內容存檔於2021-06-27）. 
  12. ^ Google Launches Password Checkup Extension to Alert Users of Data Breaches. BleepingComputer. [2021-08-11]. （原始內容存檔於2021-04-29） （美國英語）. 
  13. ^ Dsouza, Melisha. Google's new Chrome extension 'Password CheckUp' checks if your username or password has been exposed to a third party breach. Packt Hub. 2019-02-06 [2021-08-11]. （原始內容存檔於2021-05-07）. 
  14. ^ Narayanan, Arvind; Shmatikov, Vitaly. Robust De-anonymization of Large Sparse Datasets (PDF). [2021-08-11]. （原始內容存檔 (PDF)於2021-01-26）. 
  15. ^ Roberto J. Bayardo; Rakesh Agrawal. Data Privacy through Optimal k-anonymization (PDF). 2005: 217–28 [2021-08-11]. ISBN 978-0-7695-2285-2. ISSN 1084-4627. S2CID 17044848. doi:10.1109/ICDE.2005.42. （原始內容存檔 (PDF)於2020-11-23）. Data de-identification reconciles the demand for release of data for research purposes and the demand for privacy from individuals. This paper proposes and evaluates an optimization algorithm for the powerful de-identification procedure known as k-anonymization. A k-anonymized dataset has the property that each record is indistinguishable from at least k - 1 others. Even simple restrictions of optimized k-anonymity are NP-hard, leading to significant computational challenges. We present a new approach to exploring the space of possible anonymizations that tames the combinatorics of the problem, and develop data-management strategies to reduce reliance on expensive operations such as sorting. Through experiments on real census data, we show the resulting algorithm can find optimal k-anonymizations under two representative cost measures and a wide range of k. We also show that the algorithm can produce good anonymizations in circumstances where the input data or input parameters preclude finding an optimal solution in reasonable time. Finally, we use the algorithm to explore the effects of different coding approaches and problem variations on anonymization quality and performance. To our knowledge, this is the first result demonstrating optimal k-anonymization of a nontrivial dataset under a general model of the problem.  |journal=被忽略 (幫助)
  16. ^ Adam Meyerson; Ryan Williams. On the Complexity of Optimal K-Anonymity (PDF). New York, NY: ACM. 2004: 223–8 [2021-08-11]. ISBN 978-1581138580. S2CID 6798963. doi:10.1145/1055558.1055591. （原始內容存檔 (PDF)於2014-05-28）. The technique of k-anonymization has been proposed in the literature as an alternative way to release public information, while ensuring both data privacy and data integrity. We prove that two general versions of optimal k-anonymization of relations are NP-hard, including the suppression version which amounts to choosing a minimum number of entries to delete from the relation. We also present a polynomial time algorithm for optimal k-anonymity that achieves an approximation ratio independent of the size of the database, when k is constant. In particular, it is a O(k log k)-approximation where the constant in the big-O is no more than 4. However, the runtime of the algorithm is exponential in k. A slightly more clever algorithm removes this condition, but is a O(k logm)-approximation, where m is the degree of the relation. We believe this algorithm could potentially be quite fast in practice.  |journal=被忽略 (幫助)
  17. ^ Kenig, Batya; Tassa, Tamir. A practical approximation algorithm for optimal k-anonymity. Data Mining and Knowledge Discovery. 2012, 25: 134–168. S2CID 14158546. doi:10.1007/s10618-011-0235-9. 
  18. ^ Machanavajjhala, Ashwin; Kifer, Daniel; Gehrke, Johannes; Venkitasubramaniam, Muthuramakrishnan. L-diversity: Privacy Beyond K-anonymity. ACM Transactions on Knowledge Discovery from Data. March 2007, 1 (1): 3–es. ISSN 1556-4681. S2CID 679934. doi:10.1145/1217299.1217302. Background Knowledge Attack. Alice has a pen-friend named Umeko who is admitted to the same hospital as Bob and whose patient records also appear in the table shown in Figure 2. Alice knows that Umeko is a 21-year-old Japanese female who currently lives in zip code 13068. Based on this information, Alice learns that Umeko’s information is contained in record number 1,2,3, or 4. Without additional information, Alice is not sure whether Umeko caught a virus or has heart disease. However, it is well known that Japanese have an extremely low incidence of heart disease. Therefore Alice concludes with near certainty that Umeko has a viral infection. 
  19. ^ Aggarwal, Charu C. On k-Anonymity and the Curse of Dimensionality. VLDB '05 – Proceedings of the 31st International Conference on Very large Data Bases. Trondheim, Norway. 2005. ISBN 1-59593-154-6. 
  20. ^ de Montjoye, Yves-Alexandre; César A. Hidalgo; Michel Verleysen; Vincent D. Blondel. Unique in the Crowd: The privacy bounds of human mobility. Scientific Reports. 2013-03-25, 3: 1376 [2021-08-11]. Bibcode:2013NatSR...3E1376D. PMC 3607247 可免費查閱. PMID 23524645. doi:10.1038/srep01376. 
  21. ^ Angiuli, Olivia; Joe Blitzstein; Jim Waldo. How to De-Identify Your Data. ACM Queue. ACM. [2021-08-11]. （原始內容存檔於2021-04-22）. 
  22. ^ Angiuli, Olivia; Jim Waldo. Statistical Tradeoffs between Generalization and Suppression in the De-Identification of Large-Scale Data Sets. IEEE Computer Society Intl Conference on Computers, Software, and Applications. June 2016: 589–593. ISBN 978-1-4673-8845-0. S2CID 17716908. doi:10.1109/COMPSAC.2016.198. 
  23. ^ Li, Lucy; Pal, Bijeeta; Ali, Junade; Sullivan, Nick; Chatterjee, Rahul; Ristenpart, Thomas. Protocols for Checking Compromised Credentials. 2019-09-04. arXiv:1905.13737 可免費查閱 [cs.CR]. 
  24. ^ 24.0 24.1 Ali, Junade; Dyo, Vladimir. Practical Hash-based Anonymity for MAC Addresses. 17th International Conference on Security and Cryptography (SECRYPT 2020). 2020: 572–579. ISBN 978-989-758-446-6. S2CID 218629946. arXiv:2005.06580 可免費查閱. doi:10.5220/0009825105720579. 
  25. ^ Thomas, Kurt; Pullman, Jennifer; Yeo, Kevin; Raghunathan, Ananth; Kelley, Patrick Gage; Invernizzi, Luca; Benko, Borbala; Pietraszek, Tadek; Patel, Sarvar; Boneh, Dan; Bursztein, Elie. Protecting accounts from credential stuffing with password breach alerting. 2019: 1556–1571 [2020-05-22]. ISBN 9781939133069. （原始內容存檔於2021-04-15） （英語）. 
  26. ^ Demir, Levent; Kumar, Amrit; Cunche, Mathieu; Lauradoux, Cédric. The Pitfalls of Hashing for Privacy. Communications Surveys and Tutorials, IEEE Communications Society. 2018, 20 (1): 551 [2020-05-22]. S2CID 3571244. doi:10.1109/COMST.2017.2747598. （原始內容存檔於2020-11-27） （英語）. 
取自 "https://zh.wikipedia.org/w/index.php?title=K-匿名性&oldid=72316757"