2017年7月13日 (木) 06:48時点における版編集 M77so (会話 \| 投稿記録) 108 回編集 en:K-anonymity( 09:42, 30 June 2017 UTC)からの翻訳		2017年7月13日 (木) 07:03時点における版編集取り消し M77so (会話 \| 投稿記録) 108 回編集 m編集の要約なし新しい編集 →
6行目: ==''k''-匿名化の手法== ''k''-匿名化問題において、[[データベース]]はn行m列の表形式である。それぞれの行は対象の中のある特定の人を表しており、ユニークである必要はない。各列の値はその行の人の属性値である。下の表は匿名化されていない[[インド]]の[[コーチ_(インド)\|コーチ]]にある架空の病院の患者の一覧である。 <center> {\| class="wikitable" 71行目: このデータは「年齢」「性別」「居住州」において2−匿名性を達成している。なぜならば、これらの属性の組み合わせではどの組み合わせにおいても2人以上になるためである。こういった攻撃者が入手可能な属性は「準識別子」と呼ぶ。どの「準識別子」の組み合わせでも、k-匿名性を満たすデータセットにおいてはk人以上のレコードが該当する<ref>{{cite web\|last1=Narayanan\|first1=Arvind\|last2=Shmatikov\|first2=Vitaly\|title=Robust De-anonymization of Large Sparse Datasets\|url=https://www.cs.utexas.edu/~shmat/shmat_oak08netflix.pdf\|accessdate=2017-07-13}}</ref>。 MeyersonとWilliamsは[[2004年]]に最適な''k''-匿名性化は[[NP困難]] な問題であることを示したが、[[2005年]]にBayardo、Agrawalにより示された''k''-最適化のような[[ヒューリスティック]]な解法はしばしば良い結果を生み出す。<ref name=Optimal>{{cite journal \| url = https://www.cs.auckland.ac.nz/research/groups/ssg/pastbib/pastpapers/bayardo05data.pdf \| author1 = Roberto J. Bayardo 97行目: \| quote = 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. }}</ref> 概ねO(log k)の[[計算量]]であるという証明のある、''k''-匿名化問題を解くことができる実用的な近似[[アルゴリズム]]がKenigとTassaによって示された。<ref>{{cite journal\|last1=Kenig\|first1=Batya\|last2=Tassa\|first2=Tamir\|title=A practical approximation algorithm for optimal k-anonymity\|journal=Data Mining and Knowledge Discovery\|date=2012\|volume=25\|pages=134–168}}</ref> == 警鐘 == ''k''-匿名化はランダム性を含まないため、攻撃者は個人に対して害意のある推測が可能である。たとえば19歳のケーララ州在住のJohnが上のリストに含まれていることを知っている場合、彼の疾患がガン、心血管疾患、ウイルス感染症のいずれかであるといえる。 K''k''-匿名化は高次元のデータの匿名化には良い方法ではない。<ref>{{cite web\|url=http://dl.acm.org/citation.cfm?id=1083696\|last1=Aggarwal\|first1=Charu C.\|title=On k-Anonymity and the Curse of Dimensionality\|accessdate=2017-07-13}}</ref>例として、4つの時空間点があれば[[携帯電話]]の単一性(<math>\mathcal{E}_4</math>, k-~~anonymity when~~匿名性 <math>k=1</math>のとき)は95%の割合で満たされるということが示されている。 <ref>{{cite journal\|last=de Montjoye\|first=Yves-Alexandre\|author2=César A. Hidalgo \|author3=Michel Verleysen \|author4=Vincent D. Blondel \|title=Unique in the Crowd: The privacy bounds of human mobility\|journal=Nature srep.\|date=March 25, 2013\|doi=10.1038/srep01376\|url=http://www.nature.com/srep/2013/130325/srep01376/full/srep01376.html}}</ref> ''k''-匿名性は不釣合な抑制やそのデータを代表するものではないものによる一般化により、データの結果を歪めることもできある。 <ref>{{cite web\|last1=Angiuli\|first1=Olivia\|author2=Joe Blitzstein \|author3=Jim Waldo \|title=How to De-Identify Your Data\|url=http://queue.acm.org/detail.cfm?id=2838930\|website=ACM Queue\|publisher=ACM\|accessdate=2017-07-13}}</ref> ''k''-匿名化における抑制や一般化のアルゴリズムを改めることで、こういった歪曲を避けられる。<ref>{{cite journal\|last1=Angiuli\|first1=Olivia\|author2=Jim Waldo\|title=Statistical Tradeoffs between Generalization and Suppression in the De-Identification of Large-Scale Data Sets\|journal=IEEE Computer Society Intl Conference on Computers, Software, and Applications\|date=June 2016}}</ref> ==関連項目==

「K-匿名性」の版間の差分