暗号勉強会

あまりコードが出てこない話

対話証明系のモチベーション

ゼロ知識証明はもともと対話証明系というモデルから生まれた。この記事は基礎に立ち返って、対話証明系からゼロ知識証明の歴史を探ってみる。なお、ここで示している対話証明はゼロ知識ではないので、検証者に証拠などを提出してもよい。

NP証明系

対話証明（IP）というのはおおざっぱにいえばNPを確率的にした問題のクラスである。クラスNPに属する言語は以下のように定義されていた。

  • 問題に対する証拠wが与えられたとき、その証拠wが本当に正しいかどうかを多項式時間で判定できる。

これを別の言葉で言い換えると、NPは「問題を多項式時間で解くことは出来ないが、その証拠wが与えられた時、多項式時間で検証できるような多項式時間検証器Vが存在する問題のクラス」と言い換えられる。

これを証明者Pと検証者Vから定義される証明に簡単に拡張できる。

  1. まず、無限の計算能力を持つ証明者Pと多項式時間の検証者Vがいて、証明者Pが証拠wを持っている。証明者Pは検証者Vに証拠wがあることを納得させたい。

  2. PはVに証拠を渡し、Vはそれを多項式時間で検証する。

NPの定義よりVは証拠があれば多項式時間で検証できる。ここで

  • 証明者が無限の計算能力なのは、証明を見つけるのに時間がかかるから
  • 検証者が多項式時間なのは、多項式時間でなければNP問題を解けてしまうから

有名なグラフ同型問題で考えてみよう。wikipediaだがグラフ同型問題について詳しく書いてある。

ja.wikipedia.org

対話証明では２つのグラフが同型であることを示したい場合、そのグラフの同型写像が存在すること示せばよい。ゼロ知識ではないので証拠を示せば証明は簡単に終わる。

f:id:ATen:20201022002227p:plain
グラフ同型問題

これを多項式時間検証器VがNP証明系を定義するという。これはNPというクラスを違う視点から見た結果にすぎない。

対話証明系

NP証明系は検証手順を

  • 「証明者からもらった証拠で問題が正しいか検証する」という決定的なアルゴリズム

に限っている。これを確率的なアルゴリズムに拡張することで高い表現力が得られると思われる（ここで「思われる」とあるのはNPがIPの真部分集合か明らかではないから）。

NPを自然に確率的なアルゴリズムに拡張したものをIP(対話証明)という。

この対話証明では証明にコイン投げと対話を許すことで確率的な証明を行う。実際にグラフ非同型問題をIPで受理できることを示す。

グラフ非同型問題のプロトコル

グラフ非同型問題はco-NP問題に属する問題である。co-NP問題は

  • NP問題の否定問題で、現状NP問題に属しているかどうかは明らかでない。そのco-NP問題であるグラフ非同型問題は、NPに含まれない（と予想されている）のでNP証明系で証明することはできない。

実際に「非同型である」ことを証拠一つで証明するのは難しそうである。同型問題あれば、同型写像を一つ示せばよかったのだが。

ここで対話証明が活躍する。対話証明は一回で証明を終えるのではなく、何回かの対話の中で検証者を納得させればよい。ここで証明者と検証者の 共通入力をグラフG _ 0=(V _ 0,E _ 0)とグラフG _ 1=(V _ 1,E _ 1)とおく。

f:id:ATen:20201022002823p:plain
非同型問題

  1. 検証者はa=0かa=1を選ぶ。その後、G _ aと同型なグラフG'=(V',E')を証明者に送る。

  2. 証明者はG'=(V',E')を受け取ったら、検証者が(G _ 0,G _ 1)のどちらと同型なグラフを送ってきたか判定する。G _ 0ならb=0を、G _ 1ならb=1を送る。

  3. 検証者はa=bなら、1を出力する。そうでなければ0を出力して停止する。

ここで以下の点に注意してほしい。

  • 2で(G _ 0,G _ 1)がもし非同型なら、どちらと同型なグラフを送ってきたか特定できる。

  • 検証者はこの処理を十分な回数繰り返して、停止しなければ初めて証明を受理する。非同型でないのに受理される確率は、何度も繰り返せば限りなく低い確率になる。

なお、検証者はaをランダムに選択しなければならない。ランダムでなければ、検証者の行動が予測可能になるからである。検証者が乱数を返すようにすれば証明者は多くとも1/2の確率でしか騙せない。

対話証明のポイント

以下は対話証明の２つのポイントである。

  • 確率的にすると、決定性アルゴリズムと比べると表現力が上がる。しかし、検証者は確率的になるので必ず正しい結果を返すわけではない。
  • 対話的にすると、確率的アルゴリズムの欠点である「検証者が必ず正しい結果を返すわけではないこと」を解消できる。検証者が必ず正しい結果を返さなくても1/2より高い確率で正しい返答をしていれば、いつか証明は限りなく正しいものになる。

IP(Interactive Proof)

そして、上の対話証明が可能な言語のクラスをIPという。IPは以下のように定義される。

次の条件を満たす多項式時間関数Vと関数Pが存在し、多項式回の対話で証明が可能なら言語LはIPに属する。

  • x\in Lの時にPr[V=1]\geq 2/3
  • x\notin Lの時にP[V=0]\geq 2/3

ここで2/3となっているが、究極には1/2より大きければよい。IPはNPに含まれていないとされるグラフ非同型問題のようなco-NP問題の証明に利用できるほど強力であり、NP\subseteq IPであることが知られている。さらにIPにおける重要な事実として

IP=PSPACE=CZK

がある。ここでPSPACEは多項式領域で計算できる問題のクラスであり、CZKは計算量的ゼロ知識証明が存在する言語のクラスである。（計算量的ゼロ知識証明というのは後に解説する予定） NP\subseteq IPであることからNP\subseteq CZKでもある。これはNP問題には必ず（計算量的）ゼロ知識証明が必ず存在するという驚きの事実である。

まとめ

この記事ではIPについて説明した。次の記事ではゼロ知識証明そして、知識の証明について解説する予定である。

参考文献