k-匿名性

k-匿名性（ケーとくめいせい）は、匿名化されたデータのもつ特性の1つである。k-匿名性の概念が最初に登場したのはテンプレート:仮リンクとテンプレート:仮リンクが1998年に発表した論文中で、「個人の特徴をフィールド構造にしたデータが与えられたとき、実用性を残しつつそのデータの個人が再特定されないという科学的な証明が与えられた公開データを作成する」という問題を解決する試みにおいてである。個人情報が含まれている公開データの情報で少なくともk-1人を区別することができないとき、公開データはk-匿名性をもつという。k-匿名性を満たす匿名データを作成するための様々な手法やプログラムが米国において特許を得ている(Patent 7,269,578)。

k-匿名化の手法

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

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

識別子	準識別子				センシティブ属性
名前	年齢	性別	居住地	宗教	病気
伊藤	29	女	静岡県浜松市	神道	ガン
黒田	24	女	愛知県豊田市	無宗教	ウイルス感染症
山本	28	女	静岡県浜松市	仏教	ガン
高橋	27	男	岐阜県各務原市	仏教	結核
加藤	24	女	愛知県名古屋市	キリスト教	心血管疾患
田中	23	男	岐阜県大垣市	仏教	結核
斎藤	19	男	愛知県春日井市	無宗教	ガン
岡田	29	男	岐阜県岐阜市	無宗教	心血管疾患
林	17	男	愛知県名古屋市	無宗教	心血管疾患
鈴木	19	男	愛知県名古屋市	仏教	ウイルス感染症

このデータには6つの属性と10人分のデータが含まれている。あるkの値に対してk-匿名性を達成するための処理は主に2つある。

1. 抑制: この処理では、ある属性の一定の値をアスタリスク「*」で置換する。その列の全てないし一部の値が「*」に置換される。下の匿名化した表においては、「名前」のすべての値と「宗教」のすべての値を「*」で置換した。
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人以上のレコードが該当する。

MeyersonとWilliamsは2004年に最適なk-匿名化はNP困難な問題であることを示したが、2005年にBayardo、Agrawalにより示されたk-最適化のようなヒューリスティックな解法はしばしば良い結果を生み出す。 概ねO(log k)の計算量であるという証明のある、k-匿名化問題を解くことができる実用的な近似アルゴリズムがKenigとTassaによって示された。

警鐘

k-匿名化はランダム性を含まないため、攻撃者は個人に対して害意のある推測が可能である。たとえば19歳の愛知県在住の鈴木が上のリストに含まれていることを知っている場合、彼の疾患がガン、心血管疾患、ウイルス感染症のいずれかであるといえる。

k-匿名化は高次元のデータの匿名化には良い方法ではない。例として、4つの時空間点があれば携帯電話の単一性(${ℰ}_4$, k-匿名性 $k=1$のとき)は95%の割合で満たされるということが示されている。

k-匿名性は不釣合な抑制やそのデータを代表するものではないものによる一般化により、データの結果を歪めることもある 。k-匿名化における抑制や一般化のアルゴリズムを改めることで、こういった歪曲を避けられる。

また、k-匿名性には以下のような再識別を可能にする欠陥が知られている。

同種攻撃

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

背景知識攻撃

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

関連項目

• テンプレート:仮リンク
• テンプレート:仮リンク
• テンプレート:仮リンク