PPT

秘匿積集合プロトコルを利用した
プライバシ協調フィルタリングの提案
◎木澤寛厚磯崎邦隆菊池浩明
東海大学工学研究科情報理工学専攻
背景

商品の量が多い
見つからな
いorz
ネットショップ
情報推薦システム
amazon

他の利用者の嗜好に
基づき，利用者の嗜好
を予測

利用者の嗜好に合う
商品を提示する
http://www.amazon.co.jp/
推薦システム：問題点
B’
サーバ
MAC
S
嗜好情報漏洩の可能性
A
B
C
MAC
？
Windows
A
B
C
嗜好情報が漏洩せず
推薦結果を出したい
従来研究

Cannyの方式[1]


共役勾配法を用いて特異値分解を準同型性暗号で
行う
秘匿CF方式[5]


準同型性暗号を用いて協調フィルタリングを行う
欠損値を秘匿するためにO(n2)の通信コスト

ユーザ数943人，アイテム数1682個で1TBの通信コスト
莫大な計算コスト・通信コスト
目的

秘匿積集合プロトコル[3]というアプローチで、
個人情報を秘匿したまま嗜好を予測する
手法を提案する

計算コスト・通信コストを削減する
要素技術：一覧

協調フィルタリング方式(CF方式)



2者間秘匿積集合プロトコル



嗜好の評価値を予測する
一般的な推薦システムに利用されている技術
お互いが評価したアイテムの数s(ui,uj)を得る
お互いどのアイテムを評価しているか秘密
準同型性暗号
要素技術：
協調フィルタリング方式(CF方式)
アイテム
ユ
ー
ザ
a
b
c
d
i1
i2
＊
1
2
i3
5
3
2
2
＊=aの平均＋
類似度
S
i4
1
3
5
平均
0
3.5
2
0.88
0.96
2
2.7
bとの類似度・bの評価+dとの類似度・dの評価
類似度の総和
0(1-2)+0.96(2-2.7)
=3.5 +
0+0.96
=
2.8
要素技術：
2者間秘匿積集合プロトコル
B={1,2}
A={2,3}
a
b
E ( f ( x))  E (( x  2)( x  3))
復号
f (1)  0
f ( 2)  0
0の数=|A∩B|=1
E ( f (1)) E ( f (2))
提案方式 1/3
a
b
c
d


i1
＊
1
2
i2
2
i3
3
2
1
i4
5
3
5
s(a,*)
0
1
2
2者間秘匿積集合プロトコルを使用し、
s(a,*)の値をそれぞれ出す
閾値Tを決める、T≦s(a,*)の式を満たす
ユーザの集合をBとする

今回はT=1、B={c,d}
提案方式 2/3 -1
i1
c
a
i1 i2
＊ 2
i3
i4
5
i3
i4
2.5 2.5 2
3
c
n out of 1 OT
a
E (r1,c )  E (2.5)
E (r1,d )  E (2)
i2
d
i1
2
i2
1
i3 i4
2.7 5
n out of 1 OT
d
提案方式 2/3 -2
c
a
i1 i2
＊ 2
i3
i4
5
E (h1,d )  E (1)
i2
i3
i4
0
0
1
1
c
n out of 1 OT
a
E (h1,c )  E (0)
i1
d
i1
1
i2
1
i3
0
i4
1
n out of 1 OT
d
提案方式 3/3
i1
i2
a
c
＊
2
d
2
＊=aの平均＋
1
類似度
s(a,*)
平均
i3
i4
2
5
3
1
3.5
2.5
5
2
2.7
dとの類似度・dの評価
類似度の総和
・準同型性暗号では割り算は計算できない
→分子と分母を計算し，復号してから割り算を計算する
分子 = s(a,c)(r1,c-rc)+s(a,d)(r1,d-rd) = 1(2.5-2.5)+2(2-2.7) = -0.7
分母 = h1,cs(a,c)+h1,ds(a,d) = 0×1+1×2 = 2
＊= aの平均+分子/分母=3.5+(-0.7)/2 = 3.15
評価実験

公開データベース(Group Lens)を使用し
MAE・通信コスト・計算コストを調べる

100個の評価値を未評価とみなし推薦値を求めMAE
を調べる
ユーザ数
アイテム数
943人
1682個
総評価数
暗号文のサイズ
べき乗計算
100,000個
256byte
1764(ms)
精度
1
SCF[3]
Proposed
Proposed
SCF[3]
0.95
MAE
0.9
0.85
0.8
0.75
0.7
0.65
0
10
20
30
40
50
60
70
number
of satistied users
推薦者数
80
90
100
計算コスト
1e+006
570000s
6.5日
SCF[3]
Proposed
computation cost[s]
100000
10000
1000
337s
5分
100
10
1
0
10
20
30
40
50
60
70
number of推薦者数
satistied users [mB]
80
90
100
通信コスト
1000
500
Proposed
SCF[3]
104.3GB
communication cost [GB]
100
10
1
0
0.1
0.01
0.001
0.0001
0
10
20
30
40
50
60
70
number of 推薦者数
satistied users [mB]
80
90
-500
100
0.8GB
通信コスト・計算コストまとめ
SCF(従来)
提案方式
精度
×
○
通信コスト
×
○
計算コスト
×
○
漏洩する情報 ○
× ※
※類似度s(ui,uj)が被推薦者に漏れる
考察：類似度 1/2


従来方式
→コサイン尺度
提案方式
→積集合の大きさ
提案方式の精度が
なぜ向上したのか検討
考察：類似度 2/2
0.9
0.8
SCF similarity
コサイン尺度
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
50
100
150
200
250
300
350
Proposed similarity
交わりの大きさ

相関係数=0.922
→提案方式の類似度はユーザ間の
類似度を反映している
考察：
2者間秘匿積集合プロトコル

2者間秘匿積集合プロトコルのコスト

推薦者の評価値の数を秘匿する場合，
1推薦者あたりnの計算コストが生じる


ユーザ数943，アイテム数1682だと
1推薦者あたり48分計算コストが生じる
通信コストは(m-1)n

ユーザ数943，アイテム数1682だと682GB
実験ではこれらのコストを除いている
→ セキュリティとコストのトレードオフ
結論

秘匿共通部分評価を利用した新しい協調
フィルタリング方式を提案した

精度が良くなった


通信コストを1/130に削減した


類似度と交わりの数の間に強い相関
ただしOTの秘匿積集合プロトコルのコストは
入っていない
計算コストを1/1700に削減した
今後の課題


2者間秘匿積集合プロトコルのコストの
詳しい検証
OTのコストの検証
紛失通信
クライアント
サーバ
{S1 , S 2 , S3}
g
r0
f (1), f (2), f (3)
g r0
f (0)  g r0
g
x
r1
f (x )
f (1)  a1
E f (1) ( S1 )
E f ( 2) ( S 2 )
E f ( 3) ( S 3 )
f (2)  g r1
f (3)  a2
y
E f (1) ( S1 ), E f ( 2 ) ( S 2 ), E f (3) ( S3 )
D ( E f (1) ( S1 ))
提案方式
BB
D
P1, D
 E (r1, B )   E (r1,C ) 


 
 E (r )   E (r ) 
B  
C 

 rD 
BC
BB
E (h1, B )  E (h1,C )
BC

BB (r1, B  rB )  BC (r1,C  rC ) 

 E  rD 


h
B

h
B
1, B B
1,C C


 1(2  2)  2(3  3) 
 E 2 
2
0 *1  1* 2



Download Report