ℓ-多様性 (ℓ-diversity) —— k-匿名性だけでは守りきれないもの

第3回の記事「k-匿名化とは何か—— 個人を「群衆」に紛れさせるプライバシー保護技術」では、匿名化の基本的な考え方である k-匿名性 (k-anonymity)※ [1] を紹介しました。「同じ属性の組み合わせを持つ人が、少なくともk人はいるようにする」という考え方です。これによって、公開されたデータの1レコードに対し、特定の個人を「あなたですね」と言い当てることは難しくなります。

しかし、実は k-匿名性を満たしていても、個人の秘密が漏れてしまうことがあります。そこで提案されたのが、今回紹介する ℓ-多様性 (ℓ-diversity)※ です。

まずは「なぜ k-匿名性だけでは不十分なのか」から見ていきましょう。

匿名化を考えるとき、データの列 (属性) は次のように分類されます。

k-匿名性は、準識別子※の組み合わせが同じレコードが必ずk個以上存在することを要件とする匿名データの安全性指標です。そして、k-匿名性を実現するためには、準識別子に分類される属性について、年齢を「30代」にまとめる、郵便番号の下位桁を伏せる、などの一般化※処理を行います。準識別子の値が同じ行のまとまりを等価クラス※と呼びます。

図1の表を見てください。準識別子は「年齢」と「郵便番号」、機密属性は「病名」です。同じ準識別子の組み合わせを持つ等価クラスが2つあり、それぞれの等価クラスのレコードを同じ色にしています。それぞれの等価クラスが3つのレコードを含んでいるので、この表は k-匿名性（k=3）を満たしています。

図1. k-匿名性（k=3）を満足するテーブルの例

ここで、あなたが「隣人のAさんは 35 歳で、郵便番号は100-0012だ」と知っていたとしましょう。Aさんがこのデータに含まれていることが分かれば、Aさんは上の3行のレコードのどれかですが、どのレコードかまでは分かりません。この意味でk-匿名性は機能していて、レコードの再識別※を防いでくれています。

ところが、上の3行のレコードはすべて病名が「胃炎」です。つまり、どのレコードかは分からなくても、Aさんが胃炎であることは 100% 分かってしまう のです（図2）。

図2. 同質性攻撃 (homogeneity attack)による属性推定

これを 同質性攻撃 (homogeneity attack) ※と呼びます。個人の「識別」は防げても、機密属性の「開示」は防げていない、というのが k-匿名性の弱点です。

もう 1 つ、背景知識攻撃 (background knowledge attack) ※という問題もあります。たとえば下の等価クラスにBさんがいると分かっていて、かつ「Bさんはスポーツが得意で骨折もしていない」と攻撃者が知っていれば、一番下の病名が「骨折」のレコードは選択肢から除けます。さらに「スポーツが得意なので気管支炎も考えにくい」と推論することで、候補が上から4番目のレコードの1つに絞り込まれ、病名が「胃炎」と分かります。

このように個人の機密属性の値が推測されることを属性推定※と呼びます。k-匿名性は匿名データの各レコードが個人と対応付けられるレコードの再識別を防いでくれますが、個人の機密属性の値が開示されてしまう属性推定の問題には対処してくれません。

2006年にコーネル大学のMachanavajjhalaら4人の研究者はこうしたk-匿名性における属性推定の問題を指摘し、その解決策としてℓ-多様性の概念を提案しました。[2] Samarati と Sweeney が k-匿名性を提案してから約8年。k-匿名性だけでは機密属性が守りきれないこと自体は早くから認識されていましたが、それを「多様性」という明快な原理として定式化し、扱いやすい安全性指標にまで落とし込むのには長い時間が必要でした。その結果、生まれた ℓ-多様性の考え方はシンプルで、k-匿名性の自然な拡張になっています。その要件は以下のように定式化されます。

それぞれの等価クラスの中に、機密属性の値が「よく代表される」形で少なくとも ℓ 種類含まれているようにする。

先ほどの例で言えば、「30代・100-00**」のグループの病名がすべて胃炎ではなく、少なくとも 2 種類、3 種類…… とばらついているようにする、ということです。そうすれば、Aさんがそのグループに属することが分かっても、病名は ℓ 通りの候補に散らばり、確実には言い当てられません。

