[[ランダムオラクルモデル]]をイデアルファンクショナリティ化したものを用いる。そのイデアルファンクショナリティをFSUB{RO};とする。k:セキュリティパラメータ~PSUB{1};,...,PSUB{n};:パーティー~S:アドバーサリー~とする。schemeであるC={CSUB{k};,VSUB{k};}の存在を仮定する。CSUB{k};,VSUB{k};はそれぞれ次のように動作する確率的アルゴリズムである。schemeなので、hiding,bindingの性質も持っている。このスキームCを使って、comとdecの対を作る(com,decそれぞれビットストリング)。CRSのように公開鍵と秘密鍵の対(公開情報とトラップドアの対)に対応するわけだ。[定義]~comSUB{K};SUP{C};(m):入力mにおいて走らせたときのCSUB{k};の出力の第1コンポーネント~decSUB{K};SUP{C};(m):入力mにおいて走らせたときのCSUB{k};の出力の第2コンポーネント~とする。~特にcomSUB{K};SUP{C};(m)とdecSUB{K};SUP{C};(m)は確率的アルゴリズムにViewされることができる。FSUB{SCOM};という新しいファンクショナリティ考える。これはCOMMITフェーズがFSUB{MCOM};と異なる。これは次のようなアタックに注意するためである。ZによってパーティーPSUB{i};は入力bでinvokeされる。それから任意のメッセージが配達される前にZはAにPSUB{i};をcorruptさせるように指示し、b’(≠b)を使って始めからプロトコルの実行を成し遂げさせる。いうZのアタックを考えると、IDEAL内ではPSUB{i};がすでにcorruptされた時点で、最初のPSUB{i};の入力bはすでにFSUB{MCOM};にフォワードされているので変更できない。REAL内ではcorruptされたときにPiはリセットされるので、b’(≠b)がcommitされる。これではZがREALとIDEALを区別できてしまう。ここでは、FSCOMを使い、Aがcommitterをcorruptしても偽造したb’を作れないように、Aの動きを制限する(ただし、Zはb’を作れる)。することでシミュレーションを解決させるわけだ。実質的にFSUB{SCOM};とFSUB{MCOM};は同じと見なせる。別の解決方法として、アドバーサリーがパーティーからイデアルファンクショナリティへ送るメッセージを遅らせることができるようにフレームワークを変更するという方法もある[CLOS02]。それではFSUB{SCOM};の仕様を説明する。PSUB{1};,...,PSUB{n};:パーティー~PSUB{i};:sender(commiter)~PSUB{j};:receiver~S:アドバーサリー~l:すでに受信されたrequestメッセージに1をプラスしたもの~とする。PSUB{i};,PSUB{j};,m)を受け取ったら、まず始めにSにメッセージ(request,sid,ssid,PSUB{i};,PSUB{j};)を送る。Sが対応するreadyメッセージを発行したら、ステップ3まで実行する。アドバーサリーから(ready,sid,ssid,PSUB{i};,PSUB{j};,l)を受け取り、少なくともl個のメッセージ(commit,sid,ssid,PSUB{i};,PSUB{j};,m)(可能な限りmは異なる)をPSUB{i};から受け取ったら、その度にステップ3を実行する(mごと、即ちl回実行する)。PSUB{i};,PSUB{j};)を送る。以降、PSUB{i};からPSUB{j};へ同じssidのメッセージが来ても無視する。[2]REVEALフェーズPSUB{i};から(reveal,sid,ssid,PSUB{j};)を受け取ったら、次を実行する。(ssid,PSUB{i};,PSUB{j};,m)が記録されていれば、PSUB{j};とSへ(reveal,sid,ssid,PSUB{j};,m)を送る。図示すると次のようになる。FSUB{SCOM};からSへ何通もrequestメッセージが届いている。Sは何通届いたかカウントしておいて、最後の届いたときの値をl(エル)にセットして、readyメッセージをFSUB{SCOM};に送る。これにより、SはFSUB{SCOM};がPSUB{j};にreceiptメッセージを送るタイミングを制御できていることになる。次に、このFSUB{SCOM};を実現することが期待できるプロトコルHCSUB{C};を考える。プロトコルHCSUB{C};の仕様は次の通りである。commitmentスキーム~とする。PSUB{i};はメッセージ(commit,sid,ssid,PSUB{i};,PSUB{j};,m)を受け取ったら、kビットのランダム値rSUB{1};を作る。FSUB{RO};ファンクショナリティに(ssid,i,j,m,rSUB{1};)を送る。FSUB{RO};ファンクショナリティはOSUB{sid};(ssid,i,j,m,rSUB{1};)をPSUB{i};へ返す。それから、CSUB{k};を使ってcomとdecのペアである(comSUB{1};,decSUB{1};)←CSUB{k};(OSUB{sid};(ssid,i,j,m,rSUB{1};);rSUB{2};)を作る。ここでrSUB{2};はランダムテープとする。次に、rSUB{2};もFROファンクショナリティに送り、PSUB{i};はOSUB{sid};(rSUB{2};)を返してもらう。それからCSUB{k};を使ってcomとdecのペアである(comSUB{2};,decSUB{2};)←CSUB{k};(OSUB{sid};(rSUB{2};);rSUB{3};)を作る。ここでrSUB{3};はランダムテープとする。最後に(ssid,j,m,rSUB{1};,rSUB{2};,decSUB{2};)を記録してから、PSUB{j};へ(sid,ssid,comSUB{1};,comSUB{2};)を送る。PSUB{j};は(sid,ssid,comSUB{1};,comSUB{2};)を受け取ったら、初めてのメッセージなら(receipt,sid,ssid,PSUB{i};,PSUB{j};)を出力する。PSUB{i};はメッセージ(reveal,sid,ssid)を受け取ったら、COMMITフェーズで記録したデータと比較して(ssid,j,m,rSUB{1};,rSUB{2};,decSUB{2};)が記録されているかチェックする。記録されていれば、PSUB{j};へ(ssid,j,m,rSUB{1};,rSUB{2};,decSUB{2};)を送信する。記録されていなければ何もしない。PSUB{j};はVSUB{k};を使ってoSUB{2};←VSUB{k};(comSUB{2};,decSUB{2};)のように計算する。それからREVEALフェーズで受け取ったrSUB{2};をFSUB{RO};ファンクショナリティに送り、PSUB{j};はOSUB{sid};(rSUB{2};)を返してもらう。FSUB{RO};ファンクショナリティに(ssid,i,j,m,rSUB{1};)を送り、PSUB{j};はOSUB{sid};(ssid,i,j,m,rSUB{1};)を返してもらう。oSUB{2};=OSUB{sid};(rSUB{2};)∧comSUB{K};SUP{C};(OSUB{sid};(ssid,i,j,m,rSUB{1};);rSUB{2};)=comSUB{1};が成り立てば(reveal,sid,ssid,PSUB{i};,PSUB{j};,m)を出力し、成り立たなければ何もしない。図示すると次のようになる。[#g7bf0e6f][定理]~認証リンク仮定の下で、プロトコルHCSUB{C};はFSUB{RO};ハイブリッドモデル内でadaptiveアドバーサリーに対してFSUB{MCOM};を安全に実現する。IDEAL_{F_{MCOM},S,Z}");を証明すればよい。このときのプロトコルの実行はHCSUB{C};の仕様を見てみると明らかである。それにZとAを追加して考えるだけでよい。FSUB{RO};ファンクショナリティからの送信はAに送られる。AはCOMMITフェーズとREVEALフェーズの通信を覗き見できる。以上がAのViewである。ZはAの報告とPSUB{j};のローカル出力をチェックする。SはFSUB{MCOM};からreceiptメッセージを受け取ったら、kビットのsと任意のビットのrSUB{2};,rSUB{3};をランダムに選ぶ。sとrSUB{2};でcomSUB{1};=comSUB{K};SUP{C};(s;rSUB{2};)を作る。シミュレートされたFSUB{RO};ファンクショナリティにrSUB{2};を送り、OSUB{sid};(rSUB{2};)を受け取る。この受け取った値OSUB{sid};(rSUB{2};)とさきほど作ったランダム値rSUB{3};でcomSUB{2};=comSUB{K};SUP{C};(OSUB{sid};(rSUB{2};);rSUB{3};)を作る。このときdecSUB{2};も作成されていることに注意。このdecSUB{2};はREVEALフェーズにおけるSのシミュレーションで使われる。Aにトランスクリプト(sid,ssid,comSUB{1};,comSUB{2};)を渡す。ここでのポイントはSはmを知らずにcomSUB{1};,comSUB{2};を作っているということだ。SはFSUB{MCOM};からメッセージ(reveal,sid,ssid,PSUB{i};,PSUB{j};,m)を受け取ったら、任意のビットのrSUB{1};をランダムに選ぶ。シミュレートしたFSUB{RO};ファンクショナリティのListに<ssid,i,j,m,rSUB{1};;s>というTableを追加する。Sは自由に内部でシミュレーションしているFSUB{RO};ファンクショナリティにTableを自由に追加でき、一方Aは外部にあるFSUB{RO};ファンクショナリティにアクセスさせているというのが、Sにアドバンテージを与えているところである。後はこのTableすでにListにあるときが問題だが、rSUB{1};の*ビット数が十分大きいならば、その確率はnegになる。Aにトランスクリプト(sid,ssid,m,rSUB{1};,rSUB{2};,decSUB{2};)を渡す。decSUB{2};はCOMMITフェーズのSがすでに作っている。PSUB{i};をcorruptしたAはCOMMITフェーズのcomSUB{1};とcomSUB{2};を偽造する可能性がある。REVEALフェーズでm,rSUB{1};,rSUB{2};,decSUB{2};を偽造する可能性がある。PSUB{j};はREVEALフェーズで検証式をチェックし、成り立てばm(偽造したならmSUP{*};)をローカル出力する。AからPSUB{i};をcorruptするように指令が来たら、SはPSUB{i};をcorruptする。COMMITフェーズにおいて、Zからの命令はそのままシミュレートされたPSUB{i};をcorruptしているAにフォワードする。するとREALのときと同様に、Aは(sid,ssid,comSUB{1};SUP{*};,comSUB{2};SUP{*};)をシミュレートされたPSUB{j};へ送る。次にSはcomSUB{1};SUP{*};,comSUB{2};SUP{*};からmを作る。Sはそのmをセットして、(commit,sid,ssid,PSUB{i};,PSUB{j};m)メッセージをFSUB{MCOM};へ送る。REVEALフェーズでも、同様にZからの命令はそのままシミュレートされたPSUB{i};をcorruptしているAにフォワードする。するとREALのときと同様に、Aは(sid,ssid,mSUP{*};,rSUB{1};SUP{*};,rSUB{2};SUP{*};,decSUB{2};SUP{*};)をシミュレートされたPSUB{j};へ送る。それからSは(reveal,sid,ssid)メッセージをFSUB{MCOM};へ送る。するとPSUB{j};はmをローカル出力する。REALとIDEALの場合のPjのローカル出力が異なる。REALではmSUP{*};、IDEALではmを出力している。そこでmSUP{*};=mを示す。\)");を出力する。\)");が成り立つ。なる確率が下がってしまうことに注意。そこで、次のようにrSUB{2};に関するレコードがあるとしなければならない。マルチセッション特有のssidの問題をチェックしなければならない。ZがREALとIDEALを区別するために様々な努力をするわけなので、そのうちで想定されるSにとって厄介な状況として次が挙げられる。PSUB{i};とPSUB{j};の両方ともhonestのときをssid=1とする。このときにSはAにトランスクリプトとして見せる。このトランスクリプトにcomSUB{1};SUP{*};が含まれていたとする。Aはこれを受け取った後に、Zに報告する。Zは一旦ssid=1のほうを放置して、PSUB{i};がcorruputされた状態であるssid=2を開始したとする。シミュレートされたPSUB{i};をcorruptしたAは、先ほどのcomSUB{1};SUP{*};の情報を受け取り、シミュレートされたPSUB{j};へのメッセージの一部にそのまま利用したとする。これはssid=1のときはSがmを知らずにcomSUB{1};SUP{*};を作り出すというAより有利な点があったが、このとき作ったこの値をssid=2のときに逆にAとZ側に利用されてしまい、Sが今度は困ったことになってしまったわけだ。commit値がcomSUB{1};SUP{*};となる確率を考えなければならない。ランダム値のcommit値はランダム値である。よって、ランダム値と定数が一致する確率はnegである。ゆえにAとZによるこの戦略をSはうまく打破できたことになる。AがPSUB{j};をcorruptするとき、ローカル出力はZに直接送信する。SはPSUB{i};とPSUB{j};がhonestのときと同じ動きをすれば、シミュレーションは成功する。後はadaptiveアドバーサリーを考慮しなければならない。COMMITフェーズでSがAにトランスクリプトを渡した後に、AがPSUB{i};をcorruptしたときを考える。AがPSUB{i};をcorruptしようと命令を送ったら、SはPSUB{i};をcorruptして、PSUB{i};の内部ステートを渡さなければならない。SはPSUB{i};をcorruptしたとき、mを得る。後はmのつじつまを合わせなければならない。ランダムストリングrSUB{1};を選び、<ssid,i,j,m,rSUB{1};,s>というTableをListに追加する。その後(rSUB{1};,rSUB{2};,rSUB{3};)をAに渡す。#img(http://security2600.sakura.ne.jp/main2/image1/HCC_FRO9.jpg)#img(,clear)。