データ解析におけるプライバシ保護 筑波大学 コンピュータサイエンス専攻 佐久間 淳 IBM TRL seminar

2 Agenda  データ解析とプライバシ保護: 各種アプローチ紹介, サービスの観点から  第三者機関の利用  匿名化アプローチ  秘匿関数計算の利用  ランダム化アプローチ  暗号理論的アプローチ  匿名化アプローチ  K-匿名化, L-多様性  暗号理論的アプローチ  秘匿関数計算, 準同型性公開鍵暗号  実例: 決定木学習, リンク解析  将来の方向性

サービスと個人情報 3 交通機関: 移動履歴 GPS: 移動履歴 RFID:品物の種類・所在 来歴(トレーサビリティ) 電子メール: 送受信履歴, アドレス帳 携帯電話:発着信履歴, メール送受信履歴, 電話帳, 病院:カルテ (疾病暦, 治療暦) 健康管理:バイタル情報 (体重, 血圧, 体脂肪率) 銀行:口座情報 カード会社:決済情報 証券会社:資産情報 保険会社:保険情報 薬局:投薬暦

4 Scenario 1: 伝染病発生源の特定 カルテ フライト ログ  疫病発生  病院は発生源を地理的に特定したい  発症患者の移動地点のクラスタリング  カルテとフライトログの統合は困難  個人情報保護  法的規制  個人情報を保護しつつ伝染病発生源を特定できないか？ 個人 航空会社 病院

Scenario 2: 破綻予測  破綻予測  企業は複数の銀行に口座をもち, 取引をしている  銀行は取引の履歴から企業の破綻確率を予測したい  取引履歴の統合は困難  機密保持  法的規制  取引履歴を統合せずに、破綻確率のみを予測できないか？ 5 取引履歴 企業 銀行A 銀行B

6 オンラインサービスにおける個人情報の活用 ユーザー ……  推薦アルゴリズム  個人個人の購入履歴に基づく推定  オンライン書店  各個人が購入した書籍をデータベースに保存  “この本を買った人はこんな本も買っています”  オンラインミュージックショップ  各個人が購入した音楽をデータベースに保存  “この音楽を買った人はこんな音楽も買っています” オンライン書店 オンラインミュージックショップ

7 オンラインサービスにおける複数の個人情報源の活用 ユーザー ……  “この本を買った人はこんな音楽も買っています” は可能か？  書店とミュージックショップでの顧客名簿の統合が必要  各顧客の購入商品の開示が必要  サーバに囲い込まれた個人情報の連携は困難  個人情報保護  ユーザの信用が得られるか オンライン書店 オンラインミュージック

サービス提供者の視点 8 交通機関: 移動履歴 GPS: 移動履歴 RFID:品物の種類・所在 来歴(トレーサビリティ) 電子メール: 送受信履歴, アドレス帳 携帯電話:発着信履歴, メール送受信履歴, 電話帳, 病院:カルテ (疾病暦, 治療暦) 健康管理:バイタル情報 (体重, 血圧, 体脂肪率) 銀行:口座情報 カード会社:決済情報 証券会社:資産情報 保険会社:保険情報 薬局:投薬暦 サービス提供者同士の連携は 進んでいない

サービスのユーザーの視点 9 ユーザー同士の連携も 進んでいない

プライバシ保護データマイニング  プライバシ保護データマイニング (Privacy-preserving data mining: PPDM)  A社/Aliceは彼女のデータベースAをB社/Bobに開示したくない  B社/Bobは彼のデータベースBをA社/Aliceに開示したくない  ただし結合されたデータベースA∪Bについてデータマイニングや統計処理を実行 し、その結果のみを知りたい 10 A A B B × マイニング結果のみ開示! データベース Alice Bob × Ａ社 Ｂ社