先ほどの図1の表をℓ-多様性を満たすように作り直すと、図3の右側の表になります (病名がグループ内で 3種類ずつになるよう等価クラスのグループ分けを変えています)。

図3. ℓ-匿名性（=3）を満足する表への変換

これで、Aさんがどのグループにいるか分かっても、病名の候補は3つに散らばります。ただし、「年齢」、「属性」にはさらなる一般化処理が必要なことにも注意してください。年齢の区分は10歳単位から「30-40代」という20歳単位になり、郵便番号も下3桁を伏せる必要が生じました。このように、ℓ-多様性の条件を満足するためには追加の一般化処理が必要になり、匿名データの有用性の損失という代償を伴います。

「種類ある」と一口に言っても、実は厳密さに幅があります。代表的な定義を3つ紹介します。

(1) distinct ℓ-多様性

もっとも素朴な定義で、等価クラスの中に機密属性の異なる値が ℓ 種類以上あることを要求します。表2で説明したℓ-匿名性（ℓ=3）の例は、distinct ℓ-多様性の定義を使っていました。

ただしこの定義には穴があります。たとえば 10 行の等価クラスで、病名が「胃炎 8 件、気管支炎1件、骨折1件」だったとします。値は3種類あるので distinct ℓ-多様性（ℓ=3)を満たしますが、実際には8割が胃炎です。攻撃者から見れば「Aさんは胃炎だろう」と高い確率で推測できてしまいます。

(2) エントロピー ℓ–多様性

そこで、値の「散らばり具合」を情報理論のエントロピー※で測る定義が使われます。等価クラス内の機密属性の分布のエントロピーが log ℓ 以上であることを要求します。

エントロピーは、値が均等にばらついているほど大きくなり、1つの値に偏るほど小さくなる指標です。そしてℓの値が大きいほど、しきい値であるlog ℓ も大きくなります。先ほどの「胃炎8件」のような偏った分布は、値が3種類あってもエントロピーが小さいため、この定義では弾かれます。

(3) 再帰的 (c, ℓ)-多様性

「もっとも多く出現する値が、出現頻度の低い値たちに比べて多くなりすぎないこと」を、パラメータ c を使って直接的に条件づける定義です。正確には、出現回数を多い順に並べたとき、もっとも多く出現する値の出現回数が、 ℓ 番目以降の値の出現回数の合計の c 倍より小さい、という条件です。エントロピーより扱いやすい場面で使われます。

いずれも狙いは同じで、「等価クラスの中で、特定の値に賭ければ高い確率で当たってしまう」状況を防ぐことです。

ℓ-多様性は k-匿名性の弱点を補いますが、万能ではありません。よく知られた2つの弱点を紹介します。[3]

偏り攻撃 (skewness attack)

ある検査の陽性者が、全体ではわずか1% だとします。ある等価クラスで陽性・陰性が 50%ずつになっていれば、値は2種類あるので ℓ-多様性（ℓ=2）は満たされます。しかし、そのグループに属すると分かった人の陽性確率は、世間一般の1% から一気に 50% に跳ね上がります。「多様である」ことと「情報が漏れていない」ことは別物なのです。

類似性攻撃 (similarity attack)

等価クラスの病名が「胃炎・胃潰瘍・胃がん」の 3種類だったとします。値としては 3 種類なので ℓ-多様性（ℓ=3）を満たしますが、どれも胃の病気です。攻撃者は「Aさんは胃を悪くしている」と確実に知ることができます。年収が「200 万円・250 万円・300 万円」と並んでいる場合も同様で、「Aさんは低所得層だ」と分かってしまいます。

ℓ-多様性は値を「異なる記号」としてしか見ておらず、値どうしの意味的な近さを考慮していないのです。

実務上の難しさ

理論的な限界とは別に、実務では次のような課題もあります。

• 機密属性の値の種類がそもそも少ないと、ℓ-多様性を満たせない (例: 「陽性・陰性」の2値しかなければ ℓ は最大 2)
• 多様性を確保するために準識別子をより粗く丸める必要があり、データの有用性が下がる
• 機密属性が複数ある場合、それぞれについて多様性を確保するのは難しい

