補題(指定シミュレータ)の証明 - 暗号理論教室

補題(指定シミュレータ)の証明のアイデア

どのような環境Zもユニバーサルなチューリング機械Z_uでシミュレートすることができる。
仮定より、Z_uに対する指定シミュレータS_uが存在するが、
環境Z_uがユニバーサルであることより、シミュレータS_uもユニバーサルとなる。

補題(指定シミュレータ)の証明

πは、指定シミュレータを用いてφをUC模倣できるとする。

ユニバーサル環境Z_u: (<Z>, z, 1^t) を入力として、

• zを入力としてZを起動する。ただし、Zのシミュレートは t ステップまで。
  • Zと外部エンティティとのやり取りは、そのまま中継する。

仮定より、任意の攻撃者Aとユニバーサル環境Z_uについて

• ∃S_u,　EXEC_φ,Su,Zu ≡_c EXEC_π,A,Zu.

主張 任意の環境Zについて、πはS_uを通してφを模倣する。
証明 Zを任意の環境とする。ある定数 c があって、Zのステップ数 ≦ |z|^c　である。
ユニバーサル環境Z_uの定義より、
∀k∈N, ∀z∈{0,1}* に対し, z_u=(<Z>,z,1^|z|c)ととれば、

• EXEC_φ,Su,Z(k,z) ≡ EXEC_φ,Su,Zu(k,z_u)
• EXEC_π,A,Z(k,z) ≡ EXEC_π,A,Zu(k,z_u)

である。よって、

• EXEC_φ,Su,Z(k,z) ≡ EXEC_φ,Su,Zu(k,z_u) ≡_c EXEC_π,A,Zu(k,z_u) ≡ EXEC_π,A,Z(k,z).

よって、

• EXEC_φ,Su,Z ≡_c EXEC_π,A,Z.　

q.e.d.

Q.E.D.

上へ

---