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

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

あるプロトコルπが機能F_COMを安全に実現するならば、

• ある環境Z_Cにおいてダミー攻撃者によるREAL（なプロトコルπの実行）をエミュレートするシミュレータSが存在しなければならない。
• そのシミュレータSを、別のある環境Z_Rのもとで、ある攻撃者A_Rが利用するとエミュレート不可能なREALが存在してしまう。

定理(InfCom)の証明

あるプロトコルπが機能F_COMを安全に実現するとする。

まず、以下の環境Z_Cを構成する。
環境Z_C:

• 攻撃者にパーティCのコラプトを指示。
• b ← {0,1}
• 攻撃者をダミー攻撃者として用いて、Cの名前で、パーティRに値bを（プロトコルπを用いて）コミットする。
• Rが Receipt を出力するのを確認し、攻撃者をダミー攻撃者として用いて、Cの名前で、パーティRに値bをオープンする。
• Rの出力 b' を得て、b =^? b' を出力する。

明らかに、REALでは、Z_Cは常に1を出力する。

πは機能F_COMを安全に実現するので、あるシミュレータSが存在し、

• SはF_COMとやり取りしながら、Z_Cにネグリジブルな例外を除いて1を出力させる。

このとき、F_COMは、コミットメントとして、コミットメント対象の値そのものしか受け取らないので、

• （Cをコラプトした）Sは、Z_Cのコミットメントから正しい値bを抽出していなければならない。

このSを用いて、以下の攻撃者A_Rを構成する。
攻撃者A_R:

• (環境からの指示に従い）Rをコラプトする。
• （Rの立場で）Cからのコミットメントを受け取る。
  • このとき、内部でSを起動し、受け取ったメッセージをSに中継する。（Sに対してZ_Cとして振る舞う。）
• Sが値b' を抽出したら、b' を環境に渡す。

以下の環境Z_Rを考える。
環境Z_R:

• 攻撃者にパーティRのコラプトを指示する。
• b ← {0,1}
• パーティCに b へのコミットを指示する。
• 攻撃者から値b' を受け取り、b =^? b' を出力する。

[Z_Rの解析]

• A_R内部のSの抽出機能のため、REALでは、Z_Rはほぼ常に1を出力する。
• ところが、F_COMは、コミットメントフェーズにおいて、Receiptしか出力しない。（Receiptにはbの情報は全く含まれない。）
• よって、IDEALでは、任意のシミュレータについて、Z_Rが1を出力する確率は1/2である。
• よって、イデアルプロセスでどのようなシミュレータを用いても、Z_RはREAL/IDEALを識別する。
• これは、πが機能F_COMをUC実現することに矛盾する。

Q.E.D.

上へ

---