このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

宣伝

 当サイトにおける暗号に関するページでは、説明が足りなかったり、誤った記述をしていたりするところがあります。今後、少しずつ修正する予定です。

 暗号理論の『暗号技術のすべて』が発売されています。初心者向けの暗号本です。これまで暗号本に何度か挑戦しつつも挫折してしまった方、学校の課題で悩んでいる方、資格試験にて暗号の問題が苦手な方などにお勧めです。

『暗号技術のすべて』宣伝サイト

 興味がある方は宣伝サイトを参照してください。Amazonでも発売中です。

UC Commitment with CRS model

 UAHCは、CRSモデルにおいてhiding,binding,equivocality,extractabilityの4つの性質を持つので、universal composabilityを持つことが期待できる。

CRS model

 CRSモデルは本質的にFCRSハイブリッドモデルである。

 FCRSの仕様は次の通りである。

  1. (crs,sid)(あるいは(crs,sid,ssid))のクエリーを受け取ると、分布Dからランダムストリングrを選ぶ。
  2. rをクエリー送信した側とアドバーサリーに送り返す。

 このFCRSを図にすると次のようになる。

 FCRSハイブリッドモデル内のアドバーサリーは、イデアルファンクショナリティからCRSの値を得ることを期待している。simulated interactionにおけるシミュレータは自分自身でCRSを選ぶことができる。つまり、CRSに関連したtrapdoor情報を知ることができると言い換えることができる。

UAHCがUC安全であることの直観的な証明

 UAHCが、CRSモデルにおいてUC commitment(マルチセッション型)のイデアルファンクショナリティであるFMCOMをUCフレームワーク内で実現できることを示す。

[定理]
trapdoor permutationの存在を仮定する。
このときUAHCは、FCRSハイブリッドモデル内でmalicious,adaptiveアドバーサリーに対して、FMCOMをUC実現する。

[証明]トラップドア置換の存在の仮定より、次のような2つの暗号スキームが作れる。

  • E:IND-CPAである暗号スキーム
  • Ecca:IND-CCA2である暗号スキーム

 このとき、次の式が主張できれば、定理が証明できたことになる。

\forall~A,\exists~S,\forall~Z;~HYB_{UAHC,A,Z}^{F_{CRS}}~\overset{c}{\approx}~IDEAL_{F_{MCOM},S,Z}

 SのアルゴリズムをPi,Pjがhonestか否かで場合分けする。

[1]Pi,Pjの両方ともがhonestのとき

<COMMITフェーズ>

[HYB]

 PiはZから(commit,sid,ssid,Pi,Pj,b)が送られてきたら、まずFCRSにクエリーを送り、CRSであるy,E,Eccaを返信メッセージとして受け取る。返信メッセージが送信されるとき、FCRSは同時にアドバーサリーにも同じメッセージを送信している。