個人情報の蓄積・活用形態 11 Local管理PPDMServer公開 情報の流通 各個人が保持 セキュリティプロトコ ルやランダム化を利用 サーバが 全て保持し公開 プライバシ保護 保障あり 保障なし 知識獲得の効用 低い (知識発見不可) 高い (知識発見可能) 例1. 人間関係 携帯電話の通話暦 ここを狙ったサービ スを作りたい アクセスフリーのSNS (mixi等) 例2. 位置情報GPSActive Badge (RFID)

プライバシ保護データマイニング：第三者機関の利用  第三者機関の利用  信頼できる第三者にデータを委託  第三者がデータマイニングを実行し、計算結果を返す  これがいつでも実行可能ならば苦労はない  もうすこし緩やかな条件でPPDMを実行できないか?  第三者機関を前提としない  通常のネットワーク環境 (e.g., TCP/IP) 12 A A B B × データベース Alice Bob Trent 信頼できる第三者機関による データマイニングの実行

プライバシ保護データマイニング：匿名化アプローチ  データの効用を失わないように各レコードの識別性を低めて公表  k-anonymity[Sweeney02]  l-diversity[Machanavajjhala06]  Differential privacy[Dwork06] 13 A A B B × データベース Alice Bob Trent 信頼できる第三者機関による 匿名化を行い公表 匿名化 データベース 一般に公表

プライバシ保護データマイニング：秘匿関数計算の利用  秘匿関数計算 [Yao86]他  Alice, Bobが持つ秘密入力に対し、  その入力を明かさずに、特定の関数f を多項式時間で実行  Alice, Bobはfの評価結果を取得  関数fをデータマインニングと捉えれば PPDMが実行できる  残念ながら, 入力サイズが大きく, 評価対象の 関数が複雑な場合、Yaoは遅い  データマイニングの入力はたいてい大きい 14 A A B B データベース Alice Bob 秘匿関数計算による 関数fの評価 Elapsed exec time (sec) in LAN Elapsed exec time (sec) in WAN Bit-and operation Billionaires (comparison of two 32bit integers ) Key database search (search an item from 16 items with 6bit key) Median (find median form 10 16bit integers) Malkhi, D. et al, Fairplay - a secure two-party computation system, Proc. of the 13th USENIX Security Symposium, 287—302, 2004

プライバシ保護データマイニング：ランダム化アプローチ  ランダム化アプローチ [Agrawal et al. SIGMOD2000] 他  オリジナルデータに乱数でノイズを加える  統計的な性質は保持しつつ、オリジナルデータの推定を困難にする  ランダム化されたデータにデータマイニング・統計処理を実行  データマイニング結果からノイズの影響を統計的推定により取り除く 15 A A B B × データベース Alice Bob A’ 乱数によるノイズ B’ データマイニング 乱数によるノイズ

プライバシ保護データマイニング：暗号アプローチ  暗号アプローチ [Lindel et al. CRYPTO2000]他  オリジナルデータを準同系性公開鍵により暗号化  暗号化されたデータ同士の加算や乗算が可能  暗号化されたデータ上でのデータマイニングを実行  マイニング結果を復号 16 A A B B × データベース Alice Bob A A 暗号化 B B 暗号化されたデータに対する データマイニング 暗号化

各種アプローチの比較  帯に短し襷に長し  データマイニングコミュニティではランダム化アプローチと暗号アプローチが主流  セキュリティコミュニティでは秘匿関数計算アプローチが主流  統計コミュニティでは匿名化アプローチが主流? 17 アプローチ結果の正確さ計算コストAuthorityの 必要性 汎用性 (適用可能 な処理に対する) プライバシ保護 第三者機関厳密に正確小さい必要高い第三者機関次第 匿名化匿名化のレベ ルによる 小さい必要高い匿名化法に準ずる 秘匿関数計算厳密に正確極めて大きい不要高い厳密に保障 ランダム化近似的小さい不要限定的統計的に保障 暗号厳密に正確大きい不要限定的厳密に保障 ■good ■medium ■bad

