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

定理(SIG-DH)の証明のアイデア

プロトコル(SIG-DH)のトランスクリプトは

• (P_i, s, α), (P_j, s, β, σ),　(P_i, s, σ').

ここで、

• σ ← Sign(sk_j, (P_j,s,β,α,P_i)),
• σ' ← Sign(sk_i, (P_i,s,α,β,P_j)).

このトランスクリプトについて、署名σ, σ' の効果により、攻撃者は

• 送信者や受信者を偽ったり、
• αやβを書き換えたり、
• 他のセッションのメッセージに置き換えたり、

できないので、

• (P_i, s, α), (P_j, s, β)

は、AMモデルにおけるプロトコル(2DH)のトランスクリプトとみなせる。

よって、定理(SIG-DH)は定理(2DH)より従う。

定理(SIG-DH)の証明

プロトコル(SIG-DH)に対する、UMモデルにおける、任意の攻撃者をUとする。
Uを用いて、AMモデルにおける、プロトコル(2DH)の攻撃者Aを構成する：

攻撃者A:

• ※ メッセージを改ざん・挿入することなしにプロトコル(2DH)を攻撃したい。
• 大域変数としてキューMを空に初期化。※ 改ざん・挿入をしないようにメッセージの送受信にはキューMを用いる。
• 各パーティの署名用鍵ペア(sk_i,vk_i)を生成し、初期化関数Iにセット。
• 攻撃者Uのコードを実行する：
  • Uから実行要求(establish_session, P_i, P_j, s) を受け取ったら、
    • 実行要求 (establish_session, P_i, P_j, s) をパーティP_i、P_jに発する。
  • パーティP_iからP_j宛て出力メッセージ (P_i, s, α) を受け取ったら、
    • アイテム(P_i, P_j, s, α)をキュー M に格納する。
    • Uに(P_i, s, α)をP_iのP_j宛て出力メッセージとして渡す。
  • UからP_j宛て入力メッセージ (P_i, s, α) を受け取ったら、
    • キュー Mにアイテム(P_i, P_j, s, α)が存在するならば、
      • それをキューMから削除するとともに、(P_i, s, α)をパーティP_jに入力メッセージとして渡す。
      • ※ キューMに存在していたということは、Uが改ざん・挿入したメッセージではないということ。
    • キューMに該当アイテムがないならば、自身の外部パーティに対しセッションsをアボート。（アボート１）
  • パーティP_jからP_i宛て出力メッセージ (P_j, s, β) を受け取ったら、
    • アイテム(P_j, P_i, s, α, β)をキュー M に格納する。
    • 署名σ ← Sign(sk_j, (P_j,s,β,α,P_i)) を計算し、
    • Uに(P_j, s, β,σ)をP_jのP_i宛て出力メッセージとして渡す。
  • UからP_i宛て入力メッセージ (P_j, s, β,σ) を受け取ったら、
    • 署名σがP_jによる(P_j,s,β,α,P_i)の正しい署名でなければ、
      • Uに対しセッションsをアボート。（イベント１）
    • 署名σが正しければ、
      • キュー Mにアイテム(P_j, P_i, s, α,β)が存在するならば、
        • それをキュー Mから削除するとともに、(P_j, s, β)をパーティP_iに入力メッセージとして渡し、
        • 署名σ' ← Sign(sk_i, (P_i,s,α,β, P_j)) を計算し、
        • Uに(P_i, s, σ')をP_iのP_j宛て出力メッセージとして渡す。
      • キューMに該当アイテムがないならば、自身の外部パーティに対しセッションsをアボート。（アボート２）
  • UからP_j宛て入力メッセージ (P_i, s, σ') を受け取ったら、
    • 署名σ'がP_iによる(P_i,s,α,β,P_j)の正しい署名でないならば、
      • AはUに対しセッションsをアボートする。（イベント２）
      • ただし、Aは自身の外部パーティに対しセッションsをアボートしない。（すでに完了しているのでアボートできない。）
  • Uから、テストセッションクエリを含む、他のクエリを受け取ったら、
    • それをチャレンジャーまたは該当外部パーティにフォワードし、受け取った結果をUにバックワードする。

[攻撃者Aの解析]:
キューMの用い方から、Aはメッセージの改ざん・挿入はできない。よって、AMモデルの攻撃者として妥当。
テストセッションの識別について、UがA以上の能力をもち得るのは以下のケースが発生する場合のみ：

• アボート１∧￢イベント１∧￢イベント２：
  • Uは、第1メッセージを改ざん・挿入したセッションsを完了しているのに（￢イベント１,２）、
  • Aはセッションsをアボートした（アボート１）。
• アボート２∧￢イベント１∧￢イベント２：
  • Uは、第2メッセージを改ざん・挿入したセッションsを完了しているのに（￢イベント１,２）、
  • Aはセッションsをアボートした（アボート２）。

ところが、これらいずれのケースにおいても、

• UはキューMには存在しないアイテムについて正しい署名を生成していることになる。しかし、
• A自身が作る署名は、必ずキューMに格納されたアイテムを対象としている。

よって、これらのケースは、Uによる署名の偽造を意味する。

したがって、署名の偽造不可能性より、Uの識別利得はAのそれを越えるとしても、ネグリジブルな程度。

Q.E.D.

上へ

---