====================================== PPDM: プライバシー保護データマイニング ====================================== 課題: プライバシー指標の確立 ============================ * 保護に関する妥当な指標による保証と広い認知 * 保護と有用性のトレードオフに対する平衡点の探索 PPDMの具体的手法 ================ * セキュア関数計算 * k-匿名法 * 再構築法 セキュア関数計算 ---------------- Pros ^^^^ * 通常のマイニングと等しい精度 * 暗号学に基づく非常に高いプライバシー保護 Cons ^^^^ * 計算効率は良くない k-匿名法 -------- Pros ^^^^ * プライバシー保護指標であるk-匿名性に基づいたデータ保護処理 Cons ^^^^ * マイニング時の有用性を保ちながらk-匿名性を満たすことが困難 * データ管理者に無防備なデータが渡ってしまう 再構築法 -------- Pros ^^^^ * セキュア関数計算よりも計算効率が高い * データ管理者や分析者に対してもプライバシー保護が可能 Cons ^^^^ * プライバシー保護指標の研究が遅れている 再構築法に対する指標の提案 ========================== Pk-匿名性 --------- データの持ち主を 1/k 以上の確信度に絞り込めない Pros ^^^^ * k-匿名性の確率的指標への拡張であり、互換性が高い。 * k-匿名性同様に直感的である。 * 再構築法に適用可能である。 関連研究 ======== 識別に対する耐性の指標 ---------------------- DB等の中のデータが誰のものか判ってしまうこと k-匿名性 ^^^^^^^^ LooM ^^^^ 属性推定に対する耐性の指標 -------------------------- 誰かの属性データが判ってしまうこと l-多様性によるプライバシー ^^^^^^^^^^^^^^^^^^^^^^^^^^ (s, ρ_1, ρ_2) Privacy Breach ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Differential Privacy ^^^^^^^^^^^^^^^^^^^^ k-匿名性 ======== テーブル形式のDBの保護処理において、 "保護処理後テーブルの中に、どのデータ行に関しても同じデータ行が自身を含めk個以上存在する" = "どのデータも持ち主をk人以下に絞り込めない" ことを保証する指標。 k-匿名性に基いて、準識別子からデータの持ち主をk人以下に絞り込めぬよう、 準識別子データの抽象化や削除を行うことで、プライバシー保護を実現する。 属性やその組み合わせの分類 -------------------------- 識別子 ^^^^^^ 単独でデータの持ち主を個人に特定できる属性 例: 会員ID 準識別子(quasi-identifier) ^^^^^^^^^^^^^^^^^^^^^^^^^^ 比較的容易にアクセスできて、しかも組合せによりデータの持ち主を個人まで特定することができる属性 例: 名前, 郵便番号, 年齢, 性別 その他の属性 ^^^^^^^^^^^^ 再構築法 ======== 撹乱と再構築 撹乱 ---- 各情報提供者は自身のデータに意図的にランダム性を付加し、このことにより個々のデータの情報量は減少する。 * 非可逆操作。撹乱後のデータから本来のデータは復元できない。 撹乱の手法 ^^^^^^^^^^ * 加法によるノイズ付加 * ランダム置換 再構築 ------ 逆行列の計算やベイズ推定等、撹乱の逆にあたる操作を行い、統計値のみを得る。 なぜこのようなことが可能なのか？ ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 撹乱がなされたテーブルで個々のデータの情報量は低下していても、 統計量としては撹乱アルゴリズム事の期待される値に収束するため。 再構築法の傾向 ^^^^^^^^^^^^^^ 情報量の減少が大きいような撹乱であればあるほどプライバシー保護性は上がり、 マイニング精度は低下する。 Pk-匿名化の定義 =============== 準備 ---- テーブル ^^^^^^^^ データ提供者から提供されたデータの集まり レコード ^^^^^^^^ テーブル上で行として表現される、一人のデータ提供者からのデータのまとまり 属性 ^^^^ 各レコードを構成する値に対応する、いくつかの予め定められた項目 テーブル保護系 ^^^^^^^^^^^^^^ 秘密のテーブル ************** 保護すべきテーブル 公開テーブル ************ データ処理後のテーブル データ保護処理 ************** 攻撃者 ****** * 公開テーブル中のレコードの個人識別が目的 * 公開テーブルとデータ保護処理アルゴリズムを閲覧可能 * 秘密のテーブルは閲覧不可 * 秘密のテーブルに関する知識を持つ可能性有 テーブル保護系の形式的定義 -------------------------- 秘密のテーブル ^^^^^^^^^^^^^^ .. 秘密のテーブルTauは、テーブルのレコードとしての有限集合Rの関数である。 この関数は、alpha が集合Aに属している/元である/要素であるという条件のもと、 属性値の集合V_aの総乗であることを導く。 .. math:: :nowrap: \begin{eqnarray} \tau : {\cal R} \longrightarrow \prod_{\alpha \in {\cal A}} {\cal V} _\alpha \end{eqnarray} * Rは有限集合 * Rの要素はテーブルのレコード（データの持ち主の集合）を表す。 * Aは属性の集合 * V_alpha は対応する属性値の集合 以降 .. math:: :nowrap: \begin{eqnarray} {\cal V} := \prod_{\alpha \in {\cal A}} {\cal V} _\alpha \end{eqnarray} 公開テーブル ^^^^^^^^^^^^ .. 秘密のテーブルTau'は、テーブルのレコードとしての有限集合R'の関数である。 この関数は、alpha' が集合A'の元であるという条件のもと、 属性値の集合V'_a'の総乗であることを導く。 .. math:: :nowrap: \begin{eqnarray} \tau^{\prime} : {\cal R}^{\prime} \longrightarrow \prod_{\alpha^{\prime} \in {\cal A^{\prime}}} {\cal V^{\prime}} _{\alpha^{\prime}} \end{eqnarray} * R', A', V'_alpha' は、R, A, V_alpha と一致しているとは限らない。 以降 .. math:: :nowrap: \begin{eqnarray} {\cal V^{\prime}} := \prod_{\alpha^{\prime} \in {\cal A^{\prime}}} {\cal V^{\prime}} _{\alpha^{\prime}} \end{eqnarray} その他の前提条件 ^^^^^^^^^^^^^^^^ .. piはtauのレコード順がtau'では入れ替わることを示す関数。識別の定義のために必要。 秘密のテーブルと公開テーブルでレコード位置が決定的に決まっている場合、識別は自明であり、意味を持たなくなるため。 deltaはデータ保護処理関数。RがVを導出するということは、RがV'を導出するということを導出する。 すなわち、ある秘密テーブルの秘密レコードRから秘密の属性値の集合Vが導き出されるならば、 ある秘密テーブルの秘密レコードRからは公開の属性値の集合V'も導き出される。 deltaは秘密テーブルtauの関数であり、公開テーブルtau'と関数piとの合成写像である。 すなわち、2つの写像 pi : R -> R', tau' : R' -> \prod_{\alpha^{\prime} \in {\cal A^{\prime}}} {\cal V^{\prime}} _{\alpha^{\prime}} が与えられているとき、 R の任意の元 alpha には pi による像 pi(alpha) が対応し、 pi(alpha) は R' の元であるので、 pi(alpha) には tau' による像 tau'(pi(alpha)) が対応し、 これは \prod_{\alpha^{\prime} \in {\cal A^{\prime}}} {\cal V^{\prime}} _{\alpha^{\prime}} の元である。 従って、R の任意の元alpha には \prod_{\alpha^{\prime} \in {\cal A^{\prime}}} {\cal V^{\prime}} _{\alpha^{\prime}} の1つの元 tau'(pi(alpha)) が対応することとなり、 R から \prod_{\alpha^{\prime} \in {\cal A^{\prime}}} {\cal V^{\prime}} _{\alpha^{\prime}} への写像が与えられたことになる。 .. math:: :nowrap: \begin{eqnarray} \pi & : & {\cal R} \longrightarrow {\cal R^{\prime}} \\ \delta & : & ({\cal R} \longrightarrow {\cal V}) \longrightarrow ({\cal R} \longrightarrow {\cal V^{\prime}}) \\ \delta(\tau) & = & \tau^{\prime} \circ \pi \end{eqnarray} * それぞれ tau, tau', pi, delta に対応する確率変数を TAU, TAU', PI, DELTA と書き、 * そのうち TAU と PI 及び DELTA は互いに独立とする。 攻撃者 ^^^^^^ .. math:: :nowrap: \begin{eqnarray} {f}_{\cal T} : ({\cal R} \longrightarrow {\cal V}) \longrightarrow \mathbb{R} \end{eqnarray} * {f}_{\cal T} は T の確率分布 テーブル保護系 ^^^^^^^^^^^^^^ .. math:: :nowrap: \begin{eqnarray} {\cal P} := ({\cal R}, {\cal V}, {\cal R^{\prime}}, {\cal V^{\prime}}, \Pi, \Delta) \end{eqnarray} k-匿名性の形式的定義 -------------------- 準識別子に関するデータのみを抽出した公開テーブルを tau' とする。 自然数 k に対し tau' が以下を満たすとき、tau' は k-匿名性を満たすという。 :: 任意の v' \in V' に対し、 tau'(r') = v' を満たす r' が k 個以上存在する .. * 秘密のテーブルのレコードを全て k 倍に複製したテーブル * Pi のような置換が介在しない場合 は、定義には沿うのにk-匿名性の目的を達成しない。 * | R | = | R' | * Pi は一様ランダム置換