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

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

ρがφをUC模倣しているとき、π^ρ/φがπをUC模倣することを示したい。

πが呼び出す複数のφインスタンスのうち、
ある一つのφインスタンスを除いた残りのすべてのインスタンスの実行を
環境のなかに取り込む。

そのように拡大してできた環境に対する、ρによるφのUC模倣性は、
π^ρ/φによるπのUC模倣性を意味する。

定理(UC)の証明

ρがφをUC模倣しているとする。π^ρ/φがπをUC模倣することを示したい。
（以下、π^ρ/φをπ^ρと略記する。）
それには、補題(DummyA)より、
あるシミュレータA_πがあって、どのような環境Zにおいても、πをπ^ρに見せることを示せばよい：

• EXEC_π,Aπ,Z ≡_c EXEC_π^ρ,Z.　　(∀Z）

（一般に、EXEC_π,Z := EXEC_π,Aε,Zとかく。A_εはダミー攻撃者）

ρはφをUC模倣しているので、
あるシミュレータSがあって、どのような環境Z_ρにおいても、φをρに見せる

• EXEC_φ,S,Zρ ≡_c EXEC_ρ,Zρ.　　(∀Z_ρ）

このSを用いて目的の（πをπ^ρに見せる）シミュレータA_πを構成する。

A_π:

• [Zから] Zから入力(m, id=(sid, pid), c)を受け取ると、　
  • ※ Zはダミー攻撃者とπ^ρを実行しているつもり。
  • ※ sidがπ内の何番目のρかを指定。
  • コードcがプロトコルρを表すならば、(m, id)をS_sid（sidに対応するシミュレータS）に渡す。
  • （まだS_sidがZ内に存在しないなら、(m, id)を入力としてS_sidを起動する。）
  • そうでなければ、 mをパーティP_idに送る。
• [パーティから] パーティまたはサブパーティからメッセージmを受け取ったら、
  • 送信者がサブパーティφ_sid,pidならば、mをS_sidに送る。
  • そうでなければ、 m を Z に渡す。
• [内部S_sidから]
  • 内部S_sidがサブパーティにメッセージを送ったら、そのままサブパーティに送る。
  • 内部S_sidがZへの値を出力したら、そのままZに渡す。

矛盾を導くために、あるZについて、A_πがπ^ρのシミュレーションに失敗すると仮定する：

• EXEC_π,Aπ,Z ≠_c EXEC_π^ρ,Z.

πは高々t個のφインスタンスを呼び出すとし、各l∈[0..t]についてハイブリッドモデルを構成する。

l-ハイブリッド:

• EXEC_π,A,Z(k,z)の実行において、
  • πの呼び出す、最初のl個のφインスタンスへの書き込み要求（値やメッセージ）はそのままφインスタンスに渡す。
  • πの呼び出す、残りの(t-l)個のφインスタンスへの書き込み要求は、（対応する）ρインスタンスに渡す。
• l-ハイブリッドの出力を EXEC_π,A,Z^l(k,z)とかく。

A_πに自明な修正を施し（ρインスタンスとのメッセージを、ダミー攻撃者のように、スルーする）、A'_πとすると、

• EXEC_π,A'π,Z^t ≡ EXEC_π,Aπ,Z　※　すべてφインスタンス
• EXEC_π,A'π,Z⁰ ≡ EXEC_πρ,Z　　※　すべてρインスタンス.

よって、背理法の仮定より、∃l ∈ [1..t]について、

• EXEC_π,A'π,Z^l ≠_c EXEC_π,A'π,Z^l-1

となる。

このlについて、環境Z_ρを構成する。

Z_ρ: (z, l)を入力として、

• Z, A'_π, π, φ₁, ..., φ_l-1, ρ_l+1, ..., ρ_tを内部で起動し、
• EXEC_π,A'π,Z^lの実行をシミュレートする。ただし、
  • l番目のπのサブルーチンインスタンスとのやり取りは、自身の攻撃者とパーティとのやりとりに接続する。

明らかに、

• EXEC_φ,S,Zρ(k, (z,l)) ≡ EXEC_π,A'π,Z^l(k,z)
• EXEC_ρ,Zρ(k, (z,l)) ≡ EXEC_π,A'π,Z^l-1(k,z)

よって、

• EXEC_φ,S,Zρ ≠_c EXEC_ρ,Zρ.

これは、Sが任意の環境においてφをρに見せるとの仮定に反する。

Q.E.D.

上へ

---