slide

組織間プライバシー保護
データマイニングの考察
9adrm009 香川大介
背景：異業種間の連携
店舗・利用履歴
連携
B
A
A
利用者
u1
B
組織
u2
高松に行かれる
のでしたら評判
の高い讃岐うど
んのお店を紹介
します
u3
従来技術：垂直分割PPDM

Vaidya, Clifton 2003
 秘匿内積評価プロトコル
 ナイーブベイズ推論器
P(テニス|晴，高)
A
B
日にち
天気
気温
湿度
テニス
1/19
晴
高
低
Yes
1/20
晴
高
高
No
1/21
雨
高
高
Yes
1/22
雨
低
高
Yes
問題点：分割の非同期性
A
B
ID
天気
気温
ID
湿度
1
晴
高
1
低
2
晴
高
3
雨
問題3. 非効率
4
雨
N
100
雨
テニス
高
*
3
Yes
問題1. 欠損値
*
*
Yes
高
低
4
高
Yes
5
高
No 重複
問題2.
3
高
高
…
No
研究目的

目的
 非同期垂直分割のデータセットに対するナ
イーブベイズ推論器

仮定：
 評価値数 nA ≈ nB ≪ N (ID空間数）

要求条件
 欠損値，（重複），効率性
従来研究1. [VC03]

秘匿内積
 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
X = { 1, 2, 3}
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
マッチ数 z = 2 = |X∩Y|
照合タグの問題

ナイーブベイズ推論への適用検討
 問題点：
z= |X∩Y|が組織Aに分かってしまう．
 VC03では，途中結果は nA + nB = a.b と分散
されていた．
提案方式

方式1
 再ソートして共通部分だけにVC03を適用.
 欠損値の近似値で置換

方式2.
 チャフ付き照合タグ
(AES03ベース）
 途中結果を不明にするようにチャフを混入
提案方式2. チャフ付照合タグ
A
X = { 1, 2, 3}
1. 乱数 u  Zq
B
Y = {2, 3, 4}
2. 乱数 v  Zq, sB [0,n]
H(1)u, H(2)u, H(3)u
3. 照合
H(2)vu, H(3)vu, H(4)vu
H(2)v, H(3)v, H(4)v
ti = H(yi)v w/p= sB/n
ri
w/p= 1-p
H(1)uv, H(2)
r2 uv , H(3)uv
H(1)uv, r2 , H(3)uv
マッチ数 sA = 1 = |X∩Y|
SFE2
sB/n = 1/2
|X∩Y| = sA * n/sB = 2
出力

分散された積集合
s A  nB
| X  Y |
sB

秘匿関数計算により
評価
パフォーマンス
 精度
 安全性

暗号化処理（方式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での実装例

SharedSum
分散和比較
S（分散した和の比較）
A0 + SB0 > SA1 + SB1
1. program SharedCmp {
2.
const size = 2; type int = Int<8>;
3.
type AliceInput = int[size]; type BobInput = int[size];
4.
type AliceOutput = int; type BobOutput = int;
5.
type Output = struct {AliceOutput alice, BobOutput bob};
6.
type Input = struct {AliceInput alice, BobInput bob};
7.
function Output output(Input input) {
8.
if(input.alice[0] + input.bob[0] >
9.
input.alice[1] + input.bob[1]){
10.
output.alice = input.alice[0];
11.
output.bob = input.bob[0];
12.
}else{
13.
output.alice = input.alice[1];
14.
output.bob = input.bob[1];
15.
}
16. }
17. }
time [s]
SFE処理時間
10bit = 1024の定義域
SFE1 (加算） = 1.6 秒
SFE2 (乗算） = 15.3 秒
7
6
5
4
3
2
1
0
Sum
Div
0
5
10
15
bit
20
25
処理時間の比較
120
1.1 * x + 1.5 + 1.6
方式1.
内積
0.15 * 4 * x*0.1
+ 15
0.15*4 * x*0.01 + 15
100
80
60
40
方式2. 照合タグ n/N = 0.1
20
n/N = 0.01
0
0
20
40
60
N
80
100
精度と安全性
真の Z = |X ∩ Y| = 10
0.3
P(sA|z)
0.25
0.2
0.15
0.1
0.05
0
0
5
観測値 szB
10
15
まとめ
入力単位
計算量
(tE 暗号化，tD 複
号化，tP べき乗）
精度
安全性
方式1 [VC03]
秘匿内積
N次元ベクトル
方式2 [AES03]
チャフ照合
n要素の集合 X
T1 =
T2
tE N + tD +SFE1 = tP n +SFE2
誤差なし
sB/n
P(z | x.y) = 1/N
P(z | sA) > 1/n
結論
方式1(再ソート法)はID空間が狭いとき有
効．精度も高く，安全性も保証．
 方式2(チャフ付き照合タグ）はID空間が疎
であるときに有効．ただし，精度は比較的
低く，元の値について漏れる情報がある．

分散比較

問題
安全性 P(a|c)の分布
0.25
0.20
0.15
系列1
0.10
0.05
0.00
0
5
10
15
方式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. 再ソート
加法の準同型暗号
Enc(m1 ; r1 )  Enc(m2 ; r2 )  Enc(m1  m2 ; r1  r2 ),
rはランダムな値
Enc(m1 ; r1 ) m2  Enc(m1m2 ; r1 )
ElGamal暗号の場合
計算　2  3  5
C1 : g 2 r1  g 3 r2  g 5 ( r1  r2 )
C2 : g r1  g r2  g r1  r2
M  C1 / C2
g
5 ( r1  r2 )
 g5
計算　2 2  4
C1 : ( g 2 r1 ) 2  g 4 2 r1
C2 : ( g )  g
r1 2
/g
r1  r2
2 r1

Download Report