プライバシー保護データマイニング ビッグデータにおける プライバシーの課題 菊池浩明 匿名化のリスク 明治大学 [email protected] 世界最先端IT国家創造宣言 n 2013年6月14日閣議決定 n n 1. 革新的な新産業・新サービスの創出 と全産業の成長を促進する社会の実現 q (1) 公共データの民間開放（オープンデータ） ・ビッグデータの活用の推進 » 公共データの案内・横断的検索を可能とするデ ータカタログサイト » 個人情報保護ガイドラインの見直し.第三者機関 の設置を含む、新たな法的措置も視野に入れる． http://www.kantei.go.jp/jp/singi/it2/dai61/siryou2-1.pdf Suica履歴をJR東日本が販売 n 2013年7月26日 概要 q 目的：携帯電話事業 を通じた社会貢献 の一環 q 各基地局に所在す る携帯電話数，性別 ，年齢層別，居住別． q 都市計画，人口変 動調査，防災計画， 帰宅困難者対策 http://www.nttdocomo.co.jp/corporate/disclosure/mobile_spatial_statistics/ 「個人情報」とは n 定義 q JR東日本は4,300万枚 のSuicaの乗降履歴を， 7月から販売していた． q 名前，連絡先は除外， 性別と年月日は含む． q 日立製作所が購入． 市場調査用統計リポ ート，10駅分500万円． q 7月31日までに8,823 件の除外申請． 例）ライフログビッグデータ Docomo モバイル空間統計 q 個人情報： 生存する個人に関する情報であ 123, 菊池，03-123, 123, 菊池，03-123, 123, 菊池，03-123, 1980年，男性， 123, 菊池，03-123, 1980年，男性， 1980年，男性， 中野， 1980年，男性， 中野， 中野， 2013年8月09日， 中野， 2013年8月09日， 2013年8月09日， 160円 2013年8月09日， 160円 160円 160円 123, 菊池，03-123, 123, 菊池，03-123, 123, 菊池，03-123, 1980年，男性， X32, *，*, 1980年，男性， 1980年，男性， 中野， 1980年，男性， 中野， 中野， 2013年8月09日， 中野， 2013年8月09日， 2013年8月09日， 160円 2013年8月09日， 160円 160円 160円 って，当該情報に含まれる氏名，生年月日 その他によって特定の個人を識別すること ができるもの． q 匿名化： 個人情報から個人を識別すること が出来る情報の全部又は一部を取り除き， 代わりにその人と関わりのない符号又は番 号を付すこと． http://digital.asahi.com/articles/TKY201307260002.html 1 匿名化と暗号化 匿名化の処理 n n 暗号化 q 1. q 2. q 3. q 4. q 5. 暗号化 平文 暗号文 攻撃（解読） 平文解読，識別可能 × CPA，CCA n 匿名化 n 氏名 年齢 駅1 菊池 克巳 30 駅2 仮ID 駅1 匿名化 33 新宿 中野 オリジナルレコード 攻撃 （再識別） 処理 注意． q k-匿名化，l-多様化などの性質はまだ考えない．2,3,4 駅2 の組み合わせはNP完全． 新宿 中野 q 他にも，ノイズデータを加える(摂動化），確率的に 匿名化レコード データを交換する(swap)，統計情報を基にサンプリン グ(re-sampling), 合成 (synthesis) などもある． ? 匿名化例 仮名化（IDを除くだけ） 属性削除（列削除) レコード削除(行削除） 一般化 統計化 「再識別化」の種類 列削除 氏名 仮ID 日付 乗駅 降駅 残高 菊池 3 10/14 新宿 中野 1200 高橋 4 10/14 新宿 三鷹 840 佐藤 5 10/14 新宿 御茶ノ水 600 菊池 3 10/15 中野 御茶ノ水 1020 仮ID 駅1 駅2 駅3 4駅 3 新宿 中野 中野 御茶ノ水 4 新宿 中野 三鷹 新宿 ユーザ 5 数 3 n=3 新宿 御茶ノ水 御茶ノ水 新宿 中野 御茶ノ水 人口 n 駅数 448, 千葉395, 埼玉 291, 栃木，群馬 q n = 42,598,300 = 4 x 107 q 関東地方(東京 930, 42,470,000 仮ID 駅1 駅2 3 新宿 中野 4 新宿 中野 3 中野 御茶ノ水 4 中野 御茶ノ水 6 新宿 信濃町 (2) 識別非特定 （仮IDが同じ人を リンク出来る） (3) 一意識別 （その駅に降りた人が 一人しかいない） 評価1 （仮名化の評価） q 総数 9,262件 q Suica 発行枚数 3 SUICAの案件は(2)を見落としている． k−匿名性で議論しているのは(3)だけ． q 東京 930万，神奈川 (2012年4月1日, Wikipedia） 菊池 駅数 s=4 基本データ n (1) 特定個人 再識別可能 神奈川 448, 千葉 395) m = 2,497 = 2.5 x 103 (http://info.jmc.or.jp/ekiensen.html ) q JR西日本 811駅， Pasmo 1,291駅，JR 東海 149, JR西日本 430駅 n 問題 q 各カードにs個の駅名があるとすると，(全員 が)再識別できるsはいくらか． n 仮定 q m個の駅乗降は一様に分布する独立事象 n 解 q ms ≧ n (全ユーザ数） を解いて， s = 2.237 駅．（3駅あれば全利用者が再識別できる） 2 sに対する再識別順位x* 評価2 (k-匿名化の評価） n x* = 23693 信濃町(153位) x 昭島 (154位) 99.9 % 行削除する必要性 P(x) 再識別可能 順位 x* 再識別可能 確率 k/n 再識別可能 レコード 行削除しないと 危険なデータ x* = 234位 立川(15位) x 浜松町 (16位) x 田町 (17位) 第 x 位 匿名化と課題 匿名化 プライバシー保護データマイニング 病院 A 病院 B Privacy-Preserving Data Mining 概要 PPDM 病院 A 病院 B AI needs Security n Privacy-Preserving Data Mining: Models and Algorithms By Charu C. Aggarwal , Philip S. Yu, Springer, 2009. n Privacy Concerns required now! 氏名 ID 年齢 術式 入院日 菊池 一郎 32 C 2011/12 佐藤 次郎 63 C 2011/12 加藤 三郎 51 P 2012/2 44 P 2012/3 鈴木四郎 氏名 匿名 化 32 C 2011/12 佐藤 次郎 63 C 2011/12 加藤 三郎 51 P 2012/2 44 P 2012/3 鈴木四郎 術式 入院日 30 C 2 60 C 2011 3 50 P 2012 4 P 2012 40 2011 (1) 属性情報から再識別化リスク (2) データ削除による精度劣化 ID 年齢 術式 入院日 菊池 一郎 年齢 1 暗号 化 年齢 術式 入院日 1 224 126 832 2 727 902 265 3 720 844 554 4 020 947 402 暗号化したまま正確な疫学調査 PPDM Class [Aggarwal 2009] n 1. Randomization q Adding artificial random noise． Perturbation Approach. n n 2. k-anonimity model 3. Distributed privacy preservation q Cryptographical Approach. Primitives of MPC (Multi-party Computation), OT (Oblivious Transfer) n 4. Downgrading q Downgrading effectiveness of mining knowledge to prevent them from analyzing 3 Tradeoff Vertically Partitioned Data n Safety statistics Players Gender age Milk Beer q Shop B F 20s 0 0 q regulation M 10s 0 1 M 30s 1 1 F 30s 0 1 F 10s 1 0 M 20s 1 1 q Agency A (no risk of leakage) Privacy-Preserving Data Mining Blog SNS n Objective q Common Knowledge of Beer Buyers Medical records Agency A Shop B private Horizontally Partitioned Data n n Players 比較 Gender Age Owner beer q Shop A F 20s Y 0 q Shop B M 10s N 1 q Competitors M 30s Y 1 Shop A Objective q Common Knowledge of Beer Buyers q Accuracy F 30s Y 1 F 10s N 0 M 20s N 1 Shop B 2 マイニング 1 摂動 マイニング ノイズ除去 分散計算 復元 秘匿計算 復号 知識 3 分割 汎用性 効率 △ ○制約 なし △ ○任意 1b. MDAV サンプリング △+ ○ △++ ○ ○- 2. 匿名化 一般化，削除 △ ○ △- ○ △ NP 完全 3. 秘匿計算 [LP00] OPE，エント ロピー ○ 2 ○ 決定木 × 3b. SFE [Yao] 1-out of-4 OT ○ ○(基本 は2) ○ ○ブール関 数 ×-- 3c. 水平分割 [JW05] 準同型性 ○ 2 ○ クラスタリン グ × 3d. P2P [Canny 02] 準同型，特異 値分割 ○ ○ ○- 固有値 ×- ○ 各自 独立 Author Application Tricks Perfor mance 1 Naïve Bays Vaidya Clifton [27] Classify Identify Conditional probability (scalar prod.) Good 2 Decision Tree Du & Zhao [8] Classify Identify Entropy gain (OFE) Fair 3 k-menas Vaidya& Clifton [26] Clustering Euclidian Bad distance (scalar prod. & SFE) 4 Associati on Rule Vaidya & Clifton [25] Knowledg e Support (scalar prod.) good Recomme ndation Eigenvalue (dist. SVD) Bad 4 Downgrading 3 暗号化 精度 分割数 秘匿 ランダマイ ズ，ベイズ Data Mining マイニング データ 要素 1. 摂動法 Summary of PPDM アプローチの違い 匿名化 技術 5 Collabora Canny, tion Kikuchi Filtering 4 ヘリコバクター・ピロリ n Helicobacter pylori q 胃に感染するらせん状の細菌 q 胃炎，胃潰瘍，十二指腸潰瘍 PPDMの応用 プライバシー保護疫学調査 疫学調査 n n 統計量 χ= 加法準同型性 a c ad / ≈ a + b c + d bc N − 1((ad − bc ) ± N / 2) (a + c) (b + d )(a + b)(c + d ) (Homomorphic Property) E + m+m’ 氏名� 年齢� 部位� 氏名� E(m, r) E(m’, r’) × E n Privacy-preserving 胃境界� 吉田哲郎� 45 2001 佐久間淳� 28 胃底部� 菊池浩明� 25 2001 三上春雄� 35 幽門� 古川和彦� 35 2002 組織A (千葉がんセンター）� 組織B (厚生省・保健所）� セキュア内積プロトコル B X = (富山，菊池，松尾，若林）� � = (1, 0, 1, 1) Xの暗号化� E(1) computations Y = (富山，菊池，松尾，若林）� � = (1, 1, 1, 0) E(1), E(0), E(1), E(1) E(m+m’, r+r’) E(m,r) × E(m’, r’) = E(m+m’, r+r’) E(m,r)x = E(mx,rx) 年齢� 検診日� 菊池浩明� 25 A n 可換な図 m m’ 組織A, Bが互いのデータセット を秘匿して，相対危険度RRを求める n 研究目的: がん罹患� 対象(無) 罹患率� a b a/(a+b) c d c/(c+d) 相対危険度 (Relative Risk) RR = n 研究目的: 安全な疫学調査 患者-対象調査 要因� ピロリ菌� 未感染� http://ja.wikipedia.org� の原因のひとつ q 40-50%の感染率(日本の40代以上 70%) 先進国は低い q 発ガン性は認められているが，そのリスクはま だ明らかになっていない c 復号� D(c) = D(E(2)) = 2 = | X ∩ Y | 合計のみ分かる � c=E(1)1E(0)1E(1)1E(1)0 =E(1*1) E(0*1) E(1*1) E(1*0) =E(1 + 0 +1 + 0) =E(2) 5 データセット CAN（がんセンター） n 人口分布 n 4000 氏名，性別，生年月 日，住所� 受付番号，診断日， 死亡日� 胃（小湾，大湾，底 部），幽門� 悪性リンパ腫，血管， 腫瘍� 分化度� 0〜9 100.00% 3000 80.00% 頻度 2500 2000 60.00% 1500 40.00% 1000 20.00% 500 20 00 19 80 19 60 19 40 0.00% 19 20 19 00 0 がん患 者数� 属性 基本� 情報� 管理� 情報� 診断� 部位� 組織� 120.00% 3500 照合結果 生年月日 非登録者� 計� ピロリ菌� 80 2,549 2,629 非保有者� 346 106,988 107,334 計� 426 2,999,574 3,000,000 相対危険度 RR = 9.70 （ピロリ菌はがんに9.7倍なりやすい） 有意性 χ = 17.81 (98%以上の確からしさで有意） � 処理時間 2500 "thread.txt" f(x) 1024bit Pailier暗号， Hadoop, Intel E5 Processing time [s] 2000 1500 Randomized Approach n = 14万件 (105)の時， 40分 (1CPU) 3分 (16 CPU) 1000 Perturbation 500 0 0 2 4 6 8 10 12 14 16 # of threads k 1. Randomization n Proposed by q Agrawal R., Srikant R. Privacy-Preserving Data Mining. Proceedings of the ACM SIGMOD Conference, 2000. q Idea: adding noise and reconstruction (denoise process based on Bays’s theorem) n Pros: scalability (no interaction) n Cons: outlier, PCA attack Perturbation n Learning data gender Beer X Random R Y q True X F 0 1 0 （unknown distribution） q Random R (known distribution） q Randomized Y Y = ƒ(X, R) M 1 0 1 M 1 1 1 Shop A F 1 0 0 F 0 1 0 M 1 0 1 Shop B 6 How to discard random noises Random Yes 25% 0.5 Yes 45% fXj+1(a) := (Bayes' rule) ∞ −∞ m=6 fY (( xi + yi ) − a ) f Xj ( a ) j := j+1 until (stopping criterion met) n Converges to maximum likelihood estimate. q D. Agrawal & C.C. Aggarwal, PODS 2001. 10 8 6 4 k (True ballots) x 2 = 40%" fY (( xi + yi ) − a ) f Xj ( a ) ∫ 0.2 0 fX0 := Uniform distribution j := 0 // Iteration number repeat n 1 ∑ n i =1 m=10 m=8 0.1 Reconstruction: Bootstrapping 0.3 2 True Yes 20% True No 30% 0.4 0 No 55% 0.6 P(k|m) Random No 25% 60% = 2 x" Probability Distribution of P(k|m) 評価値行列 X i1 i2 i3 i4 i5 Y i1 i2 i3 i4 i5 u1 2" 2" 3" 1" 0" u1 2" 3" 1" 1" 0" u2 1" 3" 2" 0" 3" 摂動化 u2 1" 1" 2" 0" 1" u3 2" 0" 3" 3" 2" u3 1" 0" 3" 3" 0" u4 3" 2" ＊ 2" 2" u4 3" 2" ＊ 2" 3" オリジナルデータ 偽データ 実験１：再構築された評価の分布 X Z Y 生活習慣とがんの相対危険度 の安全なコホート調査 7 JPHC 多目的コホート研究 n 多目的コホート研究に基づくがん予防な ど健康の維持・増進に役立つエビデンス の構築に関する研究 身体活動量とがんの関係 n n q 国立がん研究センター，11保健所，国立循 環器病研究センター q 活動量 q 14万人コホート， MET x 時間 20年間に渡る追跡調査 q 生活習慣アンケート， 血液資料，健康診断 n 課題 患者-対象調査 n (1) 要因� がん罹患� 対象(無) 罹患率� 高運動量� a b a/(a+b) 低運動量� c d c/(c+d) n 統計量 χ= ID 氏名� N − 1((ad − bc ) ± N / 2) (a + c) (b + d )(a + b)(c + d ) 秘匿積集合プロトコル [AES03] n 照合タグ（可換性を満たす一方向性関数） 1. 乱数 u ∈ Zq H(1)u, H(2)u, H(3)u 3. 照合 B Y = {2, 3, 4} 2. 乱数 v ∈ Zq H(2)v, H(3)v, H(4)v H(1)uv, H(2)uv, H(3)uv H(2)vu, H(3)vu, H(4)vu H(1)uv, H(2)uv, H(3)uv 年 部位� 齢� 10 菊池浩明� 25 胃境界� a c ad / ≈ a + b c + d bc A X = { 1, 2, 3} 個人情報の目的外利用 n (2)一意な識別子の欠落 相対危険度 (Relative Risk) RR = n 男0.74 女0.87 多目的コホート研究の成果 2013, 多目的コホート研究 事務局 疫学調査 n 定期的に体を 動かす人はが んのリスクが減る 運動強度指数 MET (Metabolic Equivalent) マッチ数 z = 2 = |X∩Y| 識別の困難さは素体上のDDH問題に帰着することが証明されている 11 佐久間淳� 28 胃底部� ID 氏名� 年齢� METs� 301 吉田哲郎� 45 H 302 菊池浩明� 25 H 303 古川和彦� 35 L 12 三上春雄� 35 幽門� 個人識別子 n 一方向性ハッシュ関数 q H: {0,1}* → {0,1}128 q SHA1, SHA2 (256) 標準化アルゴリズム q 例) ID1 = H(菊池浩明，明治大学) = 1938374 q 安全性: AES 02ではIDは互いに漏洩しな いので，名前から決め打ちされる恐れは ない． n 課題： 入力に使う個人属性は何が適当か 8 漢字表記氏名の課題 n 1. 同姓同名者の調査（氏名カナ） 異体字，システム独自拡張外字 同姓同名数 q 斉藤，斎藤，齋藤，齊藤,…. q UTF-16では37,000字を対応できない n 2. 同姓同名問題 JPHC 文献[4] 電話帳 同姓同名数の順位 個人属性の組み合わせ 実験結果 PSOモデ 重複最大数 未解決 ル絞り込み レコード数 量 [bit] 属性組 A 氏名カナ+ 姓名 14 30 30180 B 氏名カナ＋姓名＋生年月日 30 2 16 C 氏名カナ＋姓名＋生年月日 ＋都道府県 36 2 12 D 氏名カナ＋姓名＋生年月日 ＋住所 56 0 0 E 氏名カナ＋生年月日＋住所 55 0 0 F 氏名カナ＋住所 40 2 16 G 姓名＋生年月日＋住所 42 2 10 確率検定 交絡因子肥満度 n 身体活動量と結腸がんの関係 BMI27を削除 本実験結果（相対危険度） 井上 2008 （オッズ比） 男性に関しては，身体活動量が適量あれば がん罹患のリスクが軽減する． 結論 n プライバシーを保護して分散されたデー 活動量Lを基準として，95%有意水準(3.8)を超えて 相対危険度が下がる タセット間で相対危険度を安全に計算す るシステムを実装した． n 識別子として，カナ表記の氏名＋生年 月日＋住所の属性のハッシュ値を利用． n 14万件のデータを4分間で正確に結腸 がんの相対危険度と確率検定を実施． 9
© Copyright 2024 ExpyDoc
