ERATO セミナー 2011.8.30 知識発見におけるデータ匿名化とプライバシ保護 佐久間淳筑波 CS/JST さきがけ
データ解析 データ 発見 予測 解析
セキュリティとプライバシ ( 通信の ) セキュリティ 秘密情報 秘密情報 秘密情報 3
セキュリティとプライバシ ( 通信の ) セキュリティ 秘密情報 秘密情報 秘密情報 ( データ ) プライバシ 公開情報 公開情報 秘密情報 秘密情報 4
機械学習とセキュリティ プライバシの接点はどこに 議論としては大きく三つに集約 Input privacy (or 匿名化) Privacy-preserving data mining (or 秘密計算) Output privacy (or 摂動 差分プライバシーなど) クラウド利用(=outsourcing)を考慮すると少し事情は 変わる 詳細は[佐久間11] (情報処理)参照 あとで少しふれます 5
Input Privacy 所有者 秘密情報 匿名化情報 解析者 発見 予測 解析 攻撃者 公開情報からの識別を防ぐ =Anonymization/Input privacy [Sweeney02] 6
Privacy preserving data mining 秘密情報所有者 発見 予測 解析 所有者 秘密情報 データはみせずに学習結果だけ見たい =Privacy-preserving Data Mining [ 佐久間 09] 7
Output privacy 所有者 秘密情報 発見 予測 解析 発見知識と背景知識からの推定を防ぐ =output privacy [Dwork06] 背景知識 発見知識 8
Agenda 暗号理論的に安全なデータマイニング 入門編 ラベル予測におけるプライバシ保護 応用 放射線疫学調査システムにおけるプライバシ保護 Set intersection 離散構造とプライバシ保護 Set intersection, k-nn, 編集距離 プロトコル設計の考え方 動的に変化するデータの匿名化アルゴリズムの課題(時間があれば) 入門編 レコード増加型/属性増加型 課題 9
Secure function evaluation データ A データ B Ｂ社 Ａ社 A, Bをそれぞれ明かさずにf(A B) のみ計算! 秘匿関数評価 (Secure function evaluation) AはデータAをBに開示したくない BもデータBをAに開示したくない ただし結合されたデータA Bについてf(A B)を知りたい fがデータマイニングの場合 いわゆるPPDM 10
準同型性公開鍵暗号 m Z N をメッセージ, r Z N を乱数とする (pk, sk): 公開鍵と秘密鍵のペア 暗号化 : 複号化 : m0,m1, r1,r2 Z N 暗号系が ( 加法的 ) 準同系性を持つとき : 暗号文の和 暗号文と平文の積 e.g. Paillier 暗号 [Damgard01] 11
Example: private computation of ax+y Alice has x Bob has y, a Problem: compute random shares of ax+y = r A +r B mod N 12
Example: private computation of ax+y Alice has x Bob has y, a Problem: compute random shares of ax+y = r A +r B mod N Key pair 13
Example: private computation of ax+y Alice has x Bob has y, a Problem: compute random shares of ax+y = r A +r B mod N Key pair Public key 14
Example: private computation of ax+y Alice has x Bob has y, a Problem: compute random shares of ax+y = r A +r B mod N Key pair Public key Generate a random number 15
Example: private computation of ax+y Alice has x Bob has y, a Problem: compute random shares of ax+y = r A +r B mod N Key pair Public key Generate a random number ax+y が加減算 乗算で閉じているので暗号文上で計算可能 16
Example: private computation of ax+y Alice has x Bob has y, a Problem: compute random shares of ax+y = r A +r B mod N Key pair Public key Generate a random number 17
Example: private computation of ax+y Alice has x Bob has y, a Problem: compute random shares of ax+y = r A +r B mod N Key pair Public key Generate a random number ax+y が加減算 乗算で閉じているので暗号文上で計算可能 18
Example: private computation of ax+y Alice has x Bob has y, a Problem: compute random shares of ax+y = r A +r B mod N Key pair Public key Generate a random number 19
Example: private computation of ax+y Alice has x Bob has y, a Problem: compute random shares of ax+y = r A +r B mod N Key pair Public key Generate a random number 20
ラベル予測 (例 トピック予測) データ ノード 文書 リンク ハイパーリンク ラベル トピック ラベル予測 ノードは部分的にラベル付け 未ラベルノードのノードを当てたい Webグラフ
ラベル予測のプライバシ (例 感染予測) リンクプライバシ with H. Arai@tsukuba 非当事者間のリンクは見えない ラベルプライバシ 1. 当事者はリンク先ラベルが見える(弱い 秘匿 e.g. 風邪) 2. 当事者もリンク先ラベルは見えない(強 い秘匿, e.g., HIV) HIV陰性 HIV陽性 感染 HIV陰性 感染 HIV陰性 この条件下でのラベル予測 HIV陽性 感染 接触ネットワーク ノード 人 リンク 接触 ラベル 感染情報
ラベル付きグラフの行列表現 接続行列 ラベル行列? - ノードi,j間のリンク重み ノードiのラベル 1 5-2 4 + + 3 + - 0.5 0.5 1 2 3 4 5 1 0 0 1 0 0 1 2 1 0 0 1 0 2 0 1 3 0 4 0 1 0 0 0 3 1 0 0 1 0 1 4 1 0 5 1 0 0 0 0 5 0 1
ラベル付きグラフのプライバシ Label-aware model (e.g. 風邪) 他人のリンク/ラベルは見えない リンク先 リンク元ノードが見える リンク先 リンク元ラベルが見える? - 1 5-1 1 0 2 1 2 4 + + 3 3 0 4 0 5 1 2 3 4 5 + - 0 1 0 0 1 0.5 0.5 2 0 1 0 0 1 0 Sym 3 1 0 1 0 private 0 0 4 1 0 0 1 0 1N(i) row-private 5 0 1 0 0 0 0
ラベル付きグラフのプライバシ Label-unaware model (e.g. HIV) 他人のリンク/ラベルは見えない リンク先 リンク元ノードが見える リンク先 リンク元ラベルは見えない? - 1 5-1 1 0 2 1 2 4 + + 3 3 0 4 0 5 1 2 3 4 5 0 1 0 0 0 0 1 0 1 Sym 0 private 0 0 0 1 0 1 0 0 0 0 1 + - 0.5 0.5 2 0 1 row 1 private 0 3 4 1 0 0 1 5
ラベル付きグラフのプライバシ Link-unaware Label-unaware model (e.g. ピアレ ビュー) 他人のリンク/ラベルは見えない リンク先ノードは見えるがリンク元ノードは見えない - リンク先 リンク元ラベルは見えない 1 2 3 4 5? 1 5 1 0 0 1 0 0-2 1 2 + 3 0 0 1 0 row private 3 0 1 0 0 0 4 + 4 0 0 1 0 1 5 1 0 0 0 0 1 + - 0.5 0.5 2 0 1 row privat 3 1 0 4 1 0 5 0 1
ラベル付きグラフのプライバシモデル 重み行列 W ラベル行列 F 弱 Label aware symm. private N(i)-row private プライバシ制約 symm. private row private Labelunaware Linkunaware Labelunaware 強 row private row private
k-nnによるラベル予測 隣接ノードのラベルの多数決 Node 1の場合: 隣接ノードラベルは(-,+,-) - を予測とする? - 1 5-2 4 + + 3 -
ラベル伝播によるラベル予測 隣接ノードのラベル情報を使った逐次更新[Zhu 02] ラベルは確率遷移行列 更新式 ノード毎に見ると:? - 1 5 に従って伝播 - - + ノードiが所有 2 4 + 3 + リンク元ノードが所有
ラベル付きグラフのプライバシモデル 重み行列 W ラベル行列 F Label aware symm. private N(i)-row private symm. private row private knn/ ラベル伝播 OK NG NG Labelunaware Linkunaware Labelunaware row private row private
プライバシ保護ラベル伝播? 分散ラベル伝播法 プライバシ保護ラベル伝播法 (PPLP) ノードiが所有 リンク元ノードが所有 1 5 - Enc(+) 2 4 + + 3
ラベル付きグラフのプライバシモデル 重み行列 W ラベル行列 F Label aware symm. private N(i)-row private symm. private row private knn/ ラベル伝播 OK NG NG PPLP OK OK NG Labelunaware Linkunaware Labelunaware row private row private
ラベル付きグラフのプライバシモデル 重み行列 W ラベル行列 F Label aware symm. private N(i)-row private symm. private row private knn/ ラベル伝播 OK NG NG PPLP OK OK NG PPLP+onion routing OK OK OK Labelunaware Linkunaware Labelunaware row private row private
実験設定 比較対象 SFE を用いたラベル伝播法 (LP/SFE) K 近傍法 (knn), ラベル伝播 (LP) プライバシ保護ラベル伝播 (PPLP) 評価項目 開示ラベル数に対する予測精度 少ない開示ラベル数で高い予測精度が得られればうれしい 計算時間
データセット Romance Network Reality Mining 高校生の性交渉ネットワーク [Bearman04] ( 無向グラフ ) 感染者 :80/ 非感染者 :208 携帯電話で検知された相互近接関係 [Eagle07] ( 有向グラフ ) ラベル : ユーザーの所属 MIT:43/SLOAN:24
実験 : 予測精度とプライバシ保護のトレードオフ romance Reality mining K-NN, LP は予測精度と公開ラベル数がトレードオフ PPLP,LP/SFE は公開ラベル数に依存しない
実験 実データを用いた検証 Romance 公開情報と収束に要する計算時間 PPLP プライバシ保護/現実的な計算時間を両立
Set intersection Input of Alice X={x1,x2, } Input of Bob Y={y1,y2, } Problem Find X Y without releasing X and Y Find X Y without releasing X and Y 38
Protocol 1 scalar product protocol [VC02] インジケータ変数で集合を binary vector に変換 例 : レンジが {0,1,,9} で X={2,3,6,8}, Y={2,4,6,9} の場合 x=(0,1,1,0,0,1,0,1,0,0), y=(0,1,0,1,0,1,0,0,1,0) x T y= X Y に注意 プロトコル A pk B : ランダム 39
一方向性関数 H(x)=y x,yのレンジをr={0,1,,p-1}とする xがr上で一様に分布するならyもr上で一様に分布 Xからyを得るのは簡単 yからxを得るのは困難 可換な一方向性関数 H(G(x))=G(H(x)) たとえば sを知らない人にはh(x)からxを得ることはできない しかし可換 (Pohling-Hellman暗号) 40
Protocol 2 [AES03] A H(x 1 ),H(x 2 ), H(x m ) シャッフルシャッフル B G(H(x 1 )),G(H(x 2 )), G(H(x m )) G(y 1 ),G(y 2 ), G(y m ) H(G(y 1 )),H(G(y 2 )), H(G(y m )) を計算 H(G(y 1 )),H(G(y 2 )), H(G(y m )) G(H(x 1 )),G(H(x 2 )), G(H(x m )) 比較してカウント 41
Protocol 3 [FNP04] Aliceは集合を多項式にエンコードし暗号化された多項式を送信 BobはY={y1,y2, }の各要素yについて以下を計算しAliceへ送信 Aliceの集合にyが入っていれば0になる Aliceは暗号化された各要素を複号する その値が共通要素であれば その値が複号される そうでなければ乱数が得られる 42
メリット デメリット N:ドメインサイズ n: 集合サイズ 佐藤 菊池 佐久間, プライバシーを保護した放射線疫学システム, CSEC 54 (2011)より 43
なにかよいデータ構造 / アルゴリズムはないでしょうか? まだ単純なデータ構造 / アルゴリズムしか試されていないプライバシ保護 knn 探索プライバシ保護集合演算プライバシ保護編集距離評価ポイント 暗号系の演算は時間がかかる 暗号系の演算は加算 乗算しかできない 既存の計算環境では特に利用価値のないアルゴリズム データ構造でも暗号系上での演算では利用価値があるかも! 44