補題(DummyA)の証明 - 暗号理論教室

補題(DummyA)の証明のアイデア

πはダミー攻撃者A_εについてφをUC模倣するとする。
このとき、A_εに対するシミュレータS_εが存在する。

πに対する任意の攻撃者をAとすると、
AとS_εを用いて、Aに対するシミュレータSを自然に構成できる。

補題(DummyA)の証明

πはダミー攻撃者A_εについてφをUC模倣するとする。
このとき、A_εに対するシミュレータS_εが存在し、

• EXEC_φ,Sε,Z ≡_c EXEC_π,Aε,Z. 　(∀Z)

πに対する任意の攻撃者をAとする。
AとS_εを用いて、Aに対するシミュレータSを構成する。

シミュレータS:

• 自身の内部で、AとS_εを起動する。
• [Zから]　Zから（Aへの）メッセージを受け取ったら、そのまま内部Aに渡す。
• [パーティPから]　Pから（Aへの）メッセージを受け取ったら、そのまま内部S_εに渡す。
• [内部Aから]
  • 内部AがZへのメッセージを発したら、そのままZに送る。
  • 内部AがあるパーティPにメッセージを配達したら、そのメッセージの配達指示をS_εに渡す。
• [内部S_εから]
  • 内部S_εがあるパーティPにメッセージを配達したら、そのままPに渡す。
  • 内部S_εの出力は、パーティの送信したメッセージとして、Aに渡す。

矛盾を導くために、φがSを通してπをUC模倣しないとする。すなわち、

• EXEC_φ,S,Z ≠_c EXEC_π,A,Z.　(∃Z)

AとZを用いて新たに環境Z_εを構成する。
環境Z_ε:

• 自身の内部で、自身の入力をZにセットして、ZとAを起動する。
• [内部Zから]　
  • 内部Zから（Aへの）メッセージを受け取ったら、そのまま内部Aに渡す。
  • 内部Zからパーティへの入力は、そのまま自身のパーティへ入力する。
• [パーティPから]　Pからその出力値を受け取ったら、そのまま内部Zに渡す。
• [内部Aから]　
  • 内部Aがあるパーティにメッセージを配達したら、そのメッセージの配達指示を自身の外部攻撃者に渡す。
  • 内部Aが環境に向けて値を出力したら、そのままその値を内部Zに渡す。
• [出力] 内部Zが停止たら、その出力値を自身の出力として停止する。

このZ_εについて、明らかに、

• EXEC_φ,Sε,Zε ≡_c EXEC_φ,S,Z
• EXEC_π,Aε,Zε ≡_c EXEC_π,A,Z.

したがって、

• EXEC_φ,Sε,Zε ≠_c EXEC_π,Aε,Zε.

これは、φに対するS_εが、πに対するダミー攻撃者をUC模倣するとの仮定に反する。

Q.E.D.

上へ

---