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

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

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

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

でなければならない。

署名オラクルから、高々(q-1)個のメッセージm_iの署名について

• σ_i = g₁^1/(x+m_i*)

をもらっても、q-強DH問題が困難であるならば、σ* = g₁^1/(x+m*)を計算することはむずかしそう。

なぜならば、
予め指定された m_i の g₁^1/(x+m_i*) ならば（i=1..(q-1)）、

• g₂^(xi)　 (i = 0, 1,..., q)

を用いて計算できるから。

定理(ShortSignature)の証明

ある偽造者AがShortSignatureを (t, q_S, ε)-break するとする。
Aを用いて双線形群(G₁ , G₂)上の(q,t',ε)-強DH仮定を破るアルゴリズムBを構成する：

アルゴリズムB: (g₁,A₀,A₁,...,A_q)を入力として

• ※ A_i = g₂^(xi)　 (i = 0, 1,..., q)
• ※ あるc≠0について、g₁^1/(x+c)を求めたい。
• 1ⁿ を入力としてAを起動し、メッセージm₁,m₂,...,m_qSを受け取る。
  • q_S = q - 1 としてよい。（必要ならBがAの代わりにメッセージを生成する。）
• 受け取ったメッセージm_iたちに合わせて、検証鍵vkを作成する：
  • yを不定元として、(q-1)次多項式 f(y) = Π_i=1..(q-1) (y + m_i) = Σ_i=0..(q-1) α_iyⁱ を計算。
  • これらα_iを用いて、群要素 g₂' = Π_i=0..(q-1)A_i^α_i を計算。
    • ※ g₂' = g₂^f(x) = g₂^Π(x+m_i).
    • ※ 後に見るように g₂'の1/(x+m_i)乗は計算できる！
  • さらに、群要素 h = Π_i=1..qA_i^α_i-1 を計算。
    • ※ h = g₂^xf(x) = (g₂')^x.
    • ※ つまり、xを知らないのにg₂'をx乗できた。
  • g₁' = Ψ(g₂')
  • ※ g₁' = g₁^f(x).
• vk = (g₁', g₂', h) をAに送る（これは sk = x を陰に定義）。さらに、
• i ∈ [1..(q-1)] :
  • (q-2)次多項式 f_i(y) = f(y) / (y + m_i) = Σ_j=0..(q-2) β_jy^j を計算。
  • これらβ_jを用いて、群要素 S_i = Π_j=0..(q-2)A_j^β_j を計算。
  • ※ S_i = g₂^f_i(x) = (g₂')^1/(x+m_i).
  • σ_i = Ψ(S_i)
  • ※ σ_i = (g₁')^1/(x+m_i).
• σ₁, ... ,σ_q-1をAに送る。
• Aが出力(m*, σ*)で停止したら、
  • 多項式 f(y) を (y+m*) で割り算し、余り γ_-1 を求める: 　f(y) = γ(y) (y+m*) + γ_-1.
    • (q-2)次多項式 γ(y) の各係数を γ_i とする：　γ(y) = Σ_i=0..(q-2)γ_iyⁱ.
    • ※ m* はどのm_iとも異なるので、γ_-1 ≠ 0.
  • これらγ_i,γ_-1を用いて、群要素 w = (σ* Π_i=0..(q-2)Ψ(A_i)^-γ_i)^1/γ_-1 を計算。
    • ※ (m*,σ*)が正しければ、w^γ_-1 = (g₁')^1/(x+m*) Ψ(g₂^-γ(x)).
    • ※ 両辺をγ乗して、w = g₁^{(f(x)/(x+m*) - γ(x))/γ_-1} = g₁^1/(x+m*).
  • (m*, w)を出力して停止。

アルゴリズムBの解析：

• BのAに対する署名オラクル（その他）のシミュレーションは完ぺき。よって成功確率はε。
• time(B) = time(A) + O(q²) ≦ t + O(q²) ≦ t'
  • 各メッセージm_iについて、O(q).　 (i=1..q)

Q.E.D.

上へ

---