このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ
*目次 [#o3aa70c4]

#contents


*ROファンクショナリティ [#vb063665]

 [[ランダムオラクルモデル]]をイデアルファンクショナリティ化したものを用いる。そのイデアルファンクショナリティをFSUB{RO};とする。

k:セキュリティパラメータ~
PSUB{1};,…,PSUB{n};:パーティー~
S:アドバーサリー~
とする。

#img(http://security2600.sakura.ne.jp/main2/image1/FRO.jpg)
#img(,clear)


*non-interactive string commitment scheme [#y4f1745c]

 non-interactive string commitment schemeであるC={CSUB{k};,VSUB{k};}の存在を仮定する。CSUB{k};,VSUB{k};はそれぞれ次のように動作する確率的アルゴリズムである。

#img(http://security2600.sakura.ne.jp/main2/image1/ck.jpg)
#img(,clear)

#img(http://security2600.sakura.ne.jp/main2/image1/vk.jpg)
#img(,clear)

 さらに、commitment 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};とHCSUB{C}; [#f22e7496]

 まず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をプラスしたもの~
とする。

[1]COMMITフェーズ

1. PSUB{i};からメッセージ(commit,sid,ssid, PSUB{i};,PSUB{j};,m)を受け取ったら、まず始めにSにメッセージ(request,sid,ssid,PSUB{i};,PSUB{j};)を送る。そしてもしSが対応するreadyメッセージを発行したら、ステップ3まで実行する。

2. アドバーサリーから(ready,sid,ssid,PSUB{i};,PSUB{j};,l)を受け取り、少なくともl個のメッセージ(commit,sid,ssid,PSUB{i};,PSUB{j};,m)(可能な限りmは異なる)をPSUB{i};から受け取ったら、その度にステップ3を実行する(mごと、即ちl回実行する)。

3. (ssid,PSUB{i};,PSUB{j};,m)を記録し、PSUB{j};へ(receipt,sid,ssid, 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)を送る。そうでなければ、無視する。

 図示すると次のようになる。

#img(http://security2600.sakura.ne.jp/main2/image1/FSCOM.jpg)
#img(,clear)

 FSUB{SCOM};からSへ何通もrequestメッセージが届いている。Sは何通届いたかカウントしておいて、最後の届いたときの値をl(エル)にセットして、readyメッセージをFSUB{SCOM};に送る。これにより、SはFSUB{SCOM};がPSUB{j};にreceiptメッセージを送るタイミングを制御できていることになる。

 次に、このFSUB{SCOM};を実現することが期待できるプロトコルHCSUB{C};を考える。プロトコルHCSUB{C};の仕様は次の通りである。

PSUB{i};:sender(commiter)~
PSUB{j};:receiver~
C={CSUB{k};,VSUB{k};}:non-interactive string commitmentスキーム~
とする。

[1]COMMITフェーズ

 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};)を出力する。そうでなければ何もしない。

[2]REVEALフェーズ

 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)を出力し、成り立たなければ何もしない。

 図示すると次のようになる。

#img(http://security2600.sakura.ne.jp/main2/image1/HCC.jpg)
#img(,clear)


*UC Commitmentの実現可能証明 [#g7bf0e6f]

[定理]~
認証リンク仮定の下で、プロトコルHCSUB{C};はFSUB{RO};ハイブリッドモデル内でadaptiveアドバーサリーに対してFSUB{MCOM};を安全に実現する。

[証明]

&mimetex("\forall A,\exists S ,\forall Z ; HYB_{HC_{C},A,Z}^{F_{RO}} \approx IDEAL_{F_{MCOM},S,Z}");を証明すればよい。

[1]PSUB{i};とPSUB{j};が両方ともcorruptされているときは明らか

[2]PSUB{i};とPSUB{j};が両方ともhonestのとき

[HYB]

 このときのプロトコルの実行はHCSUB{C};の仕様を見てみると明らかである。それにZとAを追加して考えるだけでよい。~
 FSUB{RO};ファンクショナリティからの送信はAに送られる。またAはCOMMITフェーズとREVEALフェーズの通信を覗き見できる。以上がAのViewである。~
 ZはAの報告とPSUB{j};のローカル出力をチェックする。

#img(http://security2600.sakura.ne.jp/main2/image1/HCC_FRO1.jpg)
#img(,clear)

[IDEAL]~
<COMMITフェーズ>

 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};を作っているということだ。

