定理(Hash-and-Sign)の証明 - 暗号理論教室

定理(Hash-and-Sign)の証明のアイデア

メッセージ m の、vk' = (vk, k)に関する署名は

• σ ← Sign(sk, H_k(m)).

偽造者Fが、 σ' ← Sign(sk, H_k(m')) を与えられて、あるm (≠m')の署名σを作るには、

• H_k(m) = H_k(m') となる m (≠m') を計算し、(m, σ=σ')とするか、もしくは、
• ベースの署名スキームΩ=(Gen,Sign,Verify)の、H_k(m)（≠H_k(m'))についての、署名σを偽造する

しかなさそう。

定理(Hash-and-Sign)の証明

Hash-and-Sign署名Ω'に対する任意の効率的な偽造者をFとする。
試行CMA_Ω',Fにおいて、vk' = (vk, k)を入力として偽造者Fが起動されたとき、

• イベントcoll_Ω',F:
  • 『偽造者Fが署名オラクルに問い合わせた、あるメッセージm'について、 H_k(m) = H_k(m'). 』

Fの成功確率を、coll_Ω',Fの発生/不発生について分解すると、

• Pr[Fが成功] = Pr[Fが成功 ∧ coll_Ω',F] + Pr[Fが成功 ∧ ￢coll_Ω',F]
  • ≦ Pr[coll_Ω',F] + Pr[Fが成功 ∧ ￢coll_Ω',F].

主張1 Pr[coll_Ω',F] はネグリジブル。
証明
Fを用いてハッシュ関数Hに対する攻撃者Cを構成：
攻撃者C: k を入力として、

• Q = {}, (vk, sk) ← Gen
• vk' = (vk, k) を入力としてFを起動：
  • Fから署名オラクルに対する問い合わせ m' を受け取ったら、
    • Q = Q ∪ m'とし, σ' ← Sign(sk, H_k(m')) を返答する。
• Fが出力(m, σ)で停止したら、
  • Qに属するm'で、H_k(m) = H_k(m') となるm'(≠m)を検索し、(m, m') を出力して停止。

CのFに対するシミュレーションは完ぺきなので、

• Pr[Cが衝突(m,m')を発見] = Pr[coll_Ω',F].

仮定よりCは衝突困難なので、これはネグリジブル。
q.e.d.

主張2 Pr[Fが成功 ∧ ￢coll_Ω',F] はネグリジブル。
Fを用いてベースの固定長メッセージの署名スキームΩに対する攻撃者Aを構成：
攻撃者A: vk を入力として、

• k ← {0,1}ⁿ
• vk' = (vk, k) を入力としてFを起動：
  • Fから署名オラクルに対する問い合わせ m' を受け取ったら、
    • H_k(m')を自身の署名オラクルに問い合わせ、返答σ'をえる。
    • σ'を応答する。
• Fが出力(m, σ)で停止したら、
  • (H_k(m), σ) を出力して停止する。

￢coll_Ω',Fのとき、任意のm'について、H_k(m')≠H_k(m)なので、

• Pr[Aが成功] = [Fが成功 ∧ ￢coll_Ω',F].

仮定よりAはEUF-CMA安全なので、これはネグリジブル。
q.e.d.

主張1と主張2より、Pr[Fが成功]はネグリジブル。
Q.E.D.
上へ

---