BB-WAVE.com『仕事に使えるARCHIVES』 PowerPoint 用テンプレート　其の五

Size: px

Start display at page:

Download "BB-WAVE.com『仕事に使えるARCHIVES』 PowerPoint 用テンプレート　其の五"

のぶあきいそみ
7 years ago
Views:

1 ERATO セミナー知識発見におけるデータ匿名化とプライバシ保護佐久間淳筑波 CS/JST さきがけ

2 データ解析データ発見予測解析

3 セキュリティとプライバシ ( 通信の ) セキュリティ秘密情報秘密情報秘密情報 3

4 セキュリティとプライバシ ( 通信の ) セキュリティ秘密情報秘密情報秘密情報 ( データ ) プライバシ公開情報公開情報秘密情報秘密情報 4

5 機械学習とセキュリティプライバシの接点はどこに議論としては大きく三つに集約 Input privacy (or 匿名化) Privacy-preserving data mining (or 秘密計算) Output privacy (or 摂動差分プライバシーなど) クラウド利用(=outsourcing)を考慮すると少し事情は変わる詳細は[佐久間11] (情報処理)参照あとで少しふれます 5

6 Input Privacy 所有者秘密情報匿名化情報解析者発見予測解析攻撃者公開情報からの識別を防ぐ =Anonymization/Input privacy [Sweeney02] 6

7 Privacy preserving data mining 秘密情報所有者発見予測解析所有者秘密情報データはみせずに学習結果だけ見たい =Privacy-preserving Data Mining [ 佐久間 09] 7

8 Output privacy 所有者秘密情報発見予測解析発見知識と背景知識からの推定を防ぐ =output privacy [Dwork06] 背景知識発見知識 8

9 Agenda 暗号理論的に安全なデータマイニング入門編ラベル予測におけるプライバシ保護応用放射線疫学調査システムにおけるプライバシ保護 Set intersection 離散構造とプライバシ保護 Set intersection, k-nn, 編集距離プロトコル設計の考え方動的に変化するデータの匿名化アルゴリズムの課題(時間があれば) 入門編レコード増加型/属性増加型課題 9

10 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

11 準同型性公開鍵暗号 m Z N をメッセージ, r Z N を乱数とする (pk, sk): 公開鍵と秘密鍵のペア暗号化 : 複号化 : m0,m1, r1,r2 Z N 暗号系が ( 加法的 ) 準同系性を持つとき : 暗号文の和暗号文と平文の積 e.g. Paillier 暗号 [Damgard01] 11

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 12

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 13

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 14

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 15

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 ax+y が加減算乗算で閉じているので暗号文上で計算可能 16

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 17

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 ax+y が加減算乗算で閉じているので暗号文上で計算可能 18

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 19

20 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

21 ラベル予測 (例トピック予測) データノード文書リンクハイパーリンクラベルトピックラベル予測ノードは部分的にラベル付け未ラベルノードのノードを当てたい Webグラフ

22 ラベル予測のプライバシ (例感染予測) リンクプライバシ with H. 非当事者間のリンクは見えないラベルプライバシ 1. 当事者はリンク先ラベルが見える(弱い秘匿 e.g. 風邪) 2. 当事者もリンク先ラベルは見えない(強い秘匿, e.g., HIV) HIV陰性 HIV陽性感染 HIV陰性感染 HIV陰性この条件下でのラベル予測 HIV陽性感染接触ネットワークノード人リンク接触ラベル感染情報

23 ラベル付きグラフの行列表現接続行列ラベル行列? - ノードi,j間のリンク重みノードiのラベル

24 ラベル付きグラフのプライバシ Label-aware model (e.g. 風邪) 他人のリンク/ラベルは見えないリンク先リンク元ノードが見えるリンク先リンク元ラベルが見える? Sym private N(i) row-private

25 ラベル付きグラフのプライバシ Label-unaware model (e.g. HIV) 他人のリンク/ラベルは見えないリンク先リンク元ノードが見えるリンク先リンク元ラベルは見えない? Sym 0 private row 1 private

