定理(XCR署名)の証明 - 暗号理論教室

定理(XCR)の証明

XCR署名に対する任意のPPT偽造者をFとする。
Fを用いて計算DH問題を解くPPTアルゴリズムCを構成する。

アルゴリズムC: U=g^u, V=g^vを入力として、

• B = V, X₀ = U
• B, X₀を入力としてFを起動する：
  • FがオラクルGへ問い合わせ(Y,m)を発したら、
    • G[Y,m]が未定義なら、e ← {0,1}^l, G[Y,m]=e
    • G[Y,m]を返答する。
  • Fが署名オラクルBへ問い合わせmを発したら、
    • s ← Z_q, e ← {0,1}^l, Y = g^s / B^e
    • G[Y,m] = e とする。（ただし、G[Y,m]がすでに定義されていたらアボート。）
    • Yを返答し、FよりXを受け取って、σ=X^s を返す。
    • （※ (Y B^G(Y,m))^x = (Y B^e)^x = (g^s)^x = σ ）
• Fの出力を(Y₀, m₀, σ₀)とする。
  • （※ (Y₀, m₀)は、署名オラクルのシミュレーション時にCによって用いられておらず、かつFによりオラクルGへすでに問い合わされているとしてよい。）
• B, X₀を入力として、Fをもう一度起動する、ただし、
  • Fが(Y₀, m₀)をオラクルGへ問い合わせるまでは、先のFの実行と同一のランダムテープを用いて全く同様に処理する。
  • Fが(Y₀, m₀)をはじめてオラクルGへ問い合わせたら、以降、新しいランダムテープに切り替えて、
    • e' ← {0,1}^l, G[Y₀,m₀] = e' を返答する。
  • 後は新しいランダムテープを用いて先のFの実行と全く同様に処理する。
• Fの出力を(Y₀, m₀, σ₀')とする。
• e ≠ e' ならば、(σ₀ / σ₀' )^1/(e-e') を出力して停止する。

[アルゴリズムCの解析]:

• Fがネグリジブルでない成功確率をもつならば、2回とも偽造に成功する確率はネグリジブルでない。このとき、
  • (Y₀ B^e)^u = σ₀
  • (Y₀ B^e')^u = σ₀'
• これより、
  • V^u = B^u = (σ₀ / σ₀' )^1/(e-e').

Q.E.F.
上へ

---