#img(http://security2600.sakura.ne.jp/main2/image1/HCC_FRO2.jpg)
#img(,clear)

<REVEALフェーズ>

 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がすでに作っている。

#img(http://security2600.sakura.ne.jp/main2/image1/HCC_FRO3.jpg)
#img(,clear)

[3]PSUB{i};がcorruptされ、PSUB{j};がhonestのとき~
[HYB]

 PSUB{i};をcorruptしたAはCOMMITフェーズのcomSUB{1};とcomSUB{2};を偽造する可能性がある。~
 またREVEALフェーズでm,rSUB{1};,rSUB{2};,decSUB{2};を偽造する可能性がある。~
 PSUB{j};はREVEALフェーズで検証式をチェックし、成り立てばm(偽造したならmSUP{*};)をローカル出力する。

#img(http://security2600.sakura.ne.jp/main2/image1/HCC_FRO4.jpg)
#img(,clear)

[IDEAL]

 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を作る。

#mimetex("\exists m,\exists r_1,\exists r_2 ; com_{1}^{*} = com_{K}^{C} \( O_{sid} \( ssid,i,j,m,r_{1}\),r_{2} \) \wedge o_{2}=O_{sid} \( r_{2} \)");

 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をローカル出力する。

#img(http://security2600.sakura.ne.jp/main2/image1/HCC_FRO5.jpg)
#img(,clear)

 REALとIDEALの場合のPjのローカル出力が異なる。REALではmSUP{*};、IDEALではmを出力している。そこでmSUP{*};=mを示す。~
 Aは偽造したmSUP{*};を含むメッセージ&mimetex("com_{1}^{*} = com_{K}^{C} \( O_{sid} \( ssid,i,j,m^{*},r_{1}^{*}\),r_{2}^{*} \)");を出力する。一方S内部で&mimetex("com_{1}^{*} = com_{K}^{C} \( O_{sid} \( ssid,i,j,m,r_{1}\),r_{2} \)");が成り立つ。~
 よって次が成り立つ。

&mimetex("com_{K}^{C} \( O_{sid} \( ssid,i,j,m,r_{1}\),r_{2} \) = com_{K}^{C} \( O_{sid} \( ssid,i,j,m^{*},r_{1}^{*}\),r_{2}^{*} \)");

&mimetex("O_{sid} \( ssid,i,j,m,r_{1}\) = O_{sid} \( ssid,i,j,m^{*},r_{1}^{*} \)"); (∵Cのbinding)

&mimetex(" \( ssid,i,j,m,r_{1}\) =  \( ssid,i,j,m^{*},r_{1}^{*} \)");

∴&mimetex(" m =  m^{*}");

 ここで、rSUB{2};がListのTableにないとREALから比べて、IDEALで となる確率が下がってしまうことに注意。そこで、次のようにrSUB{2};に関するレコードがあるとしなければならない。

|ssid,i,j,m,rSUB{1};|hSUB{1};|
||hSUB{2};|
|・・・||
|rSUB{2};|oSUB{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が今度は困ったことになってしまったわけだ。~
 そこで、&mimetex("\< ssid,i,j,m,r_1 ; r_2 \> \not\in List");ならば、ランダム変数である のcommit値がcomSUB{1};SUP{*};となる確率を考えなければならない。しかしながら、ランダム値のcommit値はランダム値である。よって、ランダム値と定数が一致する確率はnegである。~
 ゆえにAとZによるこの戦略をSはうまく打破できたことになる。

#img(http://security2600.sakura.ne.jp/main2/image1/HCC_FRO6.jpg)
#img(,clear)

[4]PSUB{i};がhonest、PSUB{j};がcorruptされているとき~
[HYB]

 AがPSUB{j};をcorruptするとき、ローカル出力はZに直接送信する。

#img(http://security2600.sakura.ne.jp/main2/image1/HCC_FRO7.jpg)
#img(,clear)

[IDEAL]

 SはPSUB{i};とPSUB{j};がhonestのときと同じ動きをすれば、シミュレーションは成功する。

#img(http://security2600.sakura.ne.jp/main2/image1/HCC_FRO8.jpg)
#img(,clear)

 後は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)