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

#contents


*グラフ非同型に対するinteractive proof system [#nb853b56]

 グラフ非同型に対するinteractive proof systemの仕様を図にすると次の通りである。

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

例:V={1,2,3,4}、ESUB{1};={12,14,23,34}、ESUB{2};={12,13,14,34}とする。このとき2つのグラフGSUB{1};とGSUB{2};は次のようになる。

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

 VはPへ置換(グラフの点と線を固定したまま、数値をランダムにするようなもの)した結果のH=(V,ESUB{3};)(ESUB{3};={13,14,23,24})を送ったとする。

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

 HはGSUB{1};と同型(頂点の数値は見ないで点と線で構成される形だけ見る)なので、Pはj=1をVへ送る。 ◇

 ポイントは置換を何度やってもグラフの同型という観点からは変わらないという点である。


*グラフ非同型に対するinteractive proof systemの安全性 [#sd496a75]

**completeness [#t4d6f1e4]

 completenessなので、Pがグラフ非同型問題Πのwitnessを知っているという状態である。

 まず、PはVから置換後のグラフであるHを受け取る。ただし、置換されていたとしても同型であることは維持されていることに注意。Pはグラフ非同型問題の答えを知っているので、HがPSUB{1};,PSUB{2};のどちらと非同型であるかどうかわかる。ここでは2つのグラフだけで比較しているので、Hが仮にPSUB{1};と非同型がわかるということは、HがPSUB{2};と同型ということは絞り込める。よって、Pは実質的に同型である側もわかるということである。つまり、常にi=jになるようにjを選ぶことができるということになる。

 n回のすべてのラウンドでi=jとなるようにjを選ぶことができるので、Vは必ずacceptする。

 ゆえに、completenessは示せた。 □


**soundness [#ce41a4c4]

 soundnessなので、Pがグラフ非同型問題Πのwitnessを知らないという状態である。

 まず、PはVから置換後のグラフであるHを受け取る。しかし、Pはグラフ非同型問題の答えを知らないので、HがPSUB{1};,PSUB{2};のどちらと非同型であるか判断できない。よって、jは勘で選ぶしかない。勘で選んで、i=jになる可能性は1/2の確率である。Vはnラウンドのi=jをチェックするので、すべてにおいてi=jが成り立つ確率は1/2SUP{n};になる。よって、nが十分大きいとき、witnessを知らないPがVをacceptさせることができる確率はほとんどゼロである。

 ゆえに、soundnessは示せた。 □