定理(ShortSignatureFull)の証明 - 暗号理論教室

定理(ShortSignatureFull)の証明のアイデア

検証鍵 vk = (g₁, g₂, u = g₂^x, v = g₂^y)のもとで、
(σ*,r*)がm*のShortSignatureFullによる妥当な署名であるためには、

• σ* = g₁^1/(x+m*+yr*)

でなければならない。

このとき、σ* はメッセージ w* = m* + yr* の（ベーススキームである）ShortSignatureの署名となっている。

• w* が fresh ならば、ShortSignatureが破られている。
• w* が non-fresh ならば、ある署名オラクルへの問い合わせ(m_i, (σ_i, r_i))について、
  • m* + yr* = m_i + yr_i　より
  • 離散対数 y = (m* - m_i) / (r_i - r*) が計算できてしまう。

定理(ShortSignatureFull)の証明

ShorSignatureが非適応的選択文書攻撃で安全であるならば、
ShortSignatureFullは適応的選択文書攻撃で安全であることを示せばよい。

ある偽造者AがShortSignatureFull Ωを (t, q_S, ε)-break するとする。

CMA_Ω,A(n)において、

• Fは第i回目の署名クエリとして m_i を発し、その応答として(σ_i,r_i)を得た。(w_i := m_i + y r_i)
• Fは (m*, (σ*, r*)) をメッセージと偽造署名の組として出力した。(w* := m* + y r*)

とする。

Type1 : 『ある j について m_j = -x』 OR 『どんな i についても w* ≠ w_i』
Type2 : 『どんな j についても、m_j ≠ -x』 AND 『ある i について w* = w_i』

(Type1の偽造が発生するならば)
Aを用いてShortSignatureを非適応的選択文書攻撃で破る偽造者B₁を構成する：

偽造者B₁: 1ⁿを入力として、

• ※ B₁の目的はShortSignatureを非適応的に偽造すること。
• w₁,...,w_qS ← Z_p* を署名を要求するメッセージとしてチャレンジャーに送る。
• チャレンジャーからvk=(g₁,g₂,u), σ₁,...,σ_qSを受け取る。
• ※ e(σ_i, ug₂^w_i) = e(g₁, g₂).
• y ← Z_p*, vk = (g₁, g₂, u, v=g₂^y)
• vkを入力として偽造者Aを起動する。
  • Aから i 番目の署名クエリ m=m_i を受け取ったら、
  • g₂^-m =^? u : Bはvkの秘密鍵x=-mを入手したので、どのようにもShortSignatureを偽造可能。
  • else r_i = (w_i - m) / y
    • r_i = 0 ならばアボート。そうでないならば、(σ_i, r_i)を返答する。
    • ※ e(σ_i, ug₂^m(g₂^y)^r_i ) = e(σ_i, ug₂^w_i) = e(g₁, g₂).
• Aが出力(m*, σ*, r*)で停止したら、
  • (w* = m* + y r*, σ*) を出力して停止。
  • ※ e(σ*, ug₂^w*) = e(σ*, ug₂^m*v^r*) = e(g₁, g₂).
  • ※ Type1の仮定より、w* ≠ w_i　(∀i).

攻撃者B₁の解析：

• アボートが起きなければ、Aに対するシミュレーションは完ぺき。
• アボートが起きる確率は q_S / p.
• ケース仮定より、どんな i についても w* ≠ w_i。よって、B₁の偽造は存在的偽造として妥当。

以上より、

• Pr[B₁が偽造に成功 | Type1] = ε - q_S/p.

(Type2の偽造が発生するならば)
Aを用いてShortSignatureを非適応的選択文書攻撃で破る偽造者B₂を構成する：

偽造者B₂: 1ⁿを入力として、

• ※ B₂の目的はShortSignatureを非適応的に偽造すること。
• w₁,...,w_qS ← Z_p* を署名を要求するメッセージとしてチャレンジャーに送る。
• チャレンジャーからvk=(g₁,g₂,u), σ₁,...,σ_qSを受け取る。
• ※ e(σ_i, ug₂^w_i) = e(g₁, g₂).
• x ← Z_p*, vk = (g₁, g₂, g₂^x, u) 　※ u = g₂^y
• vkを入力として偽造者Aを起動する。
  • Aからi番目の署名クエリm=m_iを受け取ったら、
    • r_i = (x + m) / w_i とし、(σ_i^1/r_i, r_i)を返答する。
    • ※ e(σ_i^1/r_i, g₂^xg₂^mu^r_i ) = e(σ_i^1/r_i, g₂^r_iw_iu^r_i) = e(σ_i, g₂^w_iu) = e(g₁, g₂).
• Aが出力(m*, σ*, r*)で停止したら、
  • g₂^m* u^r* = g₂^m_i u^r_i となるiを検索する。
  • ※ Type2の仮定より、そのような i は存在する。
  • 署名鍵xとy = (m* - m_i) / (r_i - r*) (= log_g2(u)) を用いてどのようにもShortSignatureを偽造可能。

攻撃者B₂の解析：

• ケース仮定より、上のような i （w_i = w*となるi）は必ず見つかる。

よって、

• Pr[B₂が偽造に成功 | Type2] = 1.

Q.E.D.

上へ

---