slide

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

Download Report