複数の個人情報源の連携によるサービス例 18 交通機関: 移動履歴 GPS: 移動履歴 RFID:品物の種類 電子メール: 送受信履歴, アドレス帳 携帯電話:発着信履歴, メール送受信履歴, 電話帳, 病院:カルテ (疾病暦, 治療暦) 健康管理:バイタル情報 (体重, 血圧, 体脂肪率) 銀行:口座情報 カード会社:決済情報 証券会社:資産情報 保険会社:保険情報 薬局:投薬暦 製造場所の トレース これを食べている 人の平均体重は Xkgです こんな病気の人 はこんな薬を 使っています 伝染病発生源推定： この病気にかかった 人はこんな電車に 乗っています こんな健康状態の 人はこんな保険を 使っています 製造会社の リスク推定 これを持ってい る人の平均年収 はX万円です

匿名化アプローチ 19

k-匿名化  識別子: 名前, social security number 等  これらは通常レコードから除去される(担註：de-identification)  疑似識別子(pseudo-identifiers): 年齢, 性別, 郵便番号等  これらは識別子ではないが, 疑似識別子を組み合わせることによって個人の識別可 能性が高まってしまう  k-匿名化の定義  データ開示において, 全ての疑似識別子の値の組み合わせに適合するレコードが， テーブル中に少なくともk 個存在しなければならない 20

データ例 21 住基ネット番 号 名前住所年齢病院名疾病薬 0A99934筑波太郎茨城県32A病院腰痛XXX 1B92372統計花子東京都46B医院鼻炎YYY 3C88892匿名幸京都府42Cクリニッ ク 水虫ZZZ ………………… 属性 レコード 数値属性 カテゴリカル 属性 直接識別子 一意性あり 間接識別子 一意性なし 疑似識別子 Sensitiveな情報 年齢属性における値

k-匿名化の具体例 22 住基ネット番 号 名前住所年齢病院名疾病薬 0A99934筑波太郎関東[30-39]A病院腰痛XXX 1B92372統計花子関東[30-39]A病院鼻炎YYY 3C88892匿名幸関東[30-39]B病院腰痛ZZZ …… 直接識別子間接識別子 疑似識別子 Sensitiveな情報 3-匿名化 削除 公表

l-多様性  k-匿名化はシンプルだが，敵対者が背景知識を持つ場合にさまざまな攻撃法がありえ る  Homogenity attack: k レコードのグループにおいて，すべてのsensitive な属性 値が同じであった場合，たとえk-匿名化されていたとしても，そのグループの sensitive な属性の値は推測可能である  ex. 三丁目の田中さんがk 人いたとしても, k 人全員が腎臓病であったとした ら，三丁目の田中さんにとってはsensitve な属性が保護されたことにはなら ない  k-匿名化はレコードの識別を妨げることができるが，sensitive な属性値の推測を妨 げることはできない  定義： 非sensitive 属性のタプルがq*であるような集合をq*-block とよぶ。q*- block にℓ 種類のsensitive な属性値が含まれるなら, q*-block はℓ-多様であると 呼ぶ。テーブルのすべてのq* ブロックがℓ-多様なら、テーブルはℓ-多様である。 23

L-多様性の具体例 24 住基ネット番 号 名前住所年齢病院名疾病薬 0A99934筑波太郎三丁目32A病院腰痛XXX 1B92372統計花子三丁目32A病院腰痛XXX 3C88892匿名幸三丁目32Cクリニッ ク 鼻炎ZZZ …… 直接識別子間接識別子 疑似識別子 Sensitiveな情報 2-多様 q*-block

暗号理論的アプローチ 25

