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