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

目次

宣伝

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

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

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

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

ROファンクショナリティ

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

k:セキュリティパラメータ
P1,…,Pn:パーティー
S:アドバーサリー
とする。

non-interactive string commitment scheme

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

 さらに、commitment schemeなので、hiding,bindingの性質も持っている。 このスキームCを使って、comとdecの対を作る(com,decそれぞれビットストリング)。CRSのように公開鍵と秘密鍵の対(公開情報とトラップドアの対)に対応するわけだ。

[定義]
comKC(m):入力mにおいて走らせたときのCkの出力の第1コンポーネント
decKC(m):入力mにおいて走らせたときのCkの出力の第2コンポーネント
とする。
特にcomKC(m)とdecKC(m)は確率的アルゴリズムにViewされることができる。

FSCOMとHCC

 まずFSCOMという新しいファンクショナリティ考える。これはCOMMITフェーズがFMCOMと異なる。これは次のようなアタックに注意するためである。

 ZによってパーティーPiは入力bでinvokeされる。それから任意のメッセージが配達される前にZはAにPiをcorruptさせるように指示し、b’(≠b)を使って始めからプロトコルの実行を成し遂げさせる。こういうZのアタックを考えると、IDEAL内ではPiがすでにcorruptされた時点で、最初のPiの入力bはすでにFMCOMにフォワードされているので変更できない。一方、REAL内ではcorruptされたときにPiはリセットされるので、b’(≠b)がcommitされる。これではZがREALとIDEALを区別できてしまう。

 ここでは、FSCOMを使い、Aがcommitterをcorruptしても偽造したb’を作れないように、Aの動きを制限する(ただし、Zはb’を作れる)。そうすることでシミュレーションを解決させるわけだ。つまり実質的にFSCOMとFMCOMは同じと見なせる。

 別の解決方法として、アドバーサリーがパーティーからイデアルファンクショナリティへ送るメッセージを遅らせることができるようにフレームワークを変更するという方法もある[CLOS02]。

 それではFSCOMの仕様を説明する。

P1,…,Pn:パーティー
Pi:sender(commiter)
Pj:receiver
S:アドバーサリー
l:すでに受信されたrequestメッセージに1をプラスしたもの
とする。

[1]COMMITフェーズ

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

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

3. (ssid,Pi,Pj,m)を記録し、Pjへ(receipt,sid,ssid, Pi,Pj)を送る。以降、PiからPjへ同じssidのメッセージが来ても無視する。

[2]REVEALフェーズ

Piから(reveal,sid,ssid,Pj)を受け取ったら、次を実行する。もし(ssid,Pi,Pj,m)が記録されていれば、PjとSへ(reveal,sid,ssid,Pj,m)を送る。そうでなければ、無視する。

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

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

 次に、このFSCOMを実現することが期待できるプロトコルHCCを考える。プロトコルHCCの仕様は次の通りである。

Pi:sender(commiter)
Pj:receiver
C={Ck,Vk}:non-interactive string commitmentスキーム
とする。

[1]COMMITフェーズ

 Piはメッセージ(commit,sid,ssid,Pi,Pj,m)を受け取ったら、kビットのランダム値r1を作る。FROファンクショナリティに(ssid,i,j,m,r1)を送る。FROファンクショナリティはOsid(ssid,i,j,m,r1)をPiへ返す。
 それから、Ckを使ってcomとdecのペアである(com1,dec1)←Ck(Osid(ssid,i,j,m,r1);r2)を作る。ここでr2はランダムテープとする。
 次に、r2もFROファンクショナリティに送り、PiはOsid(r2)を返してもらう。それからCkを使ってcomとdecのペアである(com2,dec2)←Ck(Osid(r2);r3)を作る。ここでr3はランダムテープとする。
 最後に(ssid,j,m,r1,r2,dec2)を記録してから、Pjへ(sid,ssid,com1,com2)を送る。
 Pjは(sid,ssid,com1,com2)を受け取ったら、初めてのメッセージなら(receipt,sid,ssid,Pi,Pj)を出力する。そうでなければ何もしない。

[2]REVEALフェーズ

 Piはメッセージ(reveal,sid,ssid)を受け取ったら、COMMITフェーズで記録したデータと比較して(ssid,j,m,r1,r2,dec2)が記録されているかチェックする。記録されていれば、Pjへ(ssid,j,m,r1,r2,dec2)を送信する。記録されていなければ何もしない。
 PjはVkを使ってo2←Vk(com2,dec2)のように計算する。それからREVEALフェーズで受け取ったr2をFROファンクショナリティに送り、PjはOsid(r2)を返してもらう。またFROファンクショナリティに(ssid,i,j,m,r1)を送り、PjはOsid(ssid,i,j,m,r1)を返してもらう。
 o2=Osid(r2)∧comKC(Osid(ssid,i,j,m,r1);r2)=com1が成り立てば(reveal,sid,ssid,Pi,Pj,m)を出力し、成り立たなければ何もしない。

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

UC Commitmentの実現可能証明

[定理]
認証リンク仮定の下で、プロトコルHCCはFROハイブリッドモデル内でadaptiveアドバーサリーに対してFMCOMを安全に実現する。

[証明]

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

[1]PiとPjが両方ともcorruptされているときは明らか

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

[HYB]

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