分散計算における秘密保護  M B : Aliceが受信した全メッセージ 26 Alice Private input x A Bob Private input x B { Messages: M B Output y A Output y B MBMB

分散計算における秘密保護  M B : Aliceが受信した全メッセージ  M B ’: Aliceの入力とプロトコルの出力のみが与えられたシミュレータが生成したメ ッセージ 27 Alice Private input x A Bob Private input x B Simulator of Bob input x A, y A, y B { Messages: M B Simulated messages: M’ B Output y A Output y B MBMB

分散計算における秘密保護  M B : Aliceが受信した全メッセージ  M B ’: Aliceの入力とプロトコルの出力のみが与えられたシミュレータが生成したメ ッセージ  プライバシ保護  もしM B と M B ’が区別できなければ, プロトコルはBobの余分な情報を漏らさ ない 28 Alice Private input x A Bob Private input x B Simulator of Bob input x A, y A, y B { Messages: M B Simulated messages: M’ B Indistinguishable? Output x A Output x B MBMB

PPDMに利用される要素技術  秘密分散 (secret sharing)  秘匿関数評価 (secure function evaluation)  準同型性航海鍵暗号 (homomorphic public-key cryptography)  紛失送信 (oblivious transfer)  紛失多項式評価 (oblivious polynomial evaluation)  ゼロ知識証明 (zero knowledge proof), etc… 29

 秘匿関数評価(including Yao’s protocol)  関数:  任意のfについて,秘匿関数評価は の互いの出力以外の情報をもらさ ない秘匿評価が可能  様々なバージョン (二者間プロトコル, 多者間プロトコル, 半数未満の不正者を許すプロトコル, etc)  秘匿関数評価はどのようにして動作するか? (直感的に)  各パーティーの入力をランダムな情報に分割して分配  関数fをand-gateとor-gateで構成される回路に変換  情報を分割したまま各And/or-gateを評価(garbled circuit)  各出力を持ち寄り、最終的な出力を復元  秘匿関数評価の利用例  Private comparison: x A > x B or not? 秘匿関数評価 30 Alice’ input: x A Bob’s input: x B Alice’s output: y B Bob’s output: y B Evaluation of f by SFE

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

Example: private computation of ax+y 32 Bob has y, a Alice has x Problem: compute random shares of ax+y = r A +r B mod N

Example: private computation of ax+y 33 Bob has y, a Key pair Alice has x Problem: compute random shares of ax+y = r A +r B mod N

Example: private computation of ax+y 34 Bob has y, a Alice has x Problem: compute random shares of ax+y = r A +r B mod N Key pair Public key

Example: private computation of ax+y 35 Bob has y, a Key pair Alice has x Problem: compute random shares of ax+y = r A +r B mod N Public key Generate a random number

Example: private computation of ax+y 36 Bob has y, a Key pair Alice has x Problem: compute random shares of ax+y = r A +r B mod N Public key Generate a random number

Example: private computation of ax+y 37 Bob has y, a Key pair Alice has x Problem: compute random shares of ax+y = r A +r B mod N Public key Generate a random number

Example: private computation of ax+y 38 Bob has y, a Key pair Alice has x Problem: compute random shares of ax+y = r A +r B mod N Public key Generate a random number

Example: private computation of ax+y 39 Bob has y, a Key pair Alice has x Problem: compute random shares of ax+y = r A +r B mod N Public key Generate a random number

Example: private comparison of scalar product 40 Bob Alice Problem: which is greater ?

Example: private comparison of scalar product 41 Bob Key pair Alice r A and r B are random shares of Comparison by SFE rArA rBrB void Comparison result Problem: which is greater ? Public key Generate a random number r B

PPDMの実例 42

プライバシ保護型決定木学習 [Lindell00] 43  決定木学習の例  データ集合T  クラス集合C={c i }, 属性集合A={a j }  クラスc i を持つデータ集合T(c i )  エントロピー  条件付エントロピー  情報利得  情報利得を最大にする属性における分割  プライバシ保護型決定木学習  分割データを開示せずに、情報利得を最大 化する属性を選択  Aliceのa, Bobのbからの(a+b)log(a+b)の 秘匿評価に帰着 Alice’s data Bob’s data

プライバシ保護型リンク解析  リンク解析→ グラフのリンク構造からノードを重要度に応じてランキング  Web文書解析において有名かつ有用 (spectral ranking)  E.g., PageRank (Page et al.)  これまでのリンク解析の対象は…  文書ネットワーク、文献引用関係、たんぱく質・DNA相互作用関係、etc…  人間関係や経済活動などの実社会ネットワークを対象にできないか？  人・企業などの信頼度や実績に応じたランキング  プライバシー・機密性などがボトルネックになる 44 ランダムウォーク時の 状態遷移確率行列 べき乗法： マルコフ連鎖の定常分布 x を求める 定常分布密度でranking 重要 まあまあ そうでもない まあまあ そうでもない

グラフにおけるプライバシー(1)： 取引グラフ  企業間取引: 企業iの企業jからの購入額は年間w ij 円  取引関係がリンクe ij, 取引額が重みw ij なる重み付きグラフG=(V,E,W)  企業iと企業jは取引e ij を認識、それ以外の企業には取引e ij の存在は秘密  企業iと企業jは取引額w ij を認識、それ以外の企業には取引額w ij は秘密 45

グラフにおけるプライバシー(2)： 通信グラフ 46  個人間の通話: iさんからjさんへの通話頻度はw ij  通話関係がリンクe ij, 通話頻度が重みw ij なる重み付きグラフG=(V,E,W)  iさんとjさんは通話e ij を認識、それ以外の人には通話e ij の存在は秘密  iさんだけが通話頻度w ij を認識、jさんとそれ以外の人には通話頻度w ij は 秘密

グラフにおけるプライバシー(3)： 評価グラフ  人事評価: iさんからjさんへの評価はw ij  評価関係がリンクe ij, 評価が重みw ij なる重み付きグラフG=(V,E,W)  iさんだけが評価関係e ij を認識、それ以外の人には評価e ij の存在は秘密  iさんだけが評価w ij を認識、jさんとそれ以外の人には評価w ij は秘密 47

ネットワーク構造を持つ秘密情報のモデル化: Private Graph  Privately shared matrix  M=(m ij ) n×n行列  行列Mをn個に分解し、n個のノードが各パーツを保持している  各ノードが保持しているパーツは他のノードには秘密  典型的な2パターンを想定  Row-private: ノードiはi行目のみを保持  Symmetrically-private: ノードiはi行目およびi列目を保持 48 Node 1 Node 2 Node n

ネットワーク構造を持つ秘密情報のモデル化: Private Graph  Privately shared matrix  M=(m ij ) n×n行列  行列Mをn個に分解し、n個のノードが各パーツを保持している  各ノードが保持しているパーツは他のノードには秘密  典型的な2パターンを想定  Row-private: ノードiはi行目のみを保持  Symmetrically-private: ノードiはi行目およびi列目を保持 49 Node 1 Node 2 Node n

ネットワーク構造を持つ秘密情報のモデル化: Private Graph 50 取引グラフ リンク先・リンク元ともに 情報を共有 ↑ リンク構造の秘密性 ↑ 重みの秘密性

ネットワーク構造を持つ秘密情報のモデル化: Private Graph 51 通話グラフ リンク先・リンク元ともに リンク情報を共有 ↑ リンク構造の秘密性 ↑ 重みの秘密性

ネットワーク構造を持つ秘密情報のモデル化: Private Graph 52 評価グラフ リンク元のみが情報を保持 ↑ リンク構造の秘密性 ↑ 重みの秘密性

ネットワーク構造を持つ秘密情報のモデル化: Private Graph 53 目標：private graphを違反せずにspectral rankingを行う

Decentralized Spectral Ranking 54 Node iに着目 j i j x j p ji  Node iは，被リンク先ノードからp ji を送信してもらい  Private graphでは…  x j p ji はnode iにvisibleではない  Node jはP ji をnode iに見せずに を更新したい

Link-awareモデルにおけるspectral ranking  Link-awareモデルにおけるSpectral ranking 1. Node iにリンクしているノード (node j )は c ji ←Enc(x j p ji ) を計算しnode iに送信 55 j i j x j p ji c ji ←Enc(x j p ji )

Link-awareモデルにおけるspectral ranking  Link-awareモデルにおけるspectral ranking 1. Node iにリンクしているノード (node j )はc ji ←Enc(x j p ji ) を計算しnode iに送信 2. Node iは上の更新式のかわりに 56 j i j x j p ji c ji x j p ji

Link-awareモデルにおけるspectral ranking  Decentralized spectral ranking  Link-awareモデルにおけるSpectral ranking 57 j i j x j p ji c ji x j p ji

他のリンク解析法への拡張  Private graph上のPageRank: PrivateRank  Private graph上のHITS: PrivateHITS 58

実験：比較対象  Link-aware model  DSA(decentralized spectral analysis) [Kempe07]  P2P上でspectral rankingを行うプロトコル  SFE (secure function analysis) [Yao86]  任意の分散計算を安全に行うプロトコル  PR (PrivateRank)  提案法 59

実験: Link-aware model 60 DSA PR(提案法, 結託対性なし) SFE PR(提案法, 結託対性あり)

考察  DSA：計算は速いがプライバシ保護は完全ではない  SFE: プライバシ保護は達成するが計算が重い  提案法(PR): プライバシ保護と計算効率性を両立 61

Future direction  Personalizedサービスとの接続  サービスのpersonalizationの深化と個人情報の利用は密接に関係  ネットワーク/グラフマイニングへの発展  ネットワークに含まれるリンク情報は本質的に秘密保護が必要とされる  送受信関係, 電話発着信関係, 企業間資本関係, 地理的移動グラフ etc…  ユビキタス計算環境との接続  携帯電話＋GPS  個人の所有物に付与されたRFIDを用いたデータマイニング  応用:  情報大公開プロジェクトにて進行中  マイ・ライフ・アシストサービス(NTTドコモ)  GPS付き携帯電話やICカード乗車券から収集したユーザーの行動データをもとに、ユー ザーにおすすめの情報やコンテンツを表示する「空気の読めるケータイ」  GPS付き携帯電話やICカード乗車券からの位置情報を組み合わせている 62

参考  代表的な論文  L. Sweeney. k-anonymity: a model for protecting privacy. International Journal on Uncertainty, Fuzziness and Knowledge-based Systems, 10 (5), 2002; (匿名化)  L-diversity: Privacy beyond k-anonymity, Ashwin Machanavajjhala et al., ACM Transactions on Knowledge Discovery from Data (TKDD), Vol. 1, Issue 1, Article No. 3, (2007). (匿名化)  Privacy-preserving data mining, Agrawal, R. and Srikant, R., ACM SIGMOD Record, vol. 29, no. 2, pp , 2000, ACM (乱数アプローチ)  Privacy Preserving Data Mining, Lindell, Y. and Pinkas, B, Journal of Cryptology, vol. 15, no. 3, po , 2002, Springer (暗号アプローチ)  サーベイ論文  State-of-the-art in privacy preserving data mining, Verykios, V.S. and Bertino, E. and Fovino, I.N. and Provenza, L.P. and Saygin, Y. and Theodoridis, Y., ACM SIGMOD Record, vol. 33, no. 1, pp ,  Privacy-Preserving Data Mining: Why, How, and When, Vaidya, J. and Clifton, C., IEEE SECURITY & PRIVACY, pp , 2004, IEEE Computer Society  プライバシーとAI, 沼尾 雅之, 人工知能学会誌, vol. 21, no. 5, pp , 2006  プライバシー保護データマイニング, 佐久間 淳, 人工知能学会誌, 2009年3月号  書籍  Privacy-Preserving Data Mining: Models and Algorithms, Charu C. Aggarwal Philip S. Yu, Springer- Verlag (2008/07)  Privacy Preserving Data Mining (Advances in Information Security), Jaideep Vaidya, Chris Clifton, Michael Zhu, Springer-Verlag (2005/12/30) 63