匿名化の歴史は、「ある攻撃への対策が提案される → 新たな攻撃が見つかる → さらに強い指標が提案される」という繰り返しでもあります。ℓ-多様性は、その中で「識別を防ぐだけでは足りない」という重要な気づきを与えてくれた指標です。

k-匿名性が守ろうとしたのは「誰か」を言い当てられないこと、すなわちレコードの再識別でした。しかし本記事で見たように、たとえ個人を1行に絞り込めなくても、等価クラスの中身が偏っていれば「何か」——つまり機密属性——は漏れてしまいます (同質性攻撃・背景知識攻撃)。ℓ-多様性は、この属性推定という別の脅威に正面から向き合い、「等価クラスの中で機密属性の値が十分に多様であること」を要求した点に大きな意義があります。

もっとも、ℓ-多様性は値を「異なる記号」として数えるだけで、値の分布の偏りや、値どうしの意味的な近さまでは考慮しません。そのため偏り攻撃や類似性攻撃には対処しきれない、という限界も残りました。「多様であること」と「情報が漏れていないこと」は必ずしも一致しない——この気づきは、機密属性の「値の種類」ではなく「分布そのもの」に注目する t-近似性 (t-closeness) [3] という、さらに進んだ指標へとつながっていきます。

そして忘れてはならないのは、プライバシー保護指標に唯一の万能解はない、ということです。どの指標を選ぶべきかは、扱うデータの性質、機密属性の種類、そして「どんな攻撃者を想定するか」によって変わります。加えて、安全性を高めようとすれば一般化は粗くなり、データの有用性は下がっていきます。このプライバシーと有用性のトレードオフをどこで折り合わせるか——それを見極めることこそが、匿名化を実務に活かすうえで避けて通れない課題なのです。

• ℓ-多様性 (ℓ-diversity) ・・・k-匿名化されたデータで、同じ等価クラスの中に機密属性の値が少なくとも l 種類含まれるようにするプライバシー保護の指標です。
• 同質性攻撃 (homogeneity attack) ・・・k-匿名化されたデータで、同じ等価クラス内の機密属性の値がすべて（またはほぼ）同一だった場合に、個人を1行に特定できなくても機密属性の値だけは判明してしまう攻撃です。
• 背景知識攻撃 (background knowledge attack) ・・・攻撃者が対象者について事前に持っている別の知識（背景知識）と、k-匿名化されたデータを組み合わせることで、等価クラス内に複数種類の機密属性の値があっても、候補を絞り込んで機密属性を特定してしまう攻撃です。
• 属性推定・・・匿名化されたデータから、特定の個人を1行に絞り込めなくても、その人の機密属性（病名・収入など隠したい情報）の値を言い当ててしまうことです。
• エントロピー・・・値がどれだけバラついているか（予測しにくいか）」を表す指標です。もともとは情報理論という分野で生まれた考え方で、データの集合の値が均等に散らばっているほど大きく、特定の値に偏っているほど小さくなります。

• k-匿名性（第2回）
• 準識別子（第2回）
• 一般化（第3回）
• 等価クラス（第3回）
• 再識別（第1回）

1. Pierangela Samarati and Latanya Sweeney, “Protecting Privacy When Disclosing Information: k-Anonymity and Its Enforcement through Generalization and Suppression,” Technical Report SRI-CSL-98-04, SRI International Computer Science Laboratory, 1998.
2. Ashwin Machanavajjhala, Johannes Gehrke, D. Kifer and Muthuramakrishnan Venkitasubramaniam, “L-diversity: privacy beyond k-anonymity,” 22nd International Conference on Data Engineering (ICDE’06), Atlanta, GA, USA, 2006, doi: 10.1109/ICDE.2006.1.
3. Ninghui Li, Tiancheng Li and Suresh Venkatasubramanian, “t-Closeness: Privacy Beyond k-Anonymity and -Diversity,” 2007 IEEE 23rd International Conference on Data Engineering, Istanbul, Turkey, 2007, pp. 106-115, doi: 10.1109/ICDE.2007.367856.