定理(NACMA+Σ)の証明 - 暗号理論教室

定理(NACMA+Σ)の証明のアイデア

検証鍵 vk' = (vk, pk_Σ)のもとで、
z = (σ*,x*,y*)がm*の(NACMA+Σ)署名による妥当な署名であるためには、

• Det(pk_Σ, x*, H(m*), y*) ∧ Verify(vk, x*, σ*)

でなければならない。

このとき、

• x* はメッセージm* とは独立に生成できるので、x*を守る署名σ*は非適応的な攻撃に対して安全であればよい。
• H(m*)は偽造者にとっても値をコントロールできないので、Σプロトコルの特殊健全性より、
  • x*,H(m*)に対し妥当なy*を作れるのは、sk_Σを知っている正当な署名者のみ。

定理(NACMA+Σ)の証明

Ω'に対する任意の効率的な偽造者をFとする。Fの署名クエリ回数の上界をt(n)とする。
CMA_Ω',F(n)において、

• Fは第i回目の署名クエリとして m_i を発し、その応答として z_i = (σ_i,x_i,y_i) を得た。
• Fは (m*, z = (σ*,x*,y*)) を偽造署名として出力した。

とする。

Type1 : 『ある j について、x* = x_j。』
Type2 : 『どんな i についても、x* ≠ x_i。』

(Type1の偽造が発生するならば)
ある効率的な攻撃者MがΣの特別健全性を破る。

攻撃者M: Σプロトコルの公開鍵 pk_Σ を入力として、

• ※ c ≠ c' である2つの説得的なトランスクリプト(x,c,y), (x,c',y')を生成したい。
• (vk, sk) ← Ω.Gen
• vk' = (vk, pk_Σ) を入力としてFを起動する。
• Fから署名オラクルに対するi番目の問い合わせm_iを受け取ったら、
  • (x_i,y_i) ← Sim(pk_Σ, H(m_i))
  • σ_i ← Sign(sk, x_i)
  • z_i = (σ_i, x_i, y_i)を応答する。
• Fが(m*, z = (σ*,x*,y*))を出力して停止したら、
  • x* = x_j となる j を検索する。
  • ※ Type1の仮定より、このような j は必ず存在する。
  • (x*, H(m_j), y_j), (x*, H(m*), y*) を出力して停止する。

攻撃者Mの解析：

• ΣプロトコルのHVZK性より、Fに与えている署名z_iは、真の署名と識別不可能。
• m* ≠ m_jとHの衝突困難性より、H(m*)≠H(m_j).

よって、

• Pr[MがΣプロトコルの特殊健全性を破る] ≧ Pr[FがType1の偽造に成功] - (ネグリジブル).
• ∴ Pr[FがType1の偽造に成功] ≦ (ネグリジブル).

(Type2の偽造が発生するならば)
ある効率的な偽造者BがΩを非適応的選択文書攻撃で破る。

偽造者B: Ωの検証鍵 vk を入力として、

• ※ 検証鍵vkに関する署名を非適応的に偽造したい。
• (pk_Σ, sk_Σ) ← Σ.Gen(1ⁿ)
• i ∈ [1..t(n)] : (x_i, r_i) ← Com(pk_Σ)
• x₁, ... , x_t をチャレンジャーに出力し、vk, σ₁, ... , σ_t を受け取る。
• vk' = (vk, pk_Σ) を入力としてFを起動する。
• Fから署名オラクルに対するi番目の問い合わせm_iを受け取ったら、
  • y_i ← Res(sk_Σ, r_i, H(m_i))
  • z_i = (σ_i, x_i, y_i) を返答する。
• Fが(m*, z = (σ*,x*,y*))を出力して停止したら、
  • (x*, σ*)を出力して停止する。
  • ※ Type2の仮定より、x* ≠ x_i 　(∀i).

偽造者Bの解析：

• 明らかに、BのFに対するシミュレーションは完ぺきである。
• Fの出力するType2の偽造署名(m*, z = (σ*,x*,y*))について、(x*, σ*)はΩの偽造署名として妥当である。

よって、

• Pr[BがΩの署名の偽造に成功] = Pr[FがType2の偽造に成功].
• ∴ Pr[FがType2の偽造に成功] ≦ (ネグリジブル).

Q.E.D.

上へ

---