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

目次

宣伝

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

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

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

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

グラフ非同型に対するinteractive proof system

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

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

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

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

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

グラフ非同型に対するinteractive proof systemの安全性

completeness

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

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

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

 ゆえに、completenessは示せた。 □

soundness

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

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

 ゆえに、soundnessは示せた。 □

参考文献

  • 『暗号理論の基礎』