K-匿名性のソースを表示

{{DISPLAYTITLE:''k''-匿名性}}
'''k-匿名性'''（ケーとくめいせい）は、匿名化されたデータのもつ特性の1つである。''k''-匿名性の概念が最初に登場したのは{{仮リンク|ラタニア・スウィーニー|en|Latanya Sweeney}}と{{仮リンク|Pierangela Samarati|en|Pierangela Samarati}}が[[1998年]]に発表した論文中で<ref>{{Cite web|url=https://dataprivacylab.org/dataprivacy/projects/kanonymity/paper3.pdf|title=Protecting privacy when disclosing information: k-anonymity and its enforcement through generalization and suppression|last2=Sweeney|first2=Latanya|last=Samarati|first=Pierangela|date=1998|website=Harvard Data Privacy Lab|archive-url=|archive-date=|dead-url=|access-date=April 12, 2017}}</ref>、「個人の特徴をフィールド構造にしたデータが与えられたとき、実用性を残しつつそのデータの個人が再特定されないという科学的な証明が与えられた公開データを作成する」という問題を解決する試みにおいてである<ref>{{cite web|last=L. Sweeney|title=Database Security: k-anonymity|url=http://latanyasweeney.org/work/kanonymity.html|accessdate=19 January 2014}}</ref><ref>L. Sweeney. [http://dataprivacylab.org/dataprivacy/projects/kanonymity/kanonymity.pdf k-anonymity: a model for protecting privacy]. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10 (5), 2002; 557-570.</ref><ref>P. Samarati. [http://spdp.di.unimi.it/papers/tkde_k-anonymity.pdf Protecting Respondents' Identities in Microdata Release]. IEEE Transactions on Knowledge and Data Engineering archive
Volume 13 Issue 6, November 2001.</ref>。[[個人情報]]が含まれている公開データの情報で少なくともk-1人を区別することができないとき、公開データは''k''-匿名性をもつという。''k''-匿名性を満たす匿名データを作成するための様々な手法や[[プログラム (コンピュータ)|プログラム]]が[[アメリカ合衆国|米国]]において特許を得ている([https://patents.google.com/patent/US7269578 Patent 7,269,578])<ref>{{cite web|title=Systems and methods for de-identifying entries in a data source|url=http://patft.uspto.gov/netacgi/nph-Parser?Sect2=PTO1&Sect2=HITOFF&p=1&u=/netahtml/PTO/search-bool.html&r=1&f=G&l=50&d=PALL&RefSrch=yes&Query=PN/7269578|publisher=United States Patents and Trademarks Office|accessdate=19 January 2014}}</ref>。

== ''k''-匿名化の手法 ==
''k''-匿名化問題において、[[データベース]]はn行m列の表形式である。それぞれの行はデータベースに収載された、ある特定の個人を表している。なお、それぞれの値が全て異なった値である必要はない。各列の値はその行の人の属性値である。「[[名前]]」「識別番号(ID)」など個人をはっきり指し示す属性を'''[[識別子]]'''と呼ぶのに対し、「年齢」「性別」「居住地」など単体では特定できないが、組み合わせることによって個人の特定が可能になる属性を「'''[[準識別子]]'''（quasi-identifier）」と呼ぶ。また、「年収」や「持病」など人に知られたくない属性を「センシティブ属性」（もしくは「要配慮属性」）と呼ぶ。

下の表は匿名化されていない[[日本]]の[[愛知県]][[名古屋市]]にある架空の病院の患者の一覧である。

<center>
{| class="wikitable"
|-
|識別子
|colspan="4" | 準識別子
|センシティブ属性
|-
! '''名前''' !! '''年齢''' !!  '''性別''' !!'''居住地''' !! '''宗教''' !! '''病気'''
|-
|  伊藤  || 29 ||  女 || [[静岡県]][[浜松市]] || [[神道]]   || [[悪性腫瘍|ガン]]    
|-
|  黒田  || 24  || 女 || [[愛知県]][[豊田市]]   || [[無宗教]]   || ウイルス感染症
|-
|  山本  || 28 || 女 || 静岡県浜松市   || [[仏教]]  || ガン
|-
| 高橋   || 27  || 男|| [[岐阜県]][[各務原市]]   || 仏教   || 結核
|-
|  加藤  || 24  || 女 || 愛知県名古屋市   || [[キリスト教]]   || [[心血管疾患]]
|-
|  田中  || 23 || 男 || 岐阜県[[大垣市]]   || 仏教   || 結核
|-
|  斎藤  || 19  || 男 || 愛知県[[春日井市]]   || 無宗教   || ガン
|-
|   岡田  ||  29 || 男 || 岐阜県[[岐阜市]]   || 無宗教  || 心血管疾患
|-
|  林  || 17  || 男 || 愛知県名古屋市   || 無宗教   || 心血管疾患
|-
|  鈴木  || 19  || 男 || 愛知県名古屋市   || 仏教   || ウイルス感染症
|}
</center>
このデータには6つの属性と10人分のデータが含まれている。ある''k''の値に対して''k''-匿名性を達成するための処理は主に2つある。
# '''抑制''': この処理では、ある属性の一定の値をアスタリスク「*」で置換する。その列の全てないし一部の値が「*」に置換される。下の匿名化した表においては、「名前」のすべての値と「宗教」のすべての値を「*」で置換した。
# '''一般化''': この処理では、個々の属性値を広い範囲に置換する。たとえば、年齢の「19歳」は「10代」に、「23歳」は「20代」にといった具合である。
以下に匿名化した表を示す。
<center>
{| class="wikitable"
|-
|識別子
|colspan="4" | 準識別子
|センシティブ属性
|-
! '''名前''' !! '''年齢''' !!  '''性別''' !!'''居住県''' !! '''宗教''' !! '''病気'''
|-
|  *  || 20代 ||  女 || 静岡県 || *   || ガン    
|-
|  *  || 20代 || 女 || 愛知県   || *   || ウイルス感染症
|-
|  *  || 20代 || 女 || 静岡県   || * || ガン
|-
| *   || 20代  || 男|| 岐阜県   || *  || 結核
|-
|  * || 20代 || 女 || 愛知県   || *   || 心血管疾患
|-
|  *  || 20代 || 男 || 岐阜県   || *   || 結核
|-
|  *  || 10代  || 男 || 愛知県   || *   || ガン
|-
|   *  ||  20代 || 男 || 岐阜県   || *  || 心血管疾患
|-
|  *  || 10代  || 男 || 愛知県   || *   || 心血管疾患
|-
|  *  || 10代 || 男 || 愛知県   || *   || ウイルス感染症
|}
</center>
同一の準識別子の組み合わせをもつ同値類は4つある。
<center>
{| class="wikitable"
|-
|
|識別子
|colspan="4" | 準識別子
|センシティブ属性
|-
! '''同値類''' !! '''名前''' !! '''年齢''' !!  '''性別''' !!'''居住県''' !! '''宗教''' !! '''病気'''
|-
|rowspan="2"| A||  *  || 20代 ||  女 || 静岡県 || *   || ガン  
|-
|  *  || 20代 || 女 || 静岡県   || * || ガン
|-
|rowspan="2" | B ||  *  || 20代 || 女 || 愛知県   || *   || ウイルス感染症
|-
|  * || 20代 || 女 || 愛知県   || *   || 心血管疾患
|-
|rowspan="3" | C||*   || 20代  || 男|| 岐阜県   || *  || 結核
|-
| *  || 20代 || 男 || 岐阜県   || *   || 結核
|-
|   *  ||  20代 || 男 || 岐阜県   || *  || 心血管疾患
|-
|rowspan="3" | D ||  *  || 10代  || 男 || 愛知県   || *   || ガン
|-
|  *  || 10代  || 男 || 愛知県   || *   || 心血管疾患
|-
|  *  || 10代 || 男 || 愛知県   || *   || ウイルス感染症
|}
</center>
このデータは「年齢」「性別」「居住県」において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
| author2 =  Rakesh Agrawal
| title = Data Privacy through Optimal ''k''-anonymization
| journal = ICDE '05 Proceedings of the 21st International Conference on Data Engineering
| pages = 217–28
| isbn = 0-7695-2285-8
| doi = 10.1109/ICDE.2005.42
| issn = 1084-4627
| year = 2005
| quote = 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.
}}</ref><ref>{{cite journal
| url = http://www.stanford.edu/~rrwill/kanon-pods04.pdf
| author1 = Adam Meyerson
| author2 = Ryan Williams
| title = On the Complexity of Optimal ''K''-Anonymity
| journal = PODS '04 Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
| publisher = ACM
| pages = 223–8
| place = New York, NY
| isbn = 158113858X
| doi =10.1145/1055558.1055591
| year = 2004
| 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歳の愛知県在住の鈴木が上のリストに含まれていることを知っている場合、彼の疾患がガン、心血管疾患、ウイルス感染症のいずれかであるといえる。

''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-匿名性 <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''-匿名性には以下のような再識別を可能にする欠陥が知られている<ref>{{Cite journal|first1=Ashwin|last1=Machanavajjhala|author2=Johannes Gehrke|author3=Daniel Kifer|year=2007|title=l-Diversity: Privacy Beyond k-Anonymity|url=http://www.cs.uml.edu/~ge/pdf/papers_685-2-2/ldiversity-icde06.pdf}}</ref>。

=== 同種攻撃 ===
同値類内のすべてのレコードの機密属性が同じ時に成立する攻撃である。攻撃者がある人がリストに含まれていることを知っており、その人の同値類を正しく特定できた場合、攻撃者は機密属性を入手できる。たとえば静岡県在住の伊藤が上のリストに含まれていることを知っている場合、同値類Aであることがわかるため、彼女の病気がガンであることがわかる。

=== 背景知識攻撃 ===
攻撃者がなんらかの背景知識を持っているときに成立する攻撃である。攻撃者がある人がリストに含まれていることを知っており、その人の同値類を正しく特定でき、背景知識によって機密属性を絞り込めた時、攻撃者は機密属性を入手できる。たとえば岐阜県在住の高橋が上のリストに含まれていることを知っている場合、同値類Cであることがわかる。また彼が明らかに結核ではないと攻撃者が知っている場合、彼の病気が心血管疾患であることがわかる。

== 脚注 ==
{{脚注ヘルプ}}
=== 出典 ===
{{Reflist}}

== 関連項目 ==
* {{仮リンク|t-近似性|en|t-closeness}}
* {{仮リンク|l-多様性|en|l-diversity}}
* {{仮リンク|差分プライバシー|en|Differential privacy}}

{{DEFAULTSORT:けえとくめいせい}}
[[Category:匿名性]]