k-匿名性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/10/25 01:21 UTC 版)
k-匿名性（ケーとくめいせい）は、匿名化されたデータのもつ特性の1つである。k-匿名性の概念が最初に登場したのはラタニア・スウィーニーとPierangela Samaratiが1998年に発表した論文中で[1]、「個人の特徴をフィールド構造にしたデータが与えられたとき、実用性を残しつつそのデータの個人が再特定されないという科学的な証明が与えられた公開データを作成する」という問題を解決する試みにおいてである[2][3][4]。個人情報が含まれている公開データの情報で少なくともk-1人を区別することができないとき、公開データはk-匿名性をもつという。k-匿名性を満たす匿名データを作成するための様々な手法やプログラムが米国において特許を得ている(Patent 7,269,578)[5]。
k-匿名化の手法
k-匿名化問題において、データベースはn行m列の表形式である。それぞれの行はデータベースに収載された、ある特定の個人を表している。なお、それぞれの値が全て異なった値である必要はない。各列の値はその行の人の属性値である。「名前」「識別番号(ID)」など個人をはっきり指し示す属性を識別子と呼ぶのに対し、「年齢」「性別」「居住地」など単体では特定できないが、組み合わせることによって個人の特定が可能になる属性を「準識別子（quasi-identifier）」と呼ぶ。また、「年収」や「持病」など人に知られたくない属性を「センシティブ属性」（もしくは「要配慮属性」）と呼ぶ。
下の表は匿名化されていない日本の愛知県名古屋市にある架空の病院の患者の一覧である。
| 識別子 | 準識別子 | センシティブ属性 | |||
| 名前 | 年齢 | 性別 | 居住地 | 宗教 | 病気 |
|---|---|---|---|---|---|
| 伊藤 | 29 | 女 | 静岡県浜松市 | 神道 | ガン |
| 黒田 | 24 | 女 | 愛知県豊田市 | 無宗教 | ウイルス感染症 |
| 山本 | 28 | 女 | 静岡県浜松市 | 仏教 | ガン |
| 高橋 | 27 | 男 | 岐阜県各務原市 | 仏教 | 結核 |
| 加藤 | 24 | 女 | 愛知県名古屋市 | キリスト教 | 心血管疾患 |
| 田中 | 23 | 男 | 岐阜県大垣市 | 仏教 | 結核 |
| 斎藤 | 19 | 男 | 愛知県春日井市 | 無宗教 | ガン |
| 岡田 | 29 | 男 | 岐阜県岐阜市 | 無宗教 | 心血管疾患 |
| 林 | 17 | 男 | 愛知県名古屋市 | 無宗教 | 心血管疾患 |
| 鈴木 | 19 | 男 | 愛知県名古屋市 | 仏教 | ウイルス感染症 |
このデータには6つの属性と10人分のデータが含まれている。あるkの値に対してk-匿名性を達成するための処理は主に2つある。
- 抑制: この処理では、ある属性の一定の値をアスタリスク「*」で置換する。その列の全てないし一部の値が「*」に置換される。下の匿名化した表においては、「名前」のすべての値と「宗教」のすべての値を「*」で置換した。
- 一般化: この処理では、個々の属性値を広い範囲に置換する。たとえば、年齢の「19歳」は「10代」に、「23歳」は「20代」にといった具合である。
以下に匿名化した表を示す。
| 識別子 | 準識別子 | センシティブ属性 | |||
| 名前 | 年齢 | 性別 | 居住県 | 宗教 | 病気 |
|---|---|---|---|---|---|
| * | 20代 | 女 | 静岡県 | * | ガン |
| * | 20代 | 女 | 愛知県 | * | ウイルス感染症 |
| * | 20代 | 女 | 静岡県 | * | ガン |
| * | 20代 | 男 | 岐阜県 | * | 結核 |
| * | 20代 | 女 | 愛知県 | * | 心血管疾患 |
| * | 20代 | 男 | 岐阜県 | * | 結核 |
| * | 10代 | 男 | 愛知県 | * | ガン |
| * | 20代 | 男 | 岐阜県 | * | 心血管疾患 |
| * | 10代 | 男 | 愛知県 | * | 心血管疾患 |
| * | 10代 | 男 | 愛知県 | * | ウイルス感染症 |
同一の準識別子の組み合わせをもつ同値類は4つある。
| 識別子 | 準識別子 | センシティブ属性 | ||||
| 同値類 | 名前 | 年齢 | 性別 | 居住県 | 宗教 | 病気 |
|---|---|---|---|---|---|---|
| A | * | 20代 | 女 | 静岡県 | * | ガン |
| * | 20代 | 女 | 静岡県 | * | ガン | |
| B | * | 20代 | 女 | 愛知県 | * | ウイルス感染症 |
| * | 20代 | 女 | 愛知県 | * | 心血管疾患 | |
| C | * | 20代 | 男 | 岐阜県 | * | 結核 |
| * | 20代 | 男 | 岐阜県 | * | 結核 | |
| * | 20代 | 男 | 岐阜県 | * | 心血管疾患 | |
| D | * | 10代 | 男 | 愛知県 | * | ガン |
| * | 10代 | 男 | 愛知県 | * | 心血管疾患 | |
| * | 10代 | 男 | 愛知県 | * | ウイルス感染症 | |
このデータは「年齢」「性別」「居住県」において2−匿名性を達成している。なぜならば、これらの属性の組み合わせではどの組み合わせにおいても2人以上になるためである。どの準識別子の組み合わせでも、k-匿名性を満たすデータセットにおいてはk人以上のレコードが該当する[6]。
MeyersonとWilliamsは2004年に最適なk-匿名化はNP困難な問題であることを示したが、2005年にBayardo、Agrawalにより示されたk-最適化のようなヒューリスティックな解法はしばしば良い結果を生み出す[7][8]。 概ねO(log k)の計算量であるという証明のある、k-匿名化問題を解くことができる実用的な近似アルゴリズムがKenigとTassaによって示された[9]。
警鐘
k-匿名化はランダム性を含まないため、攻撃者は個人に対して害意のある推測が可能である。たとえば19歳の愛知県在住の鈴木が上のリストに含まれていることを知っている場合、彼の疾患がガン、心血管疾患、ウイルス感染症のいずれかであるといえる。
- k-匿名性のページへのリンク
