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

定理(2DH)の証明のアイデア

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

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

ここで、

• α = g^x,　β = g^y.

出力されるセッション鍵は

• γ = α^y = β^x = g^xy.

AMモデルなので、攻撃者はメッセージの改ざんや挿入はできない。
判定DH仮定より、攻撃者にとってセッション鍵γ = g^xy は一様ランダム。

定理(2DH)の証明

構成(2DH)が定義(SK安全)の条件1を満たすことは明らか。
条件2を満たすことを示す。
構成(2DH)に対する、AMモデルにおける、任意の攻撃者をAとする。
Aのセッション呼び出し回数の上限をlとおく。

Aを用いて判定DH問題の識別者Dを構成する：
識別者D: (q, g, α*, β*, γ*)を入力として、

• ※ γ*がDH(g,α*, β*)なのか一様ランダムなのか、判定したい。
• r ← {1,...,l}
• (q,g)を2DHプロトコルの公開パラメータにセットし、攻撃者Aを呼び出す：
  • Aが第n(≠r)番目のセッションについて、あるパーティP_kに実行要求または入力メッセージを発したら、
    • パーティP_kの代わりにプロトコル2DHをオネストに実行し返答を返す。
  • AがP_iに第r番目のセッションの実行要求(P_i,P_j,s_r)を発したら、
    • P_iの出力メッセージとして、(P_i, s_r, α*)を返す。
  • AがP_jに入力メッセージとして(P_i, s_r, α*)を発したら、
    • P_jの出力メッセージとして(P_j, s_r, β*)を返し、P_jでローカル出力が生成されたことを知らせる。
  • AがP_iに入力メッセージとして(P_i, s_r, β*)を発したら、
    • P_iでローカル出力が生成されたことを知らせる。
  • AがあるパーティP_kにコラプト命令を発したら、
    • k = i or j で、第r番目のセッションがまだ失効していないならば、
      • b' ← {0,1}を出力してアボート。※ DはP_iとP_jの内部状態は知らない。
    • そうでないならば、パーティP_kのすべての内部状態を返す。
  • Aがあるパーティ内のあるセッションにセッション状態開示クエリを発したら、
    • 該当セッションがs_rなら、b' ← {0,1}を出力してアボート。※ Dはセッションs_rの内部状態は知らない。
    • そうでないならば、該当セッションの状態を返す。
  • Aがあるパーティ内のあるセッションにセッション出力クエリを発したら、
    • 該当セッションがs_rで、
      • セッションs_rが未失効なら、b' ← {0,1}を出力して停止。※ Dはセッションs_rの内部状態は知らない。
      • セッションs_rが失効なら、空文字を返す。
    • そうでないならば、該当セッションのセッション鍵を返す。
  • Aがあるパーティ内のあるセッションにセッション失効クエリを発したら、
    • オネストに対応する。
  • Aがあるパーティ内のあるセッションをテストセッションに指定したら、
    • 該当セッションがs_rでなければ、b' ← {0,1}を出力して停止。
    • 該当セッションがs_rならば、γ* を返す。
• Aが出力b'で停止したら、
  • b' を出力して停止する。

[識別者Dの解析:]
イベント GoodChoice: 『テストセッションが第r番目のセッションs_rである』

• Pr[ b' = b | ￢GoodChoice ] = 1/2.
• Pr[ b' = b | GoodChoice ] = Pr[ (AMモデルで)Aが成功 ] =: 1/2 + ε.
  • AMモデルなので、Dによるテストセッションs_rのシミュレーション、とくにγ*の分布は正しい。
    • Aはα*やβ*を書き換えられない。

よって、

• Pr[ Dが成功 ] = Pr[ b' = b ]
• = Pr[￢GoodChoice]・(1/2) + Pr[GoodChoice]・(1/2 + ε)
• = (1-1/l)・(1/2) + (1/l)・(1/2 + ε)
• = 1/2 + ε/l.

よって、判定DH仮定より、ε/l はネグリジブル。
よって、εもネグリジブル。

Q.E.D.

上へ

---