秘匿積集合プロトコルの 推薦システムへの応用

Presentation on theme: "秘匿積集合プロトコルの 推薦システムへの応用"— Presentation transcript:

1 秘匿積集合プロトコルの 推薦システムへの応用
7ADRM003　　磯崎邦隆 指導教員　　菊池浩明　教授

2 秘匿積集合プロトコル プレーヤが持つリストを秘匿したまま 共通な要素のみを抽出する 1,6 公開 2 1 3,5,6 公開 秘密 1 1 1
2人で共通な値 1,6 公開 2 プレーヤA プレーヤB プレーヤC 3人で共通な値 2人で共通な値 1 3,5,6 公開 1 2 3 3 4 5 5 7 秘密

3 情報推薦システム … Webショップ 腕時計 評価 腕時計 14596件 カメラ 10261件 ソファ 2784件 ユーザD ユーザC
腕時計　14596件 Webショップ カメラ　10261件 ソファ　2784件 評価 … 腕時計 ユーザD ユーザC ユーザA ユーザB

4 インターネット定点観測 観測機関 A 観測機関 B 観測機関 C 12台中6台のセンサで観測された ユニークホスト数 ユニークホスト数
ユニークホスト数　 観測機関 C 観測したセンサ台数 [福野 2006]

5 研究目的 定点観測 推薦システム 公開 2 1 3 公開 秘密 2者間秘匿 積集合の使用 マルチパーティ 秘匿積集合の改良 1 1 1 2
2人で共通な値 公開 2 2者間秘匿 積集合の使用 ユーザA ユーザB ユーザC 3人で共通な値 2人で共通な値 1 3 公開 マルチパーティ 秘匿積集合の改良 1 2 3 3 4 5 5 7 秘密

6 2者間秘匿積集合 ユーザA ユーザB アイテム 1 2 3 4 評価 ○ アイテム 1 2 3 4 評価 ○ 同じアイテムに評価した数 1
[Freedman 2004] ユーザA ユーザB アイテム 1 2 3 4 評価 ○ アイテム 1 2 3 4 評価 ○ 同じアイテムに評価した数　1

7 マルチパーティ秘匿積集合 多項式の積 1階微分 2人以上で共通 2階微分 3人以上で共通 ｛1｝は3人が共通して持つ値
[Kissner 2005] 多項式の積 1階微分 2人以上で共通 2階微分 3人以上で共通 ｛1｝は3人が共通して持つ値 ｛2｝は2人が共通して持つ値

8 秘匿多項式評価 提案手法 従来手法

9 評価 コサイン尺度 2者間秘匿積集合 相関係数=0.922

10 まとめ 結論 今後の課題 他のユーザとの類似度に2者間秘匿積集合を使用
マルチパーティ秘匿積集合を改良し、複数のユーザ間で集合の交わりの大きさを算出 今後の課題 秘匿積集合プロトコルの他分野への応用 提案手法のコストの削減

11

12 評価　通信量 各プレーヤは定義域{1,…,50}，サイズ10の集合を持つ 暗号の鍵の長さ　1024bit　　　暗号文のサイズ　682byte

13 評価　計算量 Windows Vista SP1，2.66GHz，Core 2 Quad 暗号化　5961　　　暗号文　27,085