定理(ツリー署名)の証明 - 暗号理論教室

定理(ツリー署名)の証明のアイデア

メッセージ m = m₁ ・・・m_n の、vk = vk_εに関するツリー署名は

• σ = <<σ_m|i, vk_m|i,0, vk_m|i,1>_i=0..(n-1), σ_m>.

ツリー署名の構成より、各ノードm|_iに格納される署名はただ一通り、σ_m|i。
よって、偽造者Fが何度署名オラクルから署名を得たとしても、
偽造者Fは各ノードについてはただ一通りの署名しか得られない。

よって、各ノードm|_iの署名はワンタイム署名で十分。

定理(ツリー署名)の証明

ツリー署名Ω'=(Gen',Sign',Verify') に対する任意の効率的な偽造者をFとする。
Fが発する署名クエリー回数の上限をl*とし、l = 2nl* + 1 とする
（ l は、Fに対する署名オラクルのシミュレーション時に、生成する必要のあるワンタイム署名の検証鍵数の上限）。
偽造者Fを用いてワンタイム署名Ω=(Gen,Sign,Verify) の偽造者Gを構成する。

偽造者G: vk を入力として、

• i* ← [1..l], vk^i* = vk
• i ∈ [1..l], i≠i* : (vkⁱ, skⁱ) ← Gen
• vk_ε = vk¹ を入力として偽造者Fを起動：
  • Fから署名オラクルに対する問い合わせ m' を受け取ったら、
    • 各 i ∈ [0..(n-1)] について: ※ n = len(m')
      • ノードm'|_iにまだ署名が格納されていなければ、
        • vk_m'|i,0, vk_m'|i,1 ← まだ用いていない、つぎの2つの vk^j, vk^j+1
        • vk_m'|iが vk^l (l≠i*) に対応していたら、σ_m'|i ← Sign(sk^l, vk_m'|i,0||vk_m'|i,1)
        • else vk_m'|i,0||vk_m'|i,1 を自身の署名オラクルに問い合わせ、σ_m'|iをえる。
        • ノードm'|_iに <σ_m'|i, vk_m'|i,0, vk_m'|i,1>を格納。
      • ノードm' にまだ署名が格納されていなければ、
        • 上と同様にして、vk_m'についてのメッセージm'の署名σ_m'を計算し、ノードm'に格納。
• Fが出力(m, σ* = <<σ*_m|i, vk*_m|i,0, vk*_m|i,1>_i=0..(n-1), σ*_m>)で停止したら、
  • ∃j ∈ [0..(n-1)],　 vk*_m|j,0 ≠ vk_m|j,0　OR　vk*_m|j,1 ≠ vk_m|j,1 :
    • インデックス j ← [そのような j のうち最小の j]
    • インデックス i ← [vkⁱ = vk*_m|j (= vk_m|j) となる i]
    • i = i* : (vk*_m|j,0||vk*_m|j,1, σ*_m|j)を出力して停止。
  • else 　※ vk*_m = vk_m
    • インデックス i ← [vkⁱ = vk*_m となる i]
    • i = i* : (m, σ*_m)を出力して停止。

偽造者Gの解析：
Gの構成より、

• Gは署名オラクルを高々一回しか使っていない。
• Gによる、Fに対するシミュレーションは完ぺき。
• i* はランダムでFのviewには属しない。i* = i ならば、Gは偽造に成功。

よって、

• Pr[Gが偽造に成功] = (1/l) Pr[Fが偽造に成功].

仮定より、左辺はネグリジブルなので、Pr[Fが偽造に成功]もネグリジブル。

Q.E.D.

上へ

---