秘匿リストマッチングプロトコルとその応用 菊池浩明 ◎香川大介 東海大学大学院 工学研究科
背景：個人情報の保護と共有 疫病が発生した際,互いの持つ個人情報を出すことなく感染潜伏者を探し出したい
従来研究 秘匿共通集合暗号計算プロトコル Freedman et al. ,Eurocrypt2004 お互いの要素を秘密にしたまま共通集合要素を見つけ出す Client Server 散歩 読書 ネットサーフィン 料理 ネットサーフィン 写真 ネットサーフィン
高速化：ハッシングによる分割 分割前 k=6 ハッシング 分割後
問題：どちらの分割がよいか? Ｂ＝3 Ｂ＝２ 不均一 によるオーバヘッド
本研究の目的 それをするためには実装に基づく評価が必要 目的→最適な分割 を求める
平衡化ハッシュ割当 Azar et al. , “Balanced allocations”,SIAM,1999 最大割当数 にするアルゴリズム
我々のアプローチ:ランダム割当 の二項分布 Ｍ X どのくらい悪くなるのか *平衡化に比べて どのくらいの効果か？
秘匿共通集合暗号計算プロトコル[1] Client X=｛2,3｝ Server Y=｛2,4｝ 代入 復号
解析 分割サイズの最大値 最適分割 処理時間 通信コスト
解析1：分割時のリスト最大値 単純なハッシングによる偏り 最大値Mがzσを超える期待値が1となる 1％
解析1：分割リスト長 リストの最大値M 60＞100/2 40＞100/4 リストの分割数B
解析2：最適な分割 ランダムハッシングによる割り当てのリスト最大長 実測値に基づいた, 計算時間をT(k)について ここで を満たす
解析2：評価値 処理時間[ms] リストの分割数B k=100 B=4近くでコストが最小化 この時の平衡化と単純ハッシングの差7800-6450=350(=17%) リストの分割数B
パフォーマンス評価 処理時間[ms] 9700 7000 リストのサイズｋ
通信コスト 通信コスト[bit] リストのサイズｋ
実装 Java JDK1.5.0を用いて,クライアントサーバ モデルで実装した 変形ElGamal暗号 測定環境 WindowsXP Pentium4 3.6GHz Java JDK1.5.0を用いて,クライアントサーバ モデルで実装した 変形ElGamal暗号
実験 被験者9人に50項目2択のアンケートに答えてもらい,重なりを調べた
結論 課題 お互いに持つ集合を秘匿したまま,重なり合う要素を求める方法について実装し 単純ハッシング時における最適な分割数をもとめた 多ユーザへの対応 ハッシュ平衡化の効果の計測 ほかに利用できる応用例 課題