命題(双子計算DH仮定)の証明 - 暗号理論教室

命題(双子計算DH仮定)の証明

群生成アルゴリズムGenGの双子計算DH問題を解く任意の効率的アルゴリズムをAとする。
Aを用いてGenGの計算DH問題を解くアルゴリズムBを構成する：

アルゴリズムB: (X, Y)を入力として、

• r, s ← Z_q
• X₁ = X, X₂ = g^s/X₁^r
  • ※ s = x₂ - x₁r
• (X₁, X₂, Y)を入力として、Aを起動：
  • Aが2dhp(X₁,X₂,・,・,・)オラクルへ問い合わせ(Y',Z'₁,Z'₂)を発したら、
    • 『(Z'₁)^rZ'₂ =^? Y'^s』を返答する。
    • ※ (Z'₁)^rZ'₂ = Y'^s ⇔ (Z'₁/Y'^x1)^r = Y'^x2/Z'₂
    • ※ Z'₁/Y'^x1 ≠ 1 ならば右辺の成り立つ確率は高々1/q.　（注：(X₁,X₂,Y)は、したがってAのviewは、rに独立。）
• Aが出力(Z₁,Z₂)で停止したら、
  • (Z₁)^rZ₂ =^? Y^sならばZ₁を（そうでなければ⊥を）出力して停止。

アルゴリズムBの解析:

• Bによる2dhpオラクルのシミュレーションは、ネグリジブルな例外を除いて完ぺき。
• よって、Pr[ Bが計算DH問題を解く ] ≧ Pr[ Aが双子計算DH問題を解く ] - (ネグリジブル).

Q.E.D.

上へ

---