帰着と確率
よく使う手で
- 方式Sに対しての攻撃能力を持つ敵Aが存在
- 敵AはType IかType IIのどちらかだ
- よって敵Aが存在するなら, 方式Sに対しての攻撃能力を持つType Iの敵A1が存在する or 方式Sに対しての攻撃能力を持つType IIの敵A2が存在する.
- 方式Sに対しての攻撃能力を持つType Iの敵A1が存在するなら, DL問題に対しての攻撃能力を持つ敵B1が存在する
- 方式Sに対しての攻撃能力を持つType IIの敵A2が存在するなら, ハッシュ関数に対しての攻撃能力を持つ敵B2が存在する
という論法がある.
このとき, 定理としては
- でDL仮定が成立しハッシュ関数が安全ならば, 方式Sが安全である.
- 方式Sに対しの攻撃能力を持つ敵Aが存在するならば, DL問題に対しての攻撃能力を持つ敵B1が存在する or ハッシュ関数に対しての攻撃能力を持つ敵B2が存在する
のどちらかの形を取る.
ここで, 敵B1が存在する or 敵B2が存在するというときに, その敵が実際に構成出来ることまで含まれるという立場を取ると確率評価が変わってくるんじゃないのかという話で昨日今日と研究室で議論が起きた.
構成の立場を取ると, にするか, (敵Aがどちらのタイプかを見分けるためにテストする必要があるので) とが変わってくる *1.
存在だけでいいなら, . ただしこの存在という立場では, 敵B1と敵B2のどちらを構成出来たのか分からない.
ややこしいことこの上ない.
定理の言明が構成できる
であっても後者の確率評価をしていることもあるので注意が必要.
*1:Camenish and LyshanskayaのCL署名 (sRSA仮定の方) だと, 証明で敵Aがどのタイプなのか調べるための統計的検査の時間を見積もっている. 分母を4にしているタイプの証明は数本で見た