秘匿積集合プロトコルを利用した プライバシ協調フィルタリングの提案 秘匿積集合プロトコルを利用した　　プライバシ協調フィルタリングの提案 ◎木澤寛厚　磯崎邦隆　菊池浩明　　　　 　東海大学 工学研究科 情報理工学専攻

背景 ネットショップ 商品の量が多い 見つからないorz

情報推薦システム 他の利用者の嗜好に 基づき，利用者の嗜好を予測 利用者の嗜好に合う 商品を提示する amazon 他の利用者の嗜好に　基づき，利用者の嗜好を予測 利用者の嗜好に合う　商品を提示する http://www.amazon.co.jp/

推薦システム：問題点 S 嗜好情報が漏洩せず 推薦結果を出したい B’ A B C A B C MAC 嗜好情報漏洩の可能性 ？ サーバ Windows C A B C 嗜好情報が漏洩せず 推薦結果を出したい

従来研究 Cannyの方式[1] 秘匿CF方式[5] 莫大な計算コスト・通信コスト 共役勾配法を用いて特異値分解を準同型性暗号で行う 準同型性暗号を用いて協調フィルタリングを行う 欠損値を秘匿するためにO(n2)の通信コスト ユーザ数943人，アイテム数1682個で1TBの通信コスト 莫大な計算コスト・通信コスト

目的 秘匿積集合プロトコル[3]というアプローチで、個人情報を秘匿したまま嗜好を予測する　手法を提案する 計算コスト・通信コストを削減する

要素技術：一覧 協調フィルタリング方式(CF方式) 2者間秘匿積集合プロトコル 準同型性暗号 嗜好の評価値を予測する 一般的な推薦システムに利用されている技術 2者間秘匿積集合プロトコル お互いが評価したアイテムの数s(ui,uj)を得る お互いどのアイテムを評価しているか秘密 準同型性暗号

要素技術： 協調フィルタリング方式(CF方式) アイテム i1 i2 i3 i4 類似度S 平均 a ＊ 2 5 3.5 b 1 3 c 0.88 d 0.96 2.7 ユーザ bとの類似度・bの評価+dとの類似度・dの評価 ＊=aの平均＋ 類似度の総和 0(1-2)+0.96(2-2.7) =3.5 +　　　　　　　　　　　　　　 =　2.8 0+0.96

要素技術： 2者間秘匿積集合プロトコル A={2,3} B={1,2} a b 復号 0の数=|A∩B|=1

提案方式 1/3 2者間秘匿積集合プロトコルを使用し、 s(a,*)の値をそれぞれ出す i1 i2 i3 i4 s(a,*) a ＊ 2 5 b 1 3 c d i1 i2 i3 i4 s(a,*) a ＊ 2 5 b 1 3 c d 2者間秘匿積集合プロトコルを使用し、　s(a,*)の値をそれぞれ出す 閾値Tを決める、T≦s(a,*)の式を満たすユーザの集合をBとする 今回はT=1、B={c,d}

提案方式 2/3 -1 i1 i2 i3 i4 c 2.5 2 3 i1 i2 i3 i4 a ＊ 2 5 c a i1 i2 i3 i4 n out of 1 OT a i1 i2 i3 i4 d 2 1 2.7 5 n out of 1 OT d

提案方式 2/3 -2 i1 i2 i3 i4 c 1 i1 i2 i3 i4 a ＊ 2 5 c a i1 i2 i3 i4 d 1 d 1 i1 i2 i3 i4 a ＊ 2 5 c n out of 1 OT a i1 i2 i3 i4 d 1 n out of 1 OT d

提案方式 3/3 i1 i2 i3 i4 類似度s(a,*) 平均 a ＊ 2 5 3.5 c 3 1 2.5 d 2.7 ＊=aの平均＋ 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・通信コスト・計算コストを調べる ユーザ数 943人 アイテム数 1682個 総評価数 暗号文のサイズ べき乗計算 100,000個 256byte 1764(ms)

精度 Proposed SCF[3] 推薦者数

計算コスト 570000s 6.5日 337s 5分 推薦者数

通信コスト 104.3GB 0.8GB 推薦者数

通信コスト・計算コストまとめ ※類似度s(ui,uj)が被推薦者に漏れる SCF(従来) 提案方式 精度 × ○ 通信コスト 計算コスト 漏洩する情報 ×　※ ※類似度s(ui,uj)が被推薦者に漏れる

考察：類似度 1/2 従来方式 →コサイン尺度 提案方式 →積集合の大きさ 提案方式の精度が 　　　なぜ向上したのか検討

考察：類似度 2/2 相関係数=0.922 →提案方式の類似度はユーザ間の 　　　類似度を反映している コサイン尺度 交わりの大きさ

考察： 2者間秘匿積集合プロトコル 2者間秘匿積集合プロトコルのコスト 実験ではこれらのコストを除いている 考察： 　2者間秘匿積集合プロトコル 2者間秘匿積集合プロトコルのコスト 推薦者の評価値の数を秘匿する場合，　　　1推薦者あたりnの計算コストが生じる ユーザ数943，アイテム数1682だと　　　　　　　　1推薦者あたり48分計算コストが生じる 通信コストは(m-1)n ユーザ数943，アイテム数1682だと682GB 実験ではこれらのコストを除いている 　→　セキュリティとコストのトレードオフ

結論 秘匿共通部分評価を利用した新しい協調フィルタリング方式を提案した 精度が良くなった 通信コストを1/130に削減した 類似度と交わりの数の間に強い相関 通信コストを1/130に削減した ただしOTの秘匿積集合プロトコルのコストは入っていない 計算コストを1/1700に削減した

今後の課題 2者間秘匿積集合プロトコルのコストの　詳しい検証 OTのコストの検証

紛失通信 クライアント サーバ 25

提案方式 D