k-匿名性

k-匿名性とは、特定の匿名化されたデータが持つ特性である。k-匿名性という用語、1998年に発表された論文でピエランジェラ・サマラティとラタニヤ・スウィーニーによって初めて導入されたが ^[1]、その概念は1986年のトーレ・ダレニウスの論文にまで遡る。^[2]

k匿名性は、「個人固有のフィールド構造化データが与えられた場合、データが実用的に有用である限り、データの対象である個人が再識別されないことを科学的に保証したデータリリースを作成する」という問題を解決するための試みです。 ^[3]^[4]^[5]リリースに含まれる各個人の情報が、リリースに情報が記載されている少なくとも個人と区別できない場合、データのリリースはk匿名性プロパティを持つと言われます。k匿名性によって提供される保証は数学的ではなく、願望的です。 $k-1$

方法け-匿名化

k匿名性を使用してデータセットを処理し、プライバシー保護付きで公開できるようにするには、データサイエンティストがまずデータセットを調べ、各属性 (列) が識別子(識別可能)、非識別子(識別不可)、または準識別子(ある程度識別可能) であるかどうかを判断する必要があります。名前などの識別子は抑制され、非識別値はそのまま残り、準識別子は、準識別子のすべての異なる組み合わせが少なくともk個のレコードを指定するように処理する必要があります。

以下のサンプルテーブルは、架空の病院の患者記録で構成される架空の非匿名データベースを示しています。名前列は識別子、年齢、性別、居住地、宗教は準識別子、病気は個人を特定しない機密値です。では、身長と体重はどうでしょうか。これらも個人を特定しない機密値でしょうか、それとも準識別子でしょうか。

このデータには 6 つの属性と 10 のレコードがあります。k の値に応じて k 匿名性を実現する一般的な方法は 2つあります。

抑制。この方法では、属性の特定の値がアスタリスク「*」に置き換えられます。列のすべてまたは一部の値が「*」に置き換えられる場合があります。以下の匿名化された表では、名前属性のすべての値と宗教属性のすべての値が「*」に置き換えられています。
一般化。この方法では、属性の個々の値がより広いカテゴリに置き換えられます。たとえば、属性Ageの値「19」は「≤ 20」に置き換えられ、値「23」は「20 < Age ≤ 30」などに置き換えられます。

次の表は匿名化されたデータベースを示しています。

このデータは、年齢、性別、居住地の属性に関して2匿名性を持っています。これは、表のどの行にこれらの属性の任意の組み合わせが見つかったとしても、それらの属性を正確に持つ行が少なくとも2つ存在するためです。攻撃者が利用できる属性は、準識別子と呼ばれます。各準識別子タプルは、 k匿名性を持つデータセットの少なくともkレコードに出現します。^[6]

批判け-匿名

次の例は、 k匿名性の欠陥を示しています。つまり、個人を特定できないとされる変数にリンクできる他のデータレコードが存在する可能性があります。たとえば、攻撃者が研究の一環としてバイタルサインを測定していた人物からログを入手し、キショールが 4 月 30 日に病院にいて、身長が 180 cm であることを知ったとします。この情報を使用して、「匿名化された」データベース (インターネットで公開されている可能性があります) にリンクし、キショールが心臓関連の病気を患っていることを知ることができます。キショールが 4 月 30 日に病院を訪れたことを知っている攻撃者は、キショールの身長が 180 cm、体重がおよそ 80 ～ 82 kg、カルナタカ州出身であることを知るだけで、このことを推測できる可能性があります。

この問題の根源は、 k匿名性の核心的な問題です。つまり、属性が識別子なのか、準識別子なのか、それとも非識別的な機密値なのかを数学的に明確に判断する方法はありません。実際、すべての値は、人口内での普及度や攻撃者が持つ可能性のある補助データに応じて、潜在的に識別可能です。差分プライバシーなどの他のプライバシーメカニズムでは、この問題は発生しません。

k-匿名性は身元の暴露に対しては保護しますが、特定の属性の開示に対しては保護しません。これは、攻撃者が背景知識を持っている場合に問題になります。さらに、機密領域に多様性がない場合は、個人情報が漏洩する可能性があります。このようなシナリオでは、ℓ-多様性を選択すると、より強力なプライバシー保護を提供できる可能性があります。[1]