[IDEAL]

 SはFMCOMからreceiptメッセージを受け取ったら、kビットのランダム値xを作り、fとxでy=f(x)を作る。{E,D},{Ecca,Dcca}を作る。

 aHCはequivocalityを持つので、aHCのbindingを破るアルゴリズムを用いて、入力をxとして、aHCの両開きのr0,r1を同時に出力できる。それらのr0,r1、ランダムコインのs1,s2,s1',s2'により、2つの暗号文C0,C1を作る。

  • C_0~=~E(E_{cca}(P_i,P_j,sid,ssid,r_0~;s_1)~;s_2)
  • C_1~=~E(E_{cca}(P_i,P_j,sid,ssid,r_1~;s_1')~;s_2')

 そして、トランスクリプトc=(sid,ssid,Pi,C0,C1)をAに渡す。

 直観的にいうと、次のようになる。ここではb=1のときで、cの後半3つの成分に注目している。

  • (HYBのc)=\{~aHC(0;r),~C_0,~U_{|C_0|}~\}
  • (IDEALのc)=\{~aHC(0;r),~E(E_{cca}~(P_i,~P_j,~sid,~ssid,~r_0~;s_1)~;s_2),C_2~\}

 上記の第1成分はaHCのhidingより区別できない。また第2成分はIND-CPA安全より区別できない。第3成分は両方とも同じ作り方なのでまったく区別できない。もしb=0なら、第2成分と第3成分の解釈が逆になるだけで、同じ議論ができる。

 よって、このときアドバーサリーAにとって識別できない(厳密な証明は後半を参照せよ)。Aから報告を受ける環境Zも識別できない。

 HYBとIDEALのPjのローカル出力はどちらも同じreceiptメッセージなので、Zはそれを超越的に見てもHYBとIDEALを識別できない。

<REVEALフェーズ>

[HYB]

[IDEAL]

 SはFMCOMから(reveal,sid,ssid,Pi,Pj,b)を受け取る。SはAにトランスクリプト(reveal,sid,ssid,rb,s,b)を渡す。ここでb=0のときs:=(s1,s2)、b=1のときs:=(s1',s2')とする。

 SはきちんとHYBのトランスクリプトと同じものをシミュレートできているので、AはトランスクリプトからHYBとIDEALを識別できない。つまり、Aから報告を受けるZも識別できない。

 HYBとIDEALのPjのローカル出力はどちらも同じ(reveal,sid,ssid,Pi,Pjb)なので、Zはそれを超越的に見てもHYBとIDEALを識別できない。

[2]Piがcorruptされ、Pjがhonestのとき

<COMMITフェーズ>

[HYB]

[IDEAL]

 Sはランダムストリングxからy=f(x)を計算する。fにより{E,D}、{Ecca,Dcca}という2つの暗号スキームを作ることができる。

 Aから送られてきた偽造されたcommitメッセージのうち、C0*,C1*をIND-CPA安全な暗号スキームの復号鍵で復号する。その結果をそれぞれC0cca,C1ccaとする。

 次に検証式によってSからFMCOMに送信されるcommitメッセージが変化する。

 まず、C0cca,C1ccaのどちらかがSによって作られたものかどうかをチェックする。なぜならマルチセッションを考える必要があるからだ。もしすでに作られたものなら、前のセッションですでにbを知っているので、そのbをセットして、commitメッセージである(commit,sid,ssid,Pi,Pj,b)をFMCOMに送信する。

 次に、C0cca,C1ccaのどちらもSによって作られたものでなければ、新しいbに関するコミットメントと判断できる。そこで、次の条件をすべて満たすbが存在すれば、Sは(commit,sid,ssid,Pi,Pj,b)をFMCOMに送信する。

  • D_{cca}(C_b^{cca})~=~(P_i,~P_j,~sid,~ssid,~r)
  • z^{*}~=~aHC(b;r)
  • D_{cca}(C_{1-b}^{cca})~=~(P_i,~P_j,~sid,~ssid,~r')
  • z^{*}~\not{=}~aHC(1-b;r')

 また、次の条件をすべて満たすbが存在すれば、Sは(commit,sid,ssid,Pi,Pj,0)をFMCOMに送信する。0をセットしているのは、どうしてもFMCOMにreceiptメッセージを出力させないと困るからである。

  • D_{cca}(C_b^{cca})~=~(P_i,~P_j,~sid,~ssid,~r)
  • z^{*}~\not{=}~aHC(b;r)
  • D_{cca}(C_{1-b}^{cca})~=~(P_i,~P_j,~sid,~ssid,~r')
  • z^{*}~\not{=}~aHC(1-b;r')

 最後に、次の条件をすべて満たすbが存在すれば、Sはfailureをローカル出力する。

  • D_{cca}(C_b^{cca})~=~(P_i,~P_j,~sid,~ssid,~r)
  • z^{*}~=~aHC(b;r)
  • D_{cca}(C_{1-b}^{cca})~=~(P_i,~P_j,~sid,~ssid,~r')
  • z^{*}~=~aHC(1-b;r')

 こうした手続きを図にすると次のようになる。

 [2]のCOMMITフェーズは、HYBとIDEALのAには、特にトランスクリプトを渡す必要はなく、あくまでZがPiとPjのローカル出力を超越的に見るのでここをチェックする必要がある。Piのローカル出力として、IDEALのときはfailureが出力される可能性があるが、これに関しては証明の後半で詳しく述べる。Pjのローカル出力はHYBとIDEALのときどちらでも同じreceiptメッセージなので、区別がつかない。

<REVEALフェーズ>

[HYB]

 PiをcorruptしたAは偽造したメッセージ(sid,ssid,r^{*},s_1^{*},s_2^{*},b^{*})を送る。PjはCOMMITフェーズですでに送られた情報とREVEALフェーズで今送られた情報を利用して、次の2つの検証式をチェックする。

  • z^{*}~=~aHC(b^{*};r^{*})
  • C_{b^{*}}^{*}=E(E_{cca}(P_i,P_j,sid,ssid,r^{*}~;~s_1^{*})~;~s_2^{*})

 もし検証式が成り立てば、(reveal,sid,ssid,P_i,P_j,b^{*})を出力する。そうでなければ何もしない。

[IDEAL]

 PiをcorruptしているSはZから命令が来たら、シミュレートされているPiをcorruptしているAにそのままフォワードする。すると、AはREALのときと同じ偽造メッセージ(sid,ssid,r^*,s_1^*,s_2^*,b^*)を出力する。

 Sは次の検証式をチェックする。

  • z^*~=~aHC(b^*;r^*)
  • C_{b^{*}}^{*}=E(E_{cca}(P_i,P_j,sid,ssid,r^{*}~;~s_1^{*})~;~s_2^{*})

 もし成り立てば、(reveal,sid,ssid,P_i,P_j)をFMCOMへ送る。成り立たなければ、何もしない。

 FMCOM(reveal,sid,ssid,P_i,P_j)を受け取ると、COMMITフェーズで記録したbを(reveal,sid,ssid,P_i,P_j,b)をPjへ送る。

[3]Pjがcorruptされ、Piがhonestのとき

 non-interactive型なので、受け手であるPjだけがcorruptされたとき、Sはプロトコルの仕様通りに動かせばよい。

 以上で典型的な状況におけるシミュレータSの動きは記述された。 □

adaptiveアドバーサリーに対してUC安全であることの証明

 しかし、上記のアドバーサリーの能力はstaticであった。次にadaptiveアドバーサリーがcorruptするタイミングについて見てみる。

 まずPiとPjがhonestのときのIDEALの世界で、SはシミュレートされたPiとPjの通信をAに見せるわけだ。通信を見せるというのは、シミュレートされたPiからのcommitment情報cはAのインカミングテープに書き込まれる。そこで一旦Aの制御に移り、単にメッセージを覗き見するだけならAのアウトゴーイングテープからcを出して、シミュレートされたPjのインカミングテープに書き込む(次図の点線の部分)。

[corruption]Piからcを受け取ったら、Piをcorruptしようとするとき

 SからトランスクリプトcがAに渡される。AがPiをcorruptする。SもPiをcorruptする。SはPiの内部ステート(sid,ssid,Pi,r,s,b)を知る。SはAに(rb,sb,b)を渡す。以降は典型的な例と同じシミュレーションで問題ない。

[corruption]Piからcを受け取ったら、Pjをcorruptしようとするとき

 SからトランスクリプトcがAに渡される。AがPjをcorruptする。SもPjをcorruptする。SはPjの内部ステートsを知る。SはAにsを渡す。以降は典型的な例と同じシミュレーションで問題ない。

UAHCがUC安全であることの厳密な証明

 以上ですべての状況におけるシミュレータSの動きは記述された。本当にそうした動きをしたときにZに対してシミュレーションがうまくいっているかどうかを調べなければならない。ここではREALの対話の実行(以降、略してREAL実行と呼ぶことにする)を少しずつ変形しながら、最終的にIDEAL実行にする。そして、その間に登場する実行が互いに識別不可能であることを示す。全体像を次に示す。

 これを参考に細かい部分を見ていく。

(I)Real interaction

 これはREALの実行である。ここでcommitしたい値はbとする。

(II) Real interaction with partially fake commitments

 (II)は次の部分だけ(I)と異なる。

  • Gのハミルトンサイクル(xに相当)はすべてのhonestパーティーに与えられるが、この情報はcorruptのときにrevealされない。
  • fakeのzを作る。即ち、aHCのbindingを破るようなr0,r1は作れる。ただし、r1-bはAに渡さない。なぜなら渡してしまうとzがfake、即ち0のcommitであることがばれてしまうからだ。

 ここで(I)と(II)を比較する。

  • (I)の実行のView=\{~aHC(1;r_1),r_1~\}
  • (II)の実行のView=\{~aHC(0;r_0),r_1~\}

 前半のaHCがCOMMITフェーズで与えられるものであり、後半のr1はREVEALフェーズで与えられるものである。

 r1でaHC(0;r0)はオープンできない。というのもr1はr0の部分情報であり、部分情報から全体が漏れるわけがない(ハミルトンサイクルのときだけオープンされる)。

 よって、(I)の実行のViewと(II)の実行のViewは計算量的に識別できない。ゆえに次が成り立つ。

\{~aHC(1;r_1),r_1~\}~\overset{c}{\approx}~\{~aHC(0;r_0),r_1~\}

(I)~\overset{c}{\approx}~(II)

(III)Real interaction with completely fake commitments

 (III)は次の部分だけ(II)と異なる。

  • C1-bをランダムストリングにする代わりに、C_{1-b}~=~E(E_{cca}(P_i,P_j,sid,ssid,r_{1-b}))と計算する。

 これはcommitment情報のzだけでなく、C1-bもfakeになったということだ。

 (II)と(III)が識別不可能であることを示したい。もう少し厳密にいうと、「EがIND-CPA」⇒「∀Zは(II)と(III)が識別不可能」を示したいとする。そこでこの対偶を考える。「(II)と(III)を区別できるZがいれば、bを見破るAが作れる」ということになる。つまり、「∃Zが(II)と(III)を識別する」⇒「∃AがLR-gameにwin」という主張を確かめればよい。

 ここで、まずLR-oracleとはどういうものかを確かめておく。LR-oracleとはチャレンジャーに当るoracleとアドバーサリーが行うゲームである。ゲームという所以は、チャレンジャーが選択した1ビットのbを、アドバーサリーが当てたらアドバーサリーの勝ち、当てることができなければチャレンジャーの勝ちとなる。

 LR-oracleの定義ではアドバーサリーが平文を2つ送り、その片方の平文に対する暗号文を受け取る。この一連のやり取りは何度も繰り返すことが可能。そうして得た暗号文からbを推測するわけだ。これを図にすると次のようになる。

 しかし、示したい主張に対応させるために、少し変形する。今度はアドバーサリーが平文を1つ送り、暗号文またはランダムストリング(暗号文と同じビット長)を受け取るというように変更するわけだ。これを図にすると次のようになる。

 このように変形しても同値であることはすでに証明されている。

 それでは主張である「∃Zが(II)と(III)を識別する」⇒「∃AがLR-gameにwin」を証明する準備ができた。では、証明に入る。

 LR-oracleのアドバーサリーはoracleが用いる暗号化の公開鍵だけ与えられる。ここではIND-CPA安全な暗号を使うので、AはEを与えられる。Aは鍵生成アルゴリズムを用いて、IND-CCA2安全な公開鍵と秘密鍵のペアを自ら生成する。

(E_{cca},C_{cca})~\leftarrow~Gen(1^k)

 そして、kビットのランダム値xに作り、それとone-way functionであるfからyを作る。これはハミルトンサイクルHを自分で決めてから、それに点と線を追加してグラフGを作ることを意味している。つまり、AはequivocalityによりaHCのbindingを破れることにする。

 Aは中で、Zをactivateして、REAL実行(プロトコルUAHC)を開始する。そのプロトコルのEでの暗号化のところでLR-oracleに頼るわけだ。Zの世界にCRSして、y,Ecca,Eを見せる(厳密にいえばFCRSを使って見せている)。ZはPiとPjをactivateする。ここでZはbをcommitしたいとして、このbはPiへ送られる。そのときAはPiにCRSのtrapdoorであるxを渡す。PiはプロトコルUAHCの仕様通りに動き、その途中でEcca(Pi,Pj,sid,ssid,r1-b)をaとおく。

 このaを変形後のLR-oracleに送る。LR-oracleはランダムにあらかじめ選んでおいた1ビットのbの0か1によって、aの暗号文E(a)あるいは暗号文と同じビット長のランダムストリングをPiへ返す。このとき暗号文を返すときが(III)、ランダムストリングを返すときが(II)に対応する。それ以降はプロトコルUAHC通りに動き、commitment情報をPjへ送る。このプロトコルを支配下に置いているZは(II)と(III)を識別するので、bを出力する。Aはこのbをそのまま出力すれば、LR-gameに勝つ。

 これで主張が証明できた。後は対偶を取って戻せば、「EがIND-CPA」⇒「∀Zは(II)と(III)が識別不可能」になる。

(II)~\overset{c}{\approx}~(III)

(IV)Simulaetd interaction

 これはIDEALの実行である。

 (III)と(IV)の違いを知りたい。結論からいうと、(IV)ではfailureをローカル出力する可能性があり、それだけが(III)と(IV)の違いである。これをきちんと場合分けして、その違いを確認しなければならない。

[a-i]Piがhonestのときの(III)

[a-ii]Piがhonestのときの(IV)

 これはすでに言及したPiとPjがhonestのときのIDEALのCOMMITフェーズとREVEALフェーズの対話の実行を考えればよい。次に示す前者の図がCOMMITフェーズのときで、後者の図がREVEALフェーズである。

 [a-i]と[a-ii]に違いがあるか調べてみる。

 [a-i]のPiではxを超越的に与えられる。一方、[a-ii]のSはxをランダムに作っていることに対応している。

 また、[a-i]のPiでは暗号文C0,C1を作っている。これは(II)と(III)の違いでわかるはずだ。一方、[a-ii]のSも同じ方法で暗号文C0,C1を作っている。

 実行全体で見ると[a-i]と[a-ii]には違いがない。それぞれの状況のViewだけでなく、プロトコルで使うメッセージの作り方も一致しているからである。

[b-i]Piがcorruptされているときの(III)

 [2]のREAL実行である。次の図はそのときのCOMMITフェーズとREVEALフェーズの実行をまとめたものである。

[b-ii]Piがcorruptされているときの(IV)

 [2]のIDEAL実行である。次の図はそのときのCOMMITフェーズとREVEALフェーズの実行をまとめたものである。

 [b-i]と[b-ii]に違いがあるか調べてみる。これは明らかにわかるように、[b-ii]ではfailureをローカル出力するElseIf文がある。

 よって、(III)と(IV)の違いは、(IV)ではfailureをローカル出力する可能性があり、(IV)のSはCOMMITフェーズでbを入力が与えられていなかったり、equivocalityによるzを使っていたりする。まだ(III)と(IV)には(思考に関する)ギャップがあるので、今度は(IV)から(III)に徐々に近づけていくことにする。

(V) Simulation with partially real encryption

 (V)は次の部分だけ(IV)と異なる。

  • Sはすべてのhonestパーティーの入力(bを含む)が与えられる。
  • simulated commitmentを生成するとき、次のように計算する。
    • C_{1-b}=~E(E_{cca}(P_i,P_j,sid,ssid,0^{|r_{1-b}|}))

 ∀(Aと)Zに対して(IV)と(V)が識別不可能であることをいうには、(IV)でSがfailureを出力する確率と(V)でSがfailureを出力する確率の差がnegligibleであることがいえればよい。即ち、次の主張がいえればよい。

\forall~A,\forall~Z;|\Pr^{(V)}[S=failure]-\Pr^{(IV)}[S=failure]|:neg

 証明には背理法を使う。次のように仮定する。

\exists~A,\exists~Z;|\Pr^{(V)}[S=failure]-\Pr^{(IV)}[S=failure]|:non-neg

 (IV)と(V)の違いはC1-bの作り方がIND-CCA2安全な暗号スキームの暗号文かランダムストリングかということである。そこで、IND-CCA2安全を破るアドバーサリーBを作りたい。

 BはEccaを入力されたら、Bの中でZをactivateして、IDEAL実行(FMCOMが存在する)を開始する。ZはPiへcommitしたいbを送るので、BはそれをSの入力とする。

 するとSは自らkビットのランダム値xを作り、そのxとfからy=f(x)を作る。後は{E,D}を作る。equivocalityにより、ハミルトンサイクルに相当するxからaHCのbindingを破るr0,r1を作ることができる。

(z,r_0,r_1)~\,~s.t.~\,~z=aHC(0;r_0)=aHC(1;r_1)

 bを知っているので、r0,r1のどちらを2重に暗号化してCbを作ればよいのかわかる。

C_b~\leftarrow~E(E_{cca}(P_i,P_j,sid,ssid,r_b))

 1-bの方はLR-oracleを使う。まず、a0とa1を次のように作る。

  • a_0=(P_i,P_j,sid,ssid,r_{1-b})
  • a_1=(P_i,P_j,sid,ssid,0^{|r_{1-b}|})

 Sはペア(a0,a1)をLR-oracleに送る。LR-oracleはあらかじめ1ビットのランダム値dを決定している。LR-oracleはdの値により、受け取ったa0とa1のどちらかをIND-CCA安全な暗号スキームで暗号化する。暗号化してできたものをCccaとする。そして、CccaをSへ送り返す。

 SはCccaをIND-CPA安全な暗号スキームで暗号化する。

C_{1-b}~\leftarrow~E(C^{cca})

 Sはトランスクリプトc=(sid,ssid,P_i,z,C_0,C_1)を作り、Aに渡す。AはZに報告する。

 ここでマルチセッションを考慮する必要がある。ZはこのセッションのREVEALフェーズを開始しないように、IDEAL実行を止めておいて、別のセッションを開始するかもしれない。

 ここではZが別のセッションを開始したとする。次のセッション(\widebar{sid},\widebar{ssid})ではPiをcorruptしたとする。Zはこの戦略を取った方が高いアドバンテージを得ることができる。

 特に最初のセッションでAを介して送られたcommitment情報cを記録しておく。そして、次のセッションでPiをAにcorruptさせてそのときのcommitment情報cに、さきほど記録しておいたものをそのまま使うわけだ。そうすることで最初のセッションでSがequivocalityで有利だった状況を逆手に取って、次のセッションではSは先ほどの有利が仇になって今度はS自身が困ってしまうわけだ。

 それでは考察してみよう。PiをcorruptしているS(即ちS(Pi))は、Zの指令をそのままA(~Pi)へ渡す。すると、A(~Pi)は偽造したcommitment情報(\widebar{sid},\widebar{ssid},P_i,z^*,C_0^*,C_1^*)を送ってくる。これをDで復号する。

  • C_0^{cca}~\leftarrow~D(C_0^*)
  • C_1^{cca}~\leftarrow~D(C_1^*)

 ここで、C_0^{cca},C_1^{cca}のどちらかが、過去にもらったチャレンジ暗号文(Cccaとする)かどうかで、場合分けが必要となる。

[ケース1]C_b^{cca}=C^{cca}のとき、即ちi=\widebar{i},j=\widebar{j},sid=\widebar{sid},ssid=\widebar{ssid}のとき

 Sはすでにbを知っている。よってSはFMCOMにこのbを送ればよい。Aにr1-bを渡さないので、Aはr1-bを知らない。つまり、r_{1-b}~\not{\in}~View(A)となる。するとAはcommitment情報をbにしかオープンできないようにできる。

[ケース2]ケース1でないとき

 このときC_b^{cca}はチャレンジ暗号文でないので、単に復号オラクルDccaが使える。復号オラクルを使って平文D_{cca}(C_b^{cca})が得られた。後は[3]のIDEAL時のSと同じ動きをすればよい。

 最後にSがfailureを出力したらBは1を出力し、Sがfailureを出力しなければBは0を出力すればよい。

 以上でSはDccaを知らないが、実際に停止することなく動作するようアルゴリズムBが作れた。

 後はBのアドバンテージを調べればよい。Bの目的はdを推測であり、「Bの出力=d」のとき成功する。

Adv(B)
=|\Pr[B~\,~outputs~\,~d]~-~\frac{1}{2}|
=|\Pr[d=0]\Pr[B=0|d=0]~+~\Pr[d=1]\Pr[B=1|d=1]~-~\frac{1}{2}|
=|\frac{1}{2}~\Pr[B=0|d=0]~+~\frac{1}{2}~\Pr[B=1|d=1]~-~\frac{1}{2}| (∵d=0,1となる確率は単にコイン投げしているだけと考えることができ、それぞれの確率は1/2)

ここで、

  • \Pr[B=0|d=0]~=~\Pr^{(IV)}[\neg(S=failure)]~=~1-\Pr^{(IV)}[S=failure]
  • \Pr[B=1|d=1]~=~\Pr^{(V)}[S=failure]

が成り立つので、

Adv(B)
=|\frac{1}{2}~(1-\Pr^{(IV)}~[S=failure])~+~\frac{1}{2}\Pr^{(V)}~[S=failure]~-~\frac{1}{2}|
=|\frac{1}{2}~\Pr^{(V)}~[S=failure]~-~\frac{1}{2}~\Pr^{(IV)}~[S=failure]|
=\frac{1}{2}~|\Pr^{(V)}~[S=failure]~-~\Pr^{(IV)}~[S=failure]|

 仮定より、|\Pr^{(V)}~[S=failure]~-~\Pr^{(IV)}~[S=failure]|:non-negなので、Adv(B)もnon-negになる。しかし、EccaがIND-CCA安全より、Adv(B)がnon-negであることに矛盾する。

 ゆえに、次の主張が成り立つ。

\forall~A,\forall~Z;|\Pr^{(V)}[S=failure]-\Pr^{(IV)}[S=failure]|:neg

(IV)~\overset{c}{\approx}~(V)

(VI) Simulation with nearly real commitments

 (VI)は次の部分だけ(V)と異なる。

  • z~\leftarrow~aHC(b;r_b)を計算する。なお、(V)ではz~\leftarrow~aHC(0;r_0)を計算していた。

 ∀(Aと)Zに対して(V)と(VI)が識別不可能であることをいうには、(V)でSがfailureを出力する確率と(VI)でSがfailureを出力する確率の差がnegligibleであることがいえればよい。示したい主張は次の通りである。

\forall~A,\forall~Z;|\Pr^{(VI)}[S=failure]-\Pr^{(V)}[S=failure]|:neg

 証明には背理法を使う。次のように仮定する。

\exists~A,\exists~Z;|\Pr^{(VI)}[S=failure]-\Pr^{(V)}[S=failure]|:non-neg

 aHC(b)を入力とし、aHCのbindingを破るアドバーサリーBを作りたい。

 Bは内部でZをactivateし、IDEAL実行を開始する。するとSは停止せずに動く。このときSがfailureを出力する可能性がある。もしSがfailureを出力したらBは1を出力し、Sがfailureを出力しなければBは0を出力するように動くことにする。

 Zが(VI)のときにb=0という戦略を取ってしまってもBのアドバンテージが上がらないため、ここでZは常にb=1をcommitすると仮定してよい。

 実際にアルゴリズムBが作れた。

 後はBのアドバンテージを調べればよい。Bの目的はdを推測であり、「Bの出力b'=aHCの中身b」のとき成功する。

Adv(B)
=|\Pr[b=b']~-~\frac{1}{2}|
=|\Pr[d=0]\Pr[b'=0|b=0]~+~\Pr[d=1]\Pr[b'=1|b=1]~-~\frac{1}{2}|
=|\frac{1}{2}~\Pr[b'=0|b=0]~+~\frac{1}{2}~\Pr[b'=1|b=1]~-~\frac{1}{2}|

ここで、

  • \Pr[b'=0|b=0]~=~\Pr^{(V)}[\neg(S=failure)]~=~1-\Pr^{(IV)}[S=failure]
  • \Pr[b'=1|b=1]~=~\Pr^{(VI)}[S=failure]

が成り立つので、

Adv(B)
=|\frac{1}{2}~(1-\Pr^{(V)}~[S=failure])~+~\frac{1}{2}\Pr^{(VI)}~[S=failure]~-~\frac{1}{2}|
=|\frac{1}{2}~\Pr^{(VI)}~[S=failure]~-~\frac{1}{2}~\Pr^{(V)}~[S=failure]|
=\frac{1}{2}~|\Pr^{(VI)}~[S=failure]~-~\Pr^{(V)}~[S=failure]|

 仮定より、|\Pr^{(VI)}~[S=failure]~-~\Pr^{(V)}~[S=failure]|:non-negなので、Adv(B)もnon-negになる。しかし、aHCはhidingを持つので、Adv(B)がnon-negであることに矛盾する。

 ゆえに、次の主張が成り立つ。

\forall~A,\forall~Z;|\Pr^{(VI)}[S=failure]-\Pr^{(V)}[S=failure]|:neg

(V)~\overset{c}{\approx}~(VI)

 以上で(IV)から(V),(VI)と(III)に近づけていった。(VI)と(III)を比較すると、(VI)はfailureを出力する可能性があるだけで、後は(III)とまったく同じ状況になった。

 最後に(VI)のときのSがfailureを出力する確率がnegであることを示せば、すべてが識別不可能であることがわかる。それでは、(VI)のとき、Sがfailureを出力する確率がnegligibleであることを示す。

 Sはハミルトンサイクルに相当するxを知らないので、failureを出力する条件を満たさない。よって、Sはnegな確率でしか、failureを出力できない。これは直観的な説明であり、厳密に背理法を使う。

 Sが(VI)において、failureを出力する確率がnon-negと仮定する。このときyを入力としてxを出力するアルゴリズムBを作ることを確かめる。

 Bはyを入力として、IDEAL実行を行うZをactivateとする。そのとき、入力yをCRSとしてZの世界に見せる。このとき(VI)のSはxなしでfailureを出力する。

 failureを出力したら、z*,r0,r1を用いてxを計算する。

 実際にアルゴリズムBが作れた。しかし、yからxを求めるのはNP問題ので、BがPPTであることに矛盾する。

 ゆえに、Sは(VI)においてfailureを出力する確率はnegである。

 したがって、最終的に∀(Aと)Zに対して(I)と(IV)は識別不可能である。

(I)~\overset{c}{\approx}~(IV) □

参考文献

  • ゼミノート
  • Lindell. "Composition of Secure Multi-Party Protocols"