秘匿積集合プロトコルの
推薦システムへの応用
7ADRM003 磯崎邦隆
指導教員 菊池浩明 教授
1
秘匿積集合プロトコル
Ιプレーヤが持つリストを秘匿したまま
共通な要素のみを抽出する
3人で共通な値
プレーヤA
プレーヤB
プレーヤC
1
1
2
1
1
2人で共通な値
3,5,6
公開
3
4
5
2人で共通な値
1,6 2
3
5
6
7
秘密
6
公開
2
情報推薦システム
腕時計 14596件
カメラ 10261件
Webショップ
ソファ 2784件
…
腕時計
評価
ユーザD
ユーザC
ユーザA
ユーザB
3
インターネット定点観測
ユニークホスト数
12台中6台のセンサで観測された
ユニークホスト数
観測機関 A
観測したセンサ台数
観測機関 B
観測機関 C
[福野 2006]
4
研究目的
定点観測
3人で共通な値
推薦システム
ユーザA
ユーザB
ユーザC
1
1
2
1
1
2人で共通な値
3
マルチパーティ
秘匿積集合の改良
公開
3
4
5
2人で共通な値
2
3
5
6
7
秘密
6
2者間秘匿
積集合の使用
公開
5
2者間秘匿積集合
[Freedman 2004]
ユーザA
アイテム 1
評価
2
ユーザB
3
4
アイテム 1
○ ○
評価
2
3
○
4
○
{2, 4}
{1,2}
f ( x)  ( x  1)( x  2)
E ( f ( x))
f (2)  (2  1)( 2  2)  0
f (4)  (4  1)( 4  2)  0
E ( f (2)) , E ( f (4))
E ( f ( x))
E ( f (2)) , E ( f (4))
同じアイテムに評価した数 1
6
マルチパーティ秘匿積集合
[Kissner 2005]
{1, 2,3}
( x  1)( x  2)( x  3)
多項式の積
{1,2,4}
{1,4,5}
( x  1)( x  2)( x  4)
( x  1)( x  4)( x  5)
P( x)  ( x  1)3 ( x  2) 2 ( x  3)( x  4) 2 ( x  5)
1階微分
2人以上で共通
d (1)
P ( x)  ( x  1) 2 ( x  2)( x  4)()
dx
(1)
2階微分
3人以上で共通
d 2 ( 2)
P ( x)  ( x  1)()
2
dx
( 2)
P (1)  0 P ( 2) (5)  0
｛1｝は3人が共通して持つ値
P (1)  0 P ( 2) (2)  0
｛2｝は2人が共通して持つ値
7
秘匿多項式評価
{1, 2,3}
{1,3,5}
{1,2,4}
( x  1)( x  2)( x  3)
( x  1)( x  3)( x  5)
( x  1)( x  2)( x  4)
d 2 ( 2)
P ( x)  ( x  1)()
2
dx
提案手法
0 , r1 , r2 , r3 , r4
従来手法
( 2)
P ( x)
P(1)( 2) , P(2)( 2) , 
8
評価
0.9
0.8
SCF similarity
コサイン尺度
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
0
50
100
相関係数=0.922
150
200
250
300
350
Proposed
similarity
2者間秘匿積集合
9
まとめ
Ι結論
Ι他のユーザとの類似度に2者間秘匿積集合を使用
Ιマルチパーティ秘匿積集合を改良し、複数のユーザ間で
集合の交わりの大きさを算出
Ι今後の課題
Ι秘匿積集合プロトコルの他分野への応用
Ι提案手法のコストの削減
10
11
評価 通信量
各プレーヤは定義域{1,…,50}，サイズ10の集合を持つ
暗号の鍵の長さ 1024bit
暗号文のサイズ 682byte
評価 計算量
Windows Vista SP1，2.66GHz，Core 2 Quad
暗号化 5961
暗号文 27,085