マイヤーソンとウィリアムズ（2004）は、最適なk匿名性はNP困難な問題であるが、ベヤルドとアグラワル（2005）が示したk最適化などのヒューリスティックな方法は、多くの場合効果的な結果をもたらすことを実証した。^[7]^[8]ケニグとタッサは、k匿名化問題を近似保証付きで解くことを可能にする実用的な近似アルゴリズムを提示した。 ^[9] $O(\log k)$

攻撃

k匿名性は、データセットを公開前に匿名化するための比較的簡単に実装できるアプローチですが、多くの攻撃を受けやすいです。攻撃者が背景知識を利用できる場合、このような攻撃はさらに効果的になります。このような攻撃には次のものが含まれます。

同種性攻撃: この攻撃は、 k個のレコードセット内の機密値のすべての値が同一である場合を利用します。このような場合、データがk匿名化されているとしても、 k 個のレコードセットの機密値は正確に予測される可能性があります。
背景知識攻撃: この攻撃は、1 つ以上の準識別子属性と機密属性との関連性を利用して、機密属性の可能な値のセットを絞り込みます。たとえば、Machanavajjhala、Kifer、Gehrke、および Venkitasubramaniam (2007) は、日本人患者における心臓発作の発生率が低いことを知ることで、患者の病気の機密属性の値の範囲を絞り込むことができることを示しました。
ダウンコーディング攻撃：2022年にアロニ・コーエンによって導入されたこの攻撃は、匿名アルゴリズムが属性を別々のレコードに集約する方法を利用します。集約は決定論的であるため、元のデータイメージをリバースエンジニアリングすることができ、多くの場合、保護されるべき元のデータを明らかにすることができます。この攻撃には背景知識は必要ありませんが、それがあると強化されます。^[10]

k匿名化にはランダム化が一切含まれないため、攻撃者は個人に危害を加える可能性のあるデータセットについて、信頼性が高く明確な推論を行うことができます。たとえば、上記のデータベースにケララ州の 19 歳のジョンが含まれていることがわかっている場合、彼が癌、心臓関連の病気、またはウイルス感染のいずれかを患っていると確実に言えます。

K匿名化は高次元データセットを匿名化するための良い方法ではない。^[11]

また、 k匿名性は、代表的でない特性を持つデータポイントを不均衡に抑制し一般化すると、データセットの結果を歪める可能性があることも示されています。 ^{[12]ただし、データセットを}k匿名化するために使用される抑制および一般化アルゴリズムは、そのような歪曲効果を持たないように変更できます。^[13]

参照

参考文献

^ Samarati, Pierangela; Sweeney, Latanya (1998). 「情報開示時のプライバシー保護: k-匿名性と一般化および抑制によるその施行」(PDF)。ハーバードデータプライバシーラボ。 2017年4月12日閲覧。
^ Tore Dalenius、「干し草の山から針を探す」、Journal of Official Statistics、第2巻、第3号、1986年、326〜336ページ。
^ Samarati, Pierangela (2001 年 11 月)。「マイクロデータの公開における回答者の個人情報の保護」( PDF)。IEEE Transactions on Knowledge and Data Engineering。13 ( 6): 1010–1027。doi : 10.1109 /69.971193。S2CID 561716。
^ Sweeney, Latanya. 「データベースセキュリティ: k-匿名性」。 2014年1月19日閲覧。
^ Sweeney, Latanya (2002). 「k-匿名性: プライバシー保護モデル」(PDF) . International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems . 10 (5): 557–570. doi :10.1142/S0218488502001648. S2CID 361794.
^ Narayanan, Arvind; Shmatikov, Vitaly. 「大規模スパースデータセットの堅牢な匿名化」(PDF)。
^ Roberto J. Bayardo、 Rakesh Agrawal (2005)。「最適な k-匿名化によるデータプライバシー」。第 21 回国際データエンジニアリング会議 (ICDE'05) ( PDF)。pp. 217–228。doi :10.1109/ICDE.2005.42。ISBN 978-0-7695-2285-2. ISSN 1084-4627. S2CID 17044848.データの匿名化は、研究目的でのデータ公開の要求と個人のプライバシーの要求を調和させます。この論文では、k匿名化と呼ばれる強力な匿名化手順の最適化アルゴリズムを提案し、評価します。k匿名化されたデータセットには、各レコードが少なくともk − 1 個の他のレコードと区別できないという特性があります。最適化された k 匿名性の単純な制約でさえNP困難であり、計算上の大きな課題につながります。私たちは、問題の組み合わせを制御する可能性のある匿名化の空間を探索する新しいアプローチを提示し、並べ替えなどのコストのかかる操作への依存を減らすデータ管理戦略を開発します。実際の国勢調査データでの実験を通じて、結果として得られたアルゴリズムが、2 つの代表的なコスト指標と広範囲の k の下で最適なk匿名化を見つけることができることを示します。また、入力データまたは入力パラメータによって、妥当な時間で最適なソリューションを見つけられない状況でも、このアルゴリズムによって優れた匿名化を実現できることも示しています。最後に、このアルゴリズムを使用して、さまざまなコーディング手法と問題のバリエーションが匿名化の品質とパフォーマンスに与える影響を調査します。私たちの知る限り、これは問題の一般的なモデルの下で、非自明なデータセットの最適なk匿名化を実証した最初の結果です。
^ Adam Meyerson、Ryan Williams (2004)。「最適な K 匿名性の複雑さについて」。データベースシステムの原理に関する第 23 回 ACM SIGMOD-SIGACT-SIGART シンポジウムの議事録( PDF)。ニューヨーク、NY: ACM。pp. 223–228。doi : 10.1145 /1055558.1055591。ISBN 978-1581138580. S2CID 6798963。k匿名化の手法は、データのプライバシーとデータの整合性の両方を確保しながら、公開情報を公開する代替方法として文献で提案されています。関係の最適なk匿名化の 2 つの一般的なバージョンが NP 困難であることを証明します。これには、関係から削除するエントリの最小数を選択することに相当する抑制バージョンが含まれます。また、 kが定数である場合に、データベースのサイズに依存しない近似比を実現する最適なk匿名性の多項式時間アルゴリズムも提示します。特に、 big -Oの定数が 4 以下である場合、これはO ( k log k ) 近似です。ただし、アルゴリズムの実行時間はkに対して指数関数的です。もう少し巧妙なアルゴリズムではこの条件がなくなりますが、これはO ( k log m ) 近似です。ここで、m は関係の次数です。このアルゴリズムは実際には非常に高速になる可能性があります。
^ Kenig, Batya; Tassa, Tamir (2012). 「最適な k匿名性のための実用的な近似アルゴリズム」.データマイニングと知識発見. 25 : 134–168. doi :10.1007/s10618-011-0235-9. S2CID 14158546.
^ 匿名化の防御に対する攻撃、Aloni Cohen、USENIX Security 2022、優秀論文賞受賞者。https://www.usenix.org/conference/usenixsecurity22/presentation/cohen
^ Aggarwal , Charu C. (2005). 「k匿名性と次元の呪いについて」 VLDB '05 – 第 31 回国際大規模データベース会議議事録。ノルウェー、トロンハイム。CiteSeerX 10.1.1.60.3155。ISBN 1-59593-154-6。
^ Angiuli, Olivia、Joe Blitzstein、Jim Waldo。「データを匿名化する方法」。ACM Queue。ACM。
^ アンジュリ、オリビア、ジム・ウォルド（2016 年 6 月）。「大規模データセットの匿名化における一般化と抑制の統計的トレードオフ」。2016 IEEE第 40 回年次コンピュータソフトウェアおよびアプリケーション会議（COMPSAC）。pp. 589–593。doi :10.1109/ COMPSAC.2016.198。ISBN 978-1-4673-8845-0. S2CID 17716908。

[1] Samarati, Pierangela; Sweeney, Latanya (1998). 「情報開示時のプライバシー保護: k-匿名性と一般化および抑制によるその施行」(PDF)。ハーバードデータプライバシーラボ。 2017年4月12日閲覧。

[2] Tore Dalenius、「干し草の山から針を探す」、Journal of Official Statistics、第2巻、第3号、1986年、326〜336ページ。

[3] Samarati, Pierangela (2001 年 11 月)。「マイクロデータの公開における回答者の個人情報の保護」( PDF)。IEEE Transactions on Knowledge and Data Engineering。13 ( 6): 1010–1027。doi : 10.1109 /69.971193。S2CID 561716。

[4] Sweeney, Latanya. 「データベースセキュリティ: k-匿名性」。 2014年1月19日閲覧。

[5] Sweeney, Latanya (2002). 「k-匿名性: プライバシー保護モデル」(PDF) . International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems . 10 (5): 557–570. doi :10.1142/S0218488502001648. S2CID 361794.

[6] Narayanan, Arvind; Shmatikov, Vitaly. 「大規模スパースデータセットの堅牢な匿名化」(PDF)。

[Optimal-7] ^ Roberto J. Bayardo、 Rakesh Agrawal (2005)。「最適な k-匿名化によるデータプライバシー」。第 21 回国際データエンジニアリング会議 (ICDE'05) ( PDF)。pp. 217–228。doi :10.1109/ICDE.2005.42。ISBN 978-0-7695-2285-2. ISSN 1084-4627. S2CID 17044848.データの匿名化は、研究目的でのデータ公開の要求と個人のプライバシーの要求を調和させます。この論文では、k匿名化と呼ばれる強力な匿名化手順の最適化アルゴリズムを提案し、評価します。k匿名化されたデータセットには、各レコードが少なくともk − 1 個の他のレコードと区別できないという特性があります。最適化された k 匿名性の単純な制約でさえNP困難であり、計算上の大きな課題につながります。私たちは、問題の組み合わせを制御する可能性のある匿名化の空間を探索する新しいアプローチを提示し、並べ替えなどのコストのかかる操作への依存を減らすデータ管理戦略を開発します。実際の国勢調査データでの実験を通じて、結果として得られたアルゴリズムが、2 つの代表的なコスト指標と広範囲の k の下で最適なk匿名化を見つけることができることを示します。また、入力データまたは入力パラメータによって、妥当な時間で最適なソリューションを見つけられない状況でも、このアルゴリズムによって優れた匿名化を実現できることも示しています。最後に、このアルゴリズムを使用して、さまざまなコーディング手法と問題のバリエーションが匿名化の品質とパフォーマンスに与える影響を調査します。私たちの知る限り、これは問題の一般的なモデルの下で、非自明なデータセットの最適なk匿名化を実証した最初の結果です。

[8] Adam Meyerson、Ryan Williams (2004)。「最適な K 匿名性の複雑さについて」。データベースシステムの原理に関する第 23 回 ACM SIGMOD-SIGACT-SIGART シンポジウムの議事録( PDF)。ニューヨーク、NY: ACM。pp. 223–228。doi : 10.1145 /1055558.1055591。ISBN 978-1581138580. S2CID 6798963。k匿名化の手法は、データのプライバシーとデータの整合性の両方を確保しながら、公開情報を公開する代替方法として文献で提案されています。関係の最適なk匿名化の 2 つの一般的なバージョンが NP 困難であることを証明します。これには、関係から削除するエントリの最小数を選択することに相当する抑制バージョンが含まれます。また、 kが定数である場合に、データベースのサイズに依存しない近似比を実現する最適なk匿名性の多項式時間アルゴリズムも提示します。特に、 big -Oの定数が 4 以下である場合、これはO ( k log k ) 近似です。ただし、アルゴリズムの実行時間はkに対して指数関数的です。もう少し巧妙なアルゴリズムではこの条件がなくなりますが、これはO ( k log m ) 近似です。ここで、m は関係の次数です。このアルゴリズムは実際には非常に高速になる可能性があります。

[9] ^ Kenig, Batya; Tassa, Tamir (2012). 「最適な k匿名性のための実用的な近似アルゴリズム」.データマイニングと知識発見. 25 : 134–168. doi :10.1007/s10618-011-0235-9. S2CID 14158546.

[10] 匿名化の防御に対する攻撃、Aloni Cohen、USENIX Security 2022、優秀論文賞受賞者。https://www.usenix.org/conference/usenixsecurity22/presentation/cohen

[11] ^ Aggarwal , Charu C. (2005). 「k匿名性と次元の呪いについて」 VLDB '05 – 第 31 回国際大規模データベース会議議事録。ノルウェー、トロンハイム。CiteSeerX 10.1.1.60.3155。ISBN 1-59593-154-6。

[12] Angiuli, Olivia、Joe Blitzstein、Jim Waldo。「データを匿名化する方法」。ACM Queue。ACM。

[13] アンジュリ、オリビア、ジム・ウォルド（2016 年 6 月）。「大規模データセットの匿名化における一般化と抑制の統計的トレードオフ」。2016 IEEE第 40 回年次コンピュータソフトウェアおよびアプリケーション会議（COMPSAC）。pp. 589–593。doi :10.1109/ COMPSAC.2016.198。ISBN 978-1-4673-8845-0. S2CID 17716908。