k-匿名性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/09/24 08:38 UTC 版)
k-匿名性は、匿名化されたデータのもつ特性の1つである。k-匿名性の概念が最初に登場したのはラタニア・スウィーニーとPierangela Samaratiが1998年に発表した論文中で[1]、「個人の特徴をフィールド構造にしたデータが与えられたとき、実用性を残しつつそのデータの個人が再特定されないという科学的な証明が与えられた公開データを作成する」という問題を解決する試みにおいてである[2][3][4]。個人情報が含まれている公開データの情報で少なくともk-1人を区別することができないとき、公開データはk-匿名性をもつという。k-匿名性を満たす匿名データを作成するための様々な手法やプログラムが米国において特許を得ている(Patent 7,269,578)[5]。
- ^ Samarati, Pierangela (1998年). “Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression”. Harvard Data Privacy Lab. 2017年4月12日閲覧。
- ^ L. Sweeney. “Database Security: k-anonymity”. 2014年1月19日閲覧。
- ^ L. Sweeney. k-anonymity: a model for protecting privacy. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10 (5), 2002; 557-570.
- ^ P. Samarati. Protecting Respondents' Identities in Microdata Release. IEEE Transactions on Knowledge and Data Engineering archive Volume 13 Issue 6, November 2001.
- ^ “Systems and methods for de-identifying entries in a data source”. United States Patents and Trademarks Office. 2014年1月19日閲覧。
- ^ “Robust De-anonymization of Large Sparse Datasets”. 2017年7月13日閲覧。
- ^ Roberto J. Bayardo; Rakesh Agrawal (2005). “Data Privacy through Optimal k-anonymization”. ICDE '05 Proceedings of the 21st International Conference on Data Engineering: 217–28. doi:10.1109/ICDE.2005.42. ISBN 0-7695-2285-8. ISSN 1084-4627. "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."
- ^ Adam Meyerson; Ryan Williams (2004). “On the Complexity of Optimal K-Anonymity”. PODS '04 Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (New York, NY: ACM): 223–8. doi:10.1145/1055558.1055591. ISBN 158113858X. "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."
- ^ Kenig, Batya; Tassa, Tamir (2012). “A practical approximation algorithm for optimal k-anonymity”. Data Mining and Knowledge Discovery 25: 134–168.
- ^ “On k-Anonymity and the Curse of Dimensionality”. 2017年7月13日閲覧。
- ^ de Montjoye, Yves-Alexandre; César A. Hidalgo; Michel Verleysen; Vincent D. Blondel (March 25, 2013). “Unique in the Crowd: The privacy bounds of human mobility”. Nature srep.. doi:10.1038/srep01376.
- ^ “How to De-Identify Your Data”. ACM Queue. ACM. 2017年7月13日閲覧。
- ^ Angiuli, Olivia; Jim Waldo (June 2016). “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.
- ^ Machanavajjhala, Ashwin; Johannes Gehrke; Daniel Kifer (2007). l-Diversity: Privacy Beyond k-Anonymity.
[続きの解説]
「k-匿名性」の続きの解説一覧
- 1 k-匿名性とは
- 2 k-匿名性の概要
- 3 関連項目
- k-匿名性のページへのリンク