[IDEAL]
<COMMITフェーズ>

 SはFMCOMからreceiptメッセージを受け取ったら、kビットのsと任意のビットのr2,r3をランダムに選ぶ。
 sとr2でcom1=comKC(s;r2)を作る。
 シミュレートされたFROファンクショナリティにr2を送り、Osid(r2)を受け取る。この受け取った値Osid(r2)とさきほど作ったランダム値r3でcom2=comKC(Osid(r2);r3)を作る。このときdec2も作成されていることに注意。このdec2はREVEALフェーズにおけるSのシミュレーションで使われる。
 Aにトランスクリプト(sid,ssid,com1,com2)を渡す。ここでのポイントはSはmを知らずにcom1,com2を作っているということだ。

<REVEALフェーズ>

 SはFMCOMからメッセージ(reveal,sid,ssid,Pi,Pj,m)を受け取ったら、任意のビットのr1をランダムに選ぶ。
 シミュレートしたFROファンクショナリティのListに<ssid,i,j,m,r1;s>というTableを追加する。Sは自由に内部でシミュレーションしているFROファンクショナリティにTableを自由に追加でき、一方Aは外部にあるFROファンクショナリティにアクセスさせているというのが、Sにアドバンテージを与えているところである。
 後はこのTableすでにListにあるときが問題だが、r1の*ビット数が十分大きいならば、その確率はnegになる。
 Aにトランスクリプト(sid,ssid,m,r1,r2,dec2)を渡す。dec2はCOMMITフェーズのSがすでに作っている。

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

 PiをcorruptしたAはCOMMITフェーズのcom1とcom2を偽造する可能性がある。
 またREVEALフェーズでm,r1,r2,dec2を偽造する可能性がある。
 PjはREVEALフェーズで検証式をチェックし、成り立てばm(偽造したならm*)をローカル出力する。

[IDEAL]

 AからPiをcorruptするように指令が来たら、SはPiをcorruptする。COMMITフェーズにおいて、Zからの命令はそのままシミュレートされたPiをcorruptしているAにフォワードする。するとREALのときと同様に、Aは(sid,ssid,com1*,com2*)をシミュレートされたPjへ送る。
 次にSはcom1*,com2*からmを作る。

\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,Pi,Pjm)メッセージをFMCOMへ送る。

 REVEALフェーズでも、同様にZからの命令はそのままシミュレートされたPiをcorruptしているAにフォワードする。するとREALのときと同様に、Aは(sid,ssid,m*,r1*,r2*,dec2*)をシミュレートされたPjへ送る。
 それからSは(reveal,sid,ssid)メッセージをFMCOMへ送る。するとPjはmをローカル出力する。

 REALとIDEALの場合のPjのローカル出力が異なる。REALではm*、IDEALではmを出力している。そこでm*=mを示す。
 Aは偽造したm*を含むメッセージcom_{1}^{*}~=~com_{K}^{C}~\(~O_{sid}~\(~ssid,i,j,m^{*},r_{1}^{*}\),r_{2}^{*}~\)を出力する。一方S内部でcom_{1}^{*}~=~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}~\)~=~com_{K}^{C}~\(~O_{sid}~\(~ssid,i,j,m^{*},r_{1}^{*}\),r_{2}^{*}~\)

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

\(~ssid,i,j,m,r_{1}\)~=~~\(~ssid,i,j,m^{*},r_{1}^{*}~\)

m~=~~m^{*}

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

ssid,i,j,m,r1h1
h2
・・・
r2o2

 さらに、マルチセッション特有のssidの問題をチェックしなければならない。ZがREALとIDEALを区別するために様々な努力をするわけなので、そのうちで想定されるSにとって厄介な状況として次が挙げられる。PiとPjの両方ともhonestのときをssid=1とする。このときにSはAにトランスクリプトとして見せる。このトランスクリプトにcom1*が含まれていたとする。Aはこれを受け取った後に、Zに報告する。Zは一旦ssid=1のほうを放置して、Piがcorruputされた状態であるssid=2を開始したとする。シミュレートされたPiをcorruptしたAは、先ほどのcom1*の情報を受け取り、シミュレートされたPjへのメッセージの一部にそのまま利用したとする。これはssid=1のときはSがmを知らずにcom1*を作り出すというAより有利な点があったが、このとき作ったこの値をssid=2のときに逆にAとZ側に利用されてしまい、Sが今度は困ったことになってしまったわけだ。
 そこで、\<~ssid,i,j,m,r_1~;~r_2~\>~\not\in~Listならば、ランダム変数である のcommit値がcom1*となる確率を考えなければならない。しかしながら、ランダム値のcommit値はランダム値である。よって、ランダム値と定数が一致する確率はnegである。
 ゆえにAとZによるこの戦略をSはうまく打破できたことになる。

[4]Piがhonest、Pjがcorruptされているとき
[HYB]

 AがPjをcorruptするとき、ローカル出力はZに直接送信する。

[IDEAL]

 SはPiとPjがhonestのときと同じ動きをすれば、シミュレーションは成功する。

 後はadaptiveアドバーサリーを考慮しなければならない。例えばCOMMITフェーズでSがAにトランスクリプトを渡した後に、AがPiをcorruptしたときを考える。AがPiをcorruptしようと命令を送ったら、SはPiをcorruptして、Piの内部ステートを渡さなければならない。SはPiをcorruptしたとき、mを得る。後はmのつじつまを合わせなければならない。
 まずランダムストリングr1を選び、<ssid,i,j,m,r1,s>というTableをListに追加する。その後(r1,r2,r3)をAに渡す。