26 ラベル付きグラフのプライバシ Link-unaware Label-unaware model (e.g. ピアレビュー) 他人のリンク/ラベルは見えないリンク先ノードは見えるがリンク元ノードは見えない - リンク先リンク元ラベルは見えない ? row private row privat

27 ラベル付きグラフのプライバシモデル重み行列 W ラベル行列 F 弱 Label aware symm. private N(i)-row private プライバシ制約 symm. private row private Labelunaware Linkunaware Labelunaware 強 row private row private

28 k-nnによるラベル予測隣接ノードのラベルの多数決 Node 1の場合: 隣接ノードラベルは(-,+,-) - を予測とする?

29 ラベル伝播によるラベル予測隣接ノードのラベル情報を使った逐次更新[Zhu 02] ラベルは確率遷移行列更新式ノード毎に見ると:? に従って伝播ノードiが所有リンク元ノードが所有

30 ラベル付きグラフのプライバシモデル重み行列 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

31 プライバシ保護ラベル伝播? 分散ラベル伝播法プライバシ保護ラベル伝播法 (PPLP) ノードiが所有リンク元ノードが所有 Enc(+)

32 ラベル付きグラフのプライバシモデル重み行列 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

33 ラベル付きグラフのプライバシモデル重み行列 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

34 実験設定比較対象 SFE を用いたラベル伝播法 (LP/SFE) K 近傍法 (knn), ラベル伝播 (LP) プライバシ保護ラベル伝播 (PPLP) 評価項目開示ラベル数に対する予測精度少ない開示ラベル数で高い予測精度が得られればうれしい計算時間

35 データセット Romance Network Reality Mining 高校生の性交渉ネットワーク [Bearman04] ( 無向グラフ ) 感染者 :80/ 非感染者 :208 携帯電話で検知された相互近接関係 [Eagle07] ( 有向グラフ ) ラベル : ユーザーの所属 MIT:43/SLOAN:24

36 実験 : 予測精度とプライバシ保護のトレードオフ romance Reality mining K-NN, LP は予測精度と公開ラベル数がトレードオフ PPLP,LP/SFE は公開ラベル数に依存しない

37 実験実データを用いた検証 Romance 公開情報と収束に要する計算時間 PPLP プライバシ保護/現実的な計算時間を両立

38 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

39 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

40 一方向性関数 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

41 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

42 Protocol 3 [FNP04] Aliceは集合を多項式にエンコードし暗号化された多項式を送信 BobはY={y1,y2, }の各要素yについて以下を計算しAliceへ送信 Aliceの集合にyが入っていれば0になる Aliceは暗号化された各要素を複号するその値が共通要素であればその値が複号されるそうでなければ乱数が得られる 42

43 メリットデメリット N:ドメインサイズ n: 集合サイズ佐藤菊池佐久間, プライバシーを保護した放射線疫学システム, CSEC 54 (2011)より 43

44 なにかよいデータ構造 / アルゴリズムはないでしょうか? まだ単純なデータ構造 / アルゴリズムしか試されていないプライバシ保護 knn 探索プライバシ保護集合演算プライバシ保護編集距離評価ポイント暗号系の演算は時間がかかる暗号系の演算は加算乗算しかできない既存の計算環境では特に利用価値のないアルゴリズムデータ構造でも暗号系上での演算では利用価値があるかも! 44

Microsoft PowerPoint - kyoto

Microsoft PowerPoint - kyoto 研究集会代数系アルゴリズムと言語および計算理論知識の証明と暗号技術情報セキュリティ大学大学院学院有田正剛 1 はじめに暗号技術の面白さとむずかしさシステムには攻撃者が存在する条件が整ったときのベストパフォーマンスより条件が整わないときの安全性攻撃者は約束事 ( プロトコル ) には従わない表面上は従っているふり放置すると正直者が損をするそれを防ぐには知識の証明が基本手段

BB-WAVE.com『仕事に使えるARCHIVES』 PowerPoint 用テンプレート 其の五

BB-WAVE.com『仕事に使えるARCHIVES』 PowerPoint 用テンプレート　其の五