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

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

CRS (pk₀, pk₁, σ)について、
プロトコルUCC_OneTimeのコミットメント y は

• y = G_pk0(r) または G_pk1(r) + σ.

CRSモデルなので、攻撃者AはCRSを要求する。
これに対し、シミュレーターSはCRSとして(pk₀, pk₁, σ) を

• (sk₀, pk₀) ← f.Gen,　 (sk₁, pk₁) ← f.Gen
• σ = G_pk0(r₀) + G_pk1(r₁)

とつくる。Gの疑似乱数性により、このσはAにとって真のCRSと区別がつかない。

抽出可能性:
攻撃者Aがコミットメント y* を生成したら、シミュレータSは、

• sk₀を用いて、y*がG_pk0のイメージか否か判定する。
• そうならば y*は0へのコミット、そうでないならば y*は1へのコミットと判断する。

両義性:
シミュレータSは、オネストなコミッターの代理として、

• コミットメント y = G_pk0(r₀)

を生成する。y は、σの作り方から、

• y = G_pk1(r₁) + σ

をもみたすので、必要ならば0にも1にもデコミットできる。

定理(UCC_OneTime)の証明

プロトコルUCC_OneTimeをπとし、任意の効率的な攻撃者Aと環境Zを取る。

（ブラックボックス）シミュレータS:

• [初期化]
  • 偽のCRS (pk₀, pk₁, σ) を生成する：
    • (sk₀, pk₀) ← f.Gen,　 (sk₁, pk₁) ← f.Gen
    • σ = G_pk0(r₀) + G_pk1(r₁).
  • 攻撃者Aのプログラムを内部で起動する。
  • 以降、任意のタイミングで、
    • 攻撃者AがCRSを求めたら、(pk₀, pk₁, σ) を返答する。
    • （外部の）環境Zと（内部でシミュレートしている）攻撃者Aの間でメッセージのやりとりが発生したら、そのまま中継する。
• [オネストパーティのコミットメント] F_COMから (Reciept, sid=(C,R,sid'))を受け取ったら、
  • y = G_pk0(r₀) とし、(Com, sid, y)のRへの送信をCの名前で攻撃者Aに依頼する。
• [オネストパーティのデコミットメント] F_COMから (Open, sid=(C,R,sid'), b)を受け取ったら、
  • b = 0 ならば、(0, r₀)のRへの送信をCの名前で攻撃者Aに依頼する。
  • b = 1 ならば、(1, r₁)のRへの送信をCの名前で攻撃者Aに依頼する。
• [コラプトパーティのコミットメント] 攻撃者AにコラプトされたパーティCが(Com, sid=(C,R,sid'), y*)をRへ送ったら、
  • sk₀を用いて、y*がG_pk0のイメージか否か判定する。
  • そうならば b' = 0 とし、そうでないならば b' = 1 とする。
  • Cの名前で(Commit, sid, b')をF_COMに渡す。
• [コラプトパーティのデコミットメント] 攻撃者AにコラプトされたパーティCが(Open, sid=(C,R,sid'), b*)をRへ送ったら、
  • b*とb'が異なるならば、アボート。
  • そうでないならば、Cの名前で(Open, sid)をF_COMに渡す。
• [コラプト要求] 攻撃者Aから (Corrupt-committer, sid=(C,R,sid')) を受け取ったら、
  • 自身も (Corrupt-committer, sid=(C,R,sid')) を F_COMに渡し、
    • bを受け取ったら、Cの内部状態として (b, r_b) をAに渡す。
  • （さらに、攻撃者Aが新たに値 b' を提供しても、無視する。）

このシミュレータSが

• IDEAL_FCOM,S,Z ≡_c EXEC_π,A,Z

をみたすことを示したい。

そのためにハイブリッドな分布HYB_π,A,Zを用意する：

• HYB_π,A,Z: 以下を除いてEXEC_π,A,Zと同じ：
  • CRSのσは σ = G_pk0(r₀) + G_pk1(r₁) とつくる。
  • オネストパーティの0へのコミットメントは y = G_pk0(r₀) でシミュレート。
  • オネストパーティの1へのコミットメントは y = G_pk1(r₁) + σ でシミュレート。
  • （デコミットメントはπの指示通り (b, r_b) を送信。）

主張1　 EXEC_π,A,Z　 ≡_c　 HYB_π,A,Z.

証明. 攻撃者Aと環境Zを用いて、疑似乱数生成器Gの識別者Dを構成する：

識別者D 文字列zと公開鍵pkを入力として、

• ※ zが疑似ランダムか真にランダムかを識別したい。
• 初期化.
  • ランダムビット c を選択し、pk_1-c = pk とする。
  • ※ cは後のシミュレーションで、Zの指示に基づいて、コミッターがコミットするビット b の推測。
  • もう一つの鍵ペア (sk_c, pk_c) ← f.Gen を生成。
  • ランダムな r_c ← {0,1}ⁿ をとり、σ = G_pkc(r_c) + z とする。
  • ※ r_1-cはわからない（または存在しない）ことに注意。
• シミュレーション.
  • (pk₀, pk₁, σ) をCRSとしてA,Zとの間でリアルライフプロトコルをシミュレートする。
  • ZがオネストパーティCにビットbのコミットを命じたら、
    • b ≠ c のときは、0を出力してアボート。
    • b = c のときは、
      • b = 0のとき、Cの名前で G_pk0(r₀) をRへ送信。
      • b = 1のとき、Cの名前で G_pk1(r₁) + σ をRへ送信。
  • ZがオネストパーティCにデコミットを命じたら、
    • Cの名前で (c, r_c) をRへ送信。
  • AがオネストパーティCをコラプトしたら、
    • Cがまだコミットしていなければ、1/2の確率で0を出力してアボートもしくは続行。
    • Cがすでにコミットしていれば、(c, r_c) をAに渡す。
• 出力.
  • （まだアボートしていなければ）Zの出力を出力。

[識別者Dの解析]
zが真にランダムとする。D内のシミュレーションにおいて、

• コミッターCがオネストならば、
  • cはZのviewに属さないので、b = c となる確率は 1/2.
  • b ≠ c ならば、Zは常に0を出力。
  • b = c ならば、ZのviewはREAL（=EXEC_π,A,Z）におけるそれと同一なので、ZはREALと同じ確率で1を出力。
  • 以上より、ZはREALの半分の確率で1を出力
• コミッターCがコラプトされるとき、
  • トリビアルに、ZはREALの半分の確率で1を出力

以上より、

• Pr[D = 1 | zが真にランダム] = Pr[ D内のZが1を出力 | zが真にランダム] = 1/2 Pr[EXEC_π,A,Z = 1].

全く同様にして、

• Pr[D = 1 | zが疑似ランダム] = Pr[ D内のZが1を出力 | zが疑似ランダム] = 1/2 Pr[HYB_π,A,Z = 1].

Gは疑似乱数生成器なので上の2つの確率の差はネグリジブル。よって、主張を得る。 　q.e.d.

主張2　 HYB_π,A,Z　 ≡_c　 IDEAL_FCOM,S,Z.

証明. HYBとIDEALの唯一の違いは、

• HYBでは、コラプトパーティの言いなりにコミット・デコミットが実行される。
• IDEALでは、コラプトパーティのコミットメントy*からb'を取り出し、b'にF_COMでコミットする。
  • （その後、コラプトパーティはb*にデコミットしようとする。）

よって、主張を示すには、IDEALにおいて、『b' ≠ b*』となること、すなわち、

• イベント『y*がG_pk0のイメージで、同時にy*+σがG_pk1のイメージである』

がネグリジブルな確率でしか起きないことを示せばよい。

攻撃者Aと環境Zを用いて、疑似乱数生成器Gの識別者Dを構成する：

識別者D 文字列zと公開鍵pkを入力として、

• ※ zが疑似ランダムか真にランダムかを識別したい。
• 初期化.
  • pk₁ = pk とし、もう一つの鍵ペア (sk₀, pk₀) ← f.Gen を生成。
  • ランダムな r₀ ← {0,1}ⁿ をとり、σ = G_pk0(r₀) + z とする。
• シミュレーション.
  • (pk₀, pk₁, σ) をCRSとしてS,Zとの間でIDEALをシミュレートする。
  • Zがオネストパーティにコミットを命じたら、0を出力してアボートする。
  • 攻撃者AにコラプトされたパーティCがコミットメント y* をRへ送ったら、
    • sk₀を用いて y* がG_pk0のイメージか否か判定する。
    • そうであったとき、さらにCがy*を b*=1 にデコミットしたら（これが問題のイベント）、1を出力して停止。
    • それ以外の場合は、0を出力して停止。

[識別者Dの解析]
Dが1を出力するのは、あるr₀*とr₁*があって、

• G_pk0(r₀*) = G_pk1(r₁*) + (G_pk0(r₀) + z)

となるときのみ。このとき、

• z ∈ { G_pk0(r₀) + G_pk0(r₀*) + G_pk1(r₁*)　|　r₀, r₀*, r₁* ∈　{0,1}ⁿ }.

zが真にランダムのとき、この確率は高々 2^-n。

よって、Gは疑似乱数生成器なので、zが疑似ランダムのときもDが1を出力する確率はネグリジブル。
すなわち、IDEALで懸案のイベントが発生する確率はネグリジブル。　　q.e.d.

主張1, 主張2 より定理を得る。
Q.E.D.

上へ

---