汎用的結合可能性 - 暗号理論教室 - atwiki（アットウィキ）

汎用的結合可能性 [Canetti 05]
コミットメント機能とその実現不可能性 [CF 01]
CRSモデルにおけるUCコミットメント [CF 01]
- CRSモデル
- UC コミットメント

汎用的結合可能性 [Canetti 05]

Ran Canetti によって2001年に提案された。[Canetti 01]
暗号プロトコルの安全性を定義するための枠組み。
各プロトコルの安全性を、単体ではなく、他の任意のプロトコルと任意の仕方で結合した場合の安全性を問題にする。

プロトコル実行モデル

環境とよばれる対話的チューリング機械Zが、攻撃者Aと協調しながら、
対象パーティにプロトコルπを実行させる、プロトコルの実行モデル。

プロトコルπを実行する各パーティへの入力は環境Zによって指定され、その出力も環境Zに渡される。
プロトコルπを実行するパーティ間のメッセージは攻撃者Aによって配送される。
プロトコルの実行中、任意のタイミングで、環境Zと攻撃者Aは対話することができる。

よりフォーマルには、いずれも効率的な対話的チューリング機械（ITM）である、
プロトコルπ、攻撃者A、環境Zについて、以下を実行する。
（以下、登場するすべてのITMは効率的であるとする。）

環境Zを(k, z)を入力として実行する：

Zは（何らかの入力のもとで）まずAを起動する。
- ※ 以降、Zが起動するその他のITMはπを実行するパーティのみ。それらはすべて同じセッション識別子SIDをもつ。
- ※ Zは自身が起動したITMとサブルーチン入出力テープでつながれる。
- ※ 実行順序：　テープに書き込みを受けたITMがつぎに活性化する。どのITMも書き込みを受けなかったときは、Zが活性化する。
Aが活性化されると、
- 自身のコードに従い計算を行い、Zにその出力を渡すことができる。
- さらに、つぎのいずれかを実行することができる：
  - Aは、あるパーティ（またはそのサブパーティ）にメッセージを送ることができる。その送信者識別子や内容は任意。
  - Aは、ある（識別子idの）パーティMをコラプトすることができる。これは、Mにメッセージ (corrupt)を送ることでモデル化される。
    - ※ ただし、Aは事前にZから (corrupt id) を入力されているとする。また、コラプトメッセージは対象パーティごとに高々1回。
πを実行しているパーティ（またはそのサブパーティ）が活性化されると、
- πのコードに従い計算を行う。さらに、つぎのいずれかを実行することができる：
  - Aにメッセージを送る（中継依頼）。
  - 自身を起動したパーティ（またはそのサブパーティ）に出力を渡す。
  - 自身のサブパーティに入力を渡す。
    - まだ該当するサブパーティが存在しないときは新しく作られる。
    - 自身のサブパーティとはサブルーチン入出力テープでつながれる。

[(corrup)メッセージに対するパーティの応答]
(corrup)メッセージに対するパーティの応答は、コラプションモデルに依存する。たとえば、

ビザンチンコラプションモデルでは、(corrup)メッセージを受け取った活性化および以降のすべての活性化において、
- 該当パーティは自身の状態をAに逐一報告
- 該当パーティは他のパーティに送るメッセージ内容について、Aの指示に従う。

[確率変数EXEC_π,A,Z]
上のモデルにおけるZの出力を EXEC_π,A,Z(k,z) とかき、

EXEC_π,A,Z =^def {EXEC_π,A,Z(k,z)}_k∈N,z∈B*.

イデアルプロセスモデルとリアルライフモデル

ある対話的チューリング機械Fについて、
各パーティがFをサブルーチンとして実行するだけのプロトコルをIDEAL_Fとかく。

すなわち、各パーティは自身の入力をそのままFにセットし、その結果Fから受け取った出力をそのまま出力する。

このとき、

IDEAL_F,A,Z =^def EXEC_{IDEAL_F,A,Z}

はイデアルプロセスモデルと呼ばれ、Fを理想機能と呼ぶ。

IDEAL_F,A,Zにおいては、EXECの定義より、どのような攻撃者Aも、
サブルーチンとして実行されているFには手を出せない。すなわち、

Aには各パーティとFがどのようなやり取りをしているかわからない。
- 各パーティは（メッセージではなく）サブルーチンテープを用いてIDEAL_Fと対話しているから。
AはFをコラプトすることもできない。

つまり、イデアルプロセスモデルIDEAL_F,A,Zは、
完全に信頼できる第三者Fが存在し、プロトコル実行のすべてをそのFに預けるときの、
プロトコル実行をモデル化する。

逆に、πがいかなる理想機能もサブルーチンとして用いないときのEXEC_π,A,Z(k,z)は、
リアルライフモデルと呼ばれ、REAL_π,A,Z(k,z)と書かれる。

UC模倣

定義(UC模倣)
π, φをそれぞれプロトコルとする。πがφをUC模倣するとは、
任意の攻撃者Aに対し、ある攻撃者Sが存在し、任意の環境Zについて、

EXEC_φ,S,Z ≡_c EXEC_π,A,Z

となることをいう。（このSをシミュレータと呼ぶ。）

つまり、Zにとって、πを（悪意をもって）実行して得られることは、
φを（悪意をもって）実行して得られることと変わらないということ。

注意 UC模倣の定義で、シミュレータSは環境Zについてユニバーサル（Zに依存しない）である。

定義(UC実現)
Fを理想機能とし、πをプロトコルとする。πがFをUC実現するとは、
πがIDEAL_FをUC模倣することをいう。

補題(指定シミュレータ)
任意のプロトコルπ、φについて、次の二つは同値である：

πはφをUC模倣する。
任意の攻撃者Aと任意の環境Zに対し、ある攻撃者Sが存在し、EXEC_φ,S,Z ≡_c EXEC_π,A,Z.

すなわち、シミュレータSが環境Zに依存することを許しても（指定シミュレータ）、UC模倣の概念は変わらない。

証明

自身では何も計算せず、

環境Zから受け取ったメッセージを指定されたパーティへそのまま配送する
パーティから受け取ったメッセージを（送信者情報を付けて)環境Zへそのまま送る

だけの攻撃者をダミー攻撃者と呼び、A_εで表す。

補題(DummyA)
任意のプロトコルπ、φについて、次の二つは同値である：

πはφをUC模倣する。
任意の環境Zについて、ある攻撃者Sが存在し、EXEC_φ,S,Z ≡_c EXEC_{π,A_ε,Z}.

すなわち、攻撃者をダミー攻撃者に制限しても、UC模倣の概念は変わらない。

証明

UC定理

プロトコルφをサブルーチンコールするプロトコルπに対し、

πにおけるφへのすべての呼び出しを、プロトコルρへの呼び出しに（SIDを保持して）変更したプロトコル

をπ^ρ/φとかく。

とくに、φ = IDEAL_Fのとき、

π^ρ/F =^def π^ρ/φ.

定理(UC)
π, ρ, φをそれぞれプロトコルとする。
ρがφをUC模倣するならば、π^ρ/φはπをUC模倣する。

証明

つまり、ρがφをUC模倣するならば、πとρの結合はπとφの結合をやはりUC模倣する。

系(UC1)
π, ρをプロトコルとする。ρが理想機能FをUC実現するならば、π^ρ/FはπをUC模倣する。

系(UC2)
F, Gを理想機能とする。πがGをUC実現し、ρがFをUC実現するならば、π^ρ/FはGをUC実現する。
∵ ∀A, ∃B, ∃S、EXEC_{π^ρ/F, A, Z} ≡_c EXEC_{π, B, Z} ≡_c EXEC_{G, S, Z}.

実現可能性

過半数のパーティが正直ならば、妥当な仮定のもとで
どのような機能についてもそれをUC実現するプロトコルが存在することが知られている。

コミットメント機能とその実現不可能性 [CF 01]

理想機能 F_COM:

Cから入力(Commit, sid, x)を受け取ったら、
- あるRについて、sid = (C, R, sid')となっていることを確認。（そうなっていなかったら無視する。）
- x を記録し、(Receipt, sid) をRに公開遅延出力する。
- いったん、xが記録されたら、以降のCommit入力は無視する。
Cから入力(Open, sid)を受け取ったら、
- あるxが記録されていたら、(Open, sid, x) をRに公開遅延出力する。（そうでなければ無視する。）
攻撃者からメッセージ(Corrupt-committer, sid)を受け取ったら、
- x を攻撃者に送る。
- さらに、攻撃者が新たに値 x' を提供し、Receipt出力がまだRのテープに書き込まれていなければ、記録されていた値を x' に変更する。

ある値をあるパーティに公開遅延出力するとは、

その値そのものををいったん攻撃者に送り、攻撃者から確認を得たのち、その値をそのパーティに送る

ことをいう。

ある値をあるパーティにプライベート遅延出力するとは、

その値のヘッダー情報のみをいったん攻撃者に送り、攻撃者から確認を得たのち、その値をそのパーティに送る

ことをいう。

定理(InfCom)
機能F_COMをUC実現するプロトコルは（認証つきチャネルを仮定しても）存在しない。

証明

CRSモデルにおけるUCコミットメント [CF 01]

CRSモデル

任意のパーティが、理想機能F_CRSを所与の機能としてサブルーチンコールできる、
リアルライフモデルをCRS (Common Reference String) モデルという。

理想機能 F_CRS:

パラメータ: 分布D
あるパーティPから入力(CRS, sid)を受け取ったら、
- それがこのF_CRSにとって初めての入力ならば値 r ← D を選択し、そうでなければ記録されているrを取り出す。
- (CRS, sid, r)をパーティPに公開遅延出力する。

UC コミットメント

プロトコル UCC_OneTime:
[部品]

トラップドア疑似乱数生成器 G_pk: {0,1}ⁿ → {0,1}⁴ⁿ :
- G_pk(r) = (f_pk⁽³ⁿ⁾(r), B(f_pk^(3n-1)(r)), ・・・, B(f_pk(r)), B(r)).
ここで、f_pkはnビットのトラップドア置換でB(・)はそのハードコア述語。

[CRS]

4nビットのランダム文字列σ
トラップドア疑似乱数生成器Gの2つの公開鍵 pk₀, pk₁

[コミットメントフェーズ] 　

コミッターC : b (∈{0,1}), SID sid = (C,R,sid') を入力として、
- r ← {0,1}ⁿ
- b = 0 ならば y = G_pk₀(r) とし、b = 1 ならば y = G_pk₁(r) + σ とする
- （ただし、+ は排他的論理和とする。）
- (Com, sid, y) をRに送る。
レシーバーR : (Receipt, sid) を出力する。