帰着と確率 - 186 @ hatenablog

よく使う手で

方式Sに対して $(t,\epsilon)$ の攻撃能力を持つ敵Aが存在
敵AはType IかType IIのどちらかだ
よって敵Aが存在するなら, 方式Sに対しての攻撃能力を持つType Iの敵A1が存在する or 方式Sに対しての攻撃能力を持つType IIの敵A2が存在する.
1. 方式Sに対して $(t',\epsilon')$ の攻撃能力を持つType Iの敵A1が存在するなら, DL問題に対して $(t',\epsilon'')$ の攻撃能力を持つ敵B1が存在する
2. 方式Sに対して $(t'',\epsilon'')$ の攻撃能力を持つType IIの敵A2が存在するなら, ハッシュ関数に対して $(t'',\epsilon'')$ の攻撃能力を持つ敵B2が存在する

という論法がある.
このとき, 定理としては

$(t',\epsilon')$ でDL仮定が成立しハッシュ関数が $(t'',\epsilon'')$ 安全ならば, 方式Sが $(t,\epsilon)$ 安全である.
方式Sに対し $(t,\epsilon)$ の攻撃能力を持つ敵Aが存在するならば, DL問題に対して $(t',\epsilon'')$ の攻撃能力を持つ敵B1が存在する or ハッシュ関数に対して $(t'',\epsilon'')$ の攻撃能力を持つ敵B2が存在する

のどちらかの形を取る.
ここで, 敵B1が存在する or 敵B2が存在するというときに, その敵が実際に構成出来ることまで含まれるという立場を取ると確率評価が変わってくるんじゃないのかという話で昨日今日と研究室で議論が起きた.
構成の立場を取ると, $\epsilon'=\epsilon''=\epsilon/4$ にするか, (敵Aがどちらのタイプかを見分けるためにテストする必要があるので) $t'$ と $t''$ が変わってくる *1.
存在だけでいいなら, $\epsilon'=\epsilon''=\epsilon/2$ . ただしこの存在という立場では, 敵B1と敵B2のどちらを構成出来たのか分からない.

ややこしいことこの上ない.
定理の言明が構成できるであっても後者の確率評価をしていることもあるので注意が必要.

*1:Camenish and LyshanskayaのCL署名 (sRSA仮定の方) だと, 証明で敵Aがどのタイプなのか調べるための統計的検査の時間を見積もっている. 分母を4にしているタイプの証明は数本で見た