秘匿リストマッチングプロトコルとその応用

Presentation on theme: "秘匿リストマッチングプロトコルとその応用"— Presentation transcript:

1 秘匿リストマッチングプロトコルとその応用
菊池浩明　◎香川大介 東海大学大学院 工学研究科

2 背景：個人情報の保護と共有 疫病が発生した際,互いの持つ個人情報を出すことなく感染潜伏者を探し出したい

3 従来研究 秘匿共通集合暗号計算プロトコル Freedman et al. ,Eurocrypt2004
お互いの要素を秘密にしたまま共通集合要素を見つけ出す Client Server 散歩 読書 ネットサーフィン 料理 ネットサーフィン 写真 ネットサーフィン

4 高速化：ハッシングによる分割 分割前 k=6 ハッシング 分割後

5 問題：どちらの分割がよいか? Ｂ＝3 Ｂ＝２ 不均一 によるオーバヘッド

6 本研究の目的 それをするためには実装に基づく評価が必要 目的→最適な分割　　を求める

7 平衡化ハッシュ割当 Azar et al. , “Balanced allocations”,SIAM,1999 最大割当数
　にするアルゴリズム

8 我々のアプローチ:ランダム割当 の二項分布 Ｍ X どのくらい悪くなるのか *平衡化に比べて どのくらいの効果か？

9 秘匿共通集合暗号計算プロトコル[1] Client X=｛2,3｝ Server Y=｛2,4｝ 代入 復号

10 解析 分割サイズの最大値 最適分割 処理時間 通信コスト

11 解析1：分割時のリスト最大値 単純なハッシングによる偏り 最大値Mがzσを超える期待値が1となる 1％

12 解析1：分割リスト長 リストの最大値M 60＞100/2 40＞100/4 リストの分割数B

13 解析2：最適な分割 ランダムハッシングによる割り当てのリスト最大長 実測値に基づいた, 計算時間をT(k)について ここで 　 を満たす

14 解析2：評価値 処理時間[ms] リストの分割数B k=100 B=4近くでコストが最小化
この時の平衡化と単純ハッシングの差 =350(=17%) リストの分割数B

15 パフォーマンス評価 処理時間[ms] 9700 7000 リストのサイズｋ

16 通信コスト 通信コスト[bit] リストのサイズｋ

17 実装 Java JDK1.5.0を用いて,クライアントサーバ モデルで実装した 変形ElGamal暗号 測定環境 WindowsXP
Pentium4 3.6GHz Java JDK1.5.0を用いて,クライアントサーバ　　　モデルで実装した 変形ElGamal暗号

18 実験 被験者9人に50項目2択のアンケートに答えてもらい,重なりを調べた

19 結論 課題 お互いに持つ集合を秘匿したまま,重なり合う要素を求める方法について実装し 単純ハッシング時における最適な分割数をもとめた
多ユーザへの対応 ハッシュ平衡化の効果の計測 ほかに利用できる応用例 課題