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

定理(GHR署名)の証明のアイデア

検証鍵 vk = (N, s, h)のもとで、σ*がm*の妥当な署名であるためには、e* = h(m*)について、

• σ*^e* ≡ s　(mod N)

でなければならない。

• 強RSA問題(N,s)の困難性から、このような(m*,σ*)を直接に構成するのは困難。また、
• 署名オラクルからのデータ(m_i, σ_i)をもとに(m*,σ*)を作るのは、
  • e_i = h(m_i) を e* = h(m*) に関連付ける必要があるが、
  • ハッシュ関数hがgcd intractable なので無理そう。

定理(GHR署名)の証明

ある偽造者FがGHR署名を非適応的選択文書攻撃において偽造するとする。
偽造者Fが発する非適応的署名クエリの回数の上限をtとする。

Fを用いてGenRSAに対する強RSA仮定を破るアルゴリズムAを構成する：

アルゴリズムA: (N, s)を入力として、
※　(σ')^e* ≡ s (mod N) となる(σ',e*)を計算したい。

• h ← H_k
• 偽造者Fを起動し、署名クエリ(m₁,...,m_t)を受け取る。
  • i ∈ [1..t] : e_i = h(m_i)
  • e = Π_i=1..t e_i, 　s' = s^e mod N
  • i ∈ [1..t] : σ_i = s^{Π_j≠i e_j} mod N
    • ※ s' = σ_i^e_i mod N.
  • (vk = (N, s'), σ₁,...,σ_t)をFに返答する
• Fが(m*,σ*)を出力して停止したら、
  • e* = h(m*)
    • ※ (m*,σ*)が正しければ、(σ*)^e* = s' = s^e.
  • gcd(e*, e) ≠ 1: アボート.
  • else 補題(CS)によって、(σ')^e* ≡ s (mod N) となるσ'を計算し、(σ', e*)を出力。

アルゴリズムAの解析:
アボートが起きない限り、AのFに対するシミュレーションは完ぺき。よって、

• Pr[ Aが強RSA問題を解く ] ≧ Pr[ FがGHR署名を非適応的に偽造 ] - Pr[ Aがアボート].

仮定より、hは gcd intractable なので、アボートの確率はネグリジブル。よって、

• Pr[ Aが強RSA問題を解く ] ≧ Pr[ FがGHR署名を非適応的に偽造 ] - (ネグリジブル).
• Pr[ FがGHR署名を非適応的に偽造 ] ≦ Pr[ Aが強RSA問題を解く ] + (ネグリジブル).

強RSA仮定より右辺はネグリジブル。

Q.E.D.

上へ

---