組織間プライバシー保護 データマイニングの考察 9adrm009 香川大介　

背景： 異業種間の連携 u1 u2 u3 高松に行かれるのでしたら評判の高い讃岐うどんのお店を紹介します 個人情報漏洩 店舗・利用履歴 連携 背景：　異業種間の連携 個人情報漏洩 店舗・利用履歴 連携 B A A B 組織 高松に行かれるのでしたら評判の高い讃岐うどんのお店を紹介します u1 u2 u3 利用者

従来技術：垂直分割PPDM Vaidya, Clifton 2003 秘匿内積評価プロトコル ナイーブベイズ推論器 P(テニス|晴，高) A B 日にち 天気 気温 湿度 テニス 1/19 晴 高 低 Yes 1/20 No 1/21 雨 1/22

問題点：分割の非同期性 A B ID 天気 気温 湿度 テニス 1 晴 高 低 Yes 2 3 雨 4 5 No 100 … 問題1. 欠損値 * * * 問題3. 非効率 問題2. 重複 N

研究目的 目的 仮定： 要求条件 非同期垂直分割のデータセットに対するナイーブベイズ推論器 評価値数 nA ≈ nB ≪ N (ID空間数） 欠損値，（重複），効率性

従来研究1. [VC03] 秘匿内積 Protocol Alice has X = (x1,..,xn) Bob has Y = (y1,..,yn) Wish to compute sA + sB = X.Y Protocol A sends E[x1], E[x2] to B B chooses sB and sends c = E[x1]y1E[x2]y2/E[sB] A decrypts D[c] = x1y1 + x2y2 – sB = sA

従来研究2. [AES03] 照合タグ（可換性を満たす一方向性関数） A B X = { 1, 2, 3} Y = {2, 3, 4} 乱数 u  Zq 2. 乱数 v  Zq H(1)u, H(2)u, H(3)u H(2)v, H(3)v, H(4)v H(1)uv, H(2)uv, H(3)uv 3. 照合 H(2)vu, H(3)vu, H(4)vu マッチ数 z = 2 = |X∩Y| H(1)uv, H(2)uv, H(3)uv

照合タグの問題 ナイーブベイズ推論への適用検討 問題点： z= |X∩Y|が組織Aに分かってしまう． VC03では，途中結果は nA + nB = a.b と分散されていた．

提案方式 方式1 方式2. 再ソートして共通部分だけにVC03を適用. 欠損値の近似値で置換 チャフ付き照合タグ (AES03ベース） 途中結果を不明にするようにチャフを混入

提案方式2. チャフ付照合タグ A B X = { 1, 2, 3} Y = {2, 3, 4} 乱数 u  Zq 2. 乱数 v  Zq, sB [0,n] H(1)u, H(2)u, H(3)u H(2)v, H(3)v, H(4)v ti = H(yi)v w/p= sB/n ri w/p= 1-p 3. 照合 H(2)vu, H(3)vu, H(4)vu H(1)uv, H(2)uv , H(3)uv r2 H(1)uv, r2 , H(3)uv マッチ数 sA = 1 = |X∩Y| sB/n = 1/2 SFE2 |X∩Y| = sA * n/sB = 2

出力 分散された積集合 秘匿関数計算により

評価 パフォーマンス 精度 安全性

暗号化処理（方式1） tE = 1.1 [s] 暗号化 tD = 1.6 [s] 複号 tP = 0.15 [s] べき乗

2. Fairplay (Yao’s SFE) Fairplay secure two-party computation system,by D Malkhi, N Nisan, B Pinkas, Y Sella, Usenix Security Symp. 2004. Compiler for SFDL to Boolean circuit (1. 8-bit AND, 2. 32-bit 比較，3. 16項目の24-bit暗号化データ検索，4. 16-bit メジアン）

FairPlayでの実装例 分散和比較 SA0 + SB0 > SA1 + SB1 SharedSum （分散した和の比較） program SharedCmp { const size = 2; type int = Int<8>; type AliceInput = int[size]; type BobInput = int[size]; type AliceOutput = int; type BobOutput = int; type Output = struct {AliceOutput alice, BobOutput bob}; type Input = struct {AliceInput alice, BobInput bob}; function Output output(Input input) { if(input.alice[0] + input.bob[0] > input.alice[1] + input.bob[1]){ output.alice = input.alice[0]; output.bob = input.bob[0]; }else{ output.alice = input.alice[1]; output.bob = input.bob[1]; }

SFE処理時間 10bit = 1024の定義域 SFE1 (加算） = 1.6 秒 SFE2 (乗算） = 15.3 秒

処理時間の比較 方式1. 内積 方式2. 照合タグ n/N = 0.1 n/N = 0.01

精度と安全性 真の Z = |X ∩ Y| = 10 観測値　sB

まとめ 方式1 [VC03] 秘匿内積 方式2 [AES03] チャフ照合 入力単位 N次元ベクトル n要素の集合 X 計算量 (tE 暗号化，tD 複号化，tP べき乗） T1 = tE N + tD +SFE1 T2 = tP n +SFE2 精度 誤差なし sB/n 安全性 P(z | x.y) = 1/N P(z | sA) > 1/n

結論 方式1(再ソート法)はID空間が狭いとき有効．精度も高く，安全性も保証．

分散比較 問題

安全性　P(a|c)の分布

方式1. 秘匿内積評価の処理時間 Secure scalar product n encryption + n exponentiations + n multiplications + 1 decryption n = 1000,1024 bit enc.の時: 270s = 4m

1. Naïve Bayes Vaidya Clifton 2004 [27] 識別（スパム判定） 最大尤度 CMAP = argmax(cj in {Y,N}) P(cj | a1,a2) P(yes | sunny, hot) = ½ P(no | sunny, hot) = ½ CMAP = yes (no)

Naïveな仮定： 全属性は独立 Naïve Bays CNB = argmax P(cj | a1, a2) = argmax P(a1, a2 | cj) P(cj)/ P(a1, a2) = argmax P(a1|cj) P(a2|cj) P(cj)/ P(a1) P(a2) = argmax P(a1|cj) P(a2|cj) P(cj) P(sunny|y) = 2/9, P(hot|y) = 2/9, P(y) = 9/14 P(sunny|n) = 3/5, P(hot|n) = 2/5, P(n) = 5/14 P(s|y)P(n|y)P(y) = 2/63 < P(s|n)P(h|n)P(n) = 2/35 より， argmax = n Class変数を持つサイトと 秘匿内積計算

方式1. 再ソート

加法の準同型暗号 rはランダムな値 ElGamal暗号の場合