📝
【技術】定数ラウンドゼロ知識証明とは
はじめに
本記事では、定数ラウンドゼロ知識証明、つまり一定回数のやりとりを行うだけでゼロ知識証明を行うことができるプロトコルについて紹介します。
以前の記事「【技術】コミットメントとゼロ知識証明」で、NP完全問題のひとつである3彩色問題に対するゼロ知識証明を紹介しました。その手法は、健全性の確率を高めるために証明者と検証者の間で1つのプロトコルを何度も反復実行する必要があり、それに従ってやりとりの回数も増えていました。
そこで、やりとりの回数を減らすために並列化を行うことを考えます。ただし、愚直に並列化を行った場合にゼロ知識性が得られるどうかは知られていません。そこで、別の方法により解決することを試みます。具体的には、以前紹介したプロトコルで用いられていた計算量的秘匿かつ完全拘束なコミットメントに加えて、本プロトコルでは完全秘匿かつ計算量拘束なコミットメントも利用します。これによって定数ラウンドでのゼロ知識証明を構築することができることを説明します。
愚直な並列化で起こる問題
ここでは、以前の記事「【技術】コミットメントとゼロ知識証明」で紹介したプロトコルにおいて、愚直に並列実行した場合の健全性条件とゼロ知識性条件について考察をしてみます。並列実行版を考える前に、以前の記事において紹介したゼロ知識証明プロトコルを、健全性を達成するために何度も繰り返すプロトコルについて説明します。ここではそのプロトコルを、並列に対して直列のプロトコルとよぶことにします。
直列のプロトコル
まずは、直列のプロトコルで健全性とゼロ知識性が成り立っていることを詳細に説明します。
健全性
先の3彩色問題のゼロ知識証明プロトコルにおいて、健全性は、証明者Pのグラフ が3彩色不可能な場合に、十分高い確率でそのことが見抜ける、というものでした。逆に言えば、このような証明者Pがプロトコルを遂行できる確率は限りなく0に近いです。今回の直列プロトコルであれば、プロトコルの繰り返しを多項式回行うわけですが、その繰り返し回数に比例して遂行確率が指数的に小さくなっていく場合であれば、繰り返し回数に対して遂行確率は限りなく0に近いといえます。
証明者Pが実際にグラフ の3彩色を知らない場合、 証明者Pの持つグラフの彩色方法には 個の辺のうちで少なくとも1つ適切でない辺が存在します。いま、頂点数 のグラフ を考え、このグラフに対する3彩色問題のゼロ知識証明プロトコルを例えば 回繰り返し実行するとします。このとき、適切な辺が選ばれ続ければ検証者を騙すことができるので、検証者を騙せる確率は となります。 であることに注意すると
となり、この確率は の増加に伴って指数関数的に小さくなります。
ゼロ知識性
ゼロ知識性は、検証者Vは証明者Pがグラフの3彩色を知っているという情報以外には何の情報も得られていないという性質でした。このことをより厳密に述べると、実際のプロトコルのやりとりの系列を、検証者Vが観察できる情報だけを使って、シミュレータとよばれる平均的には多項式時間で完了するアルゴリズムによって模擬する（見分けがつかないような系列を生成する）ことができる、という性質です。
ここでは実際に、まずは繰り返し実行するゼロ知識証明プロトコルの1回に注目し、やりとりの系列の模擬の仕方、つまりシミュレーションの流れを示し、これが平均的には多項式時間で完了することを説明します。なお、以下では とし、簡単のためシミュレータと対話する検証者は正しくプロトコルに従うとします。
シミュレーションの流れ
- シミュレータのステップ (M1)
シミュレータMはランダムに と を選択します。
すべての に対して を計算します。
シミュレータMは検証者Vに を送ります。
- 検証者Vのステップ (V1)
検証者Vはランダムに を選択し、シミュレータMに送ります。
- シミュレータのステップ (M2)
シミュレータMは検証者Vから を受け取ります。
ここで の場合、正しいプロトコルのやりとりではあり得ないので、 (M1) の最初に戻ってやり直します。
一方で の場合、以降は実際のプロトコルではうまくいくはずです。よって、模擬されたやりとりの系列を出力します。ここでは , , が出力されます。
簡単に、このシミュレーション戦略について説明します。
シミュレータMには、証明者Pがステップ(P1)で送ってくるコミットメントの代わりに、それらしいものを出力してもらわなければなりません。しかし、実際の証明者Pが知っている頂点の色、そして、どのように頂点の色を入れ替えているかはよくわからず、検証者Vからすればランダムな色が観測されます。そこでステップ (M1) では、シミュレータMにランダムな色をコミットしてもらう戦略をとることにしています。
この戦略のもとで、プロトコルのやりとりとして正しい状況が現れるまでステップ (M2) で確認をし、正しいプロトコルのやりとりではありえない状況が発生したら (M1) に戻ることを何度も繰り返します。この操作をやり直す戦略のことを巻き戻し（rewinding）といいます。
シミュレーションは平均的には多項式時間で完了することが要求されます。上記のシミュレーションは、巻き戻しのステップを除けば明らかに多項式時間で実行が可能です。全体として平均的には多項式時間で実行できるプロトコルであるためには、巻き戻し回数が平均的には多項式回でなければなりません。そこで、この巻き戻し回数が平均的には多項式回であることを確認してみます。
シミュレータMはすべての頂点の彩色をランダムに選んでいるため、検証者Vがステップ (V1) でランダムに頂点 を選んだ時に となる確率は であり、 となる確率は です。したがって、 となるまでの平均巻き戻し回数は 回です。なお一般に、引き当てたい事象が発生するまでにかかる平均試行回数は、その事象の発生確率の逆数となります（幾何分布）。
このシミュレーションによってシミュレータから出力された系列 , , は、検証者Vが証明者Pとやりとりした場合に得られるやりとりの系列 , , と見分けがつきません。したがってこのプロトコルはゼロ知識性をもつといえます。
ここまで、直列プロトコルの各1回の繰り返しについて考えていました。1回の繰り返しについてのシミュレーションが平均的に多項式時間で可能であるということは、それを 回直列に繰り返したものを考えても、シミュレーションは平均的に多項式時間で可能です。具体的には、2頂点の組の彩色が異なっているかどうかを考えるにあたってグラフ は単純であると考えてよく、この場合には であることに注意すれば、平均的には 回以内の巻き戻しでシミュレーションが完了します。したがって、全体の直列プロトコルにおいてもゼロ知識性をもつといえます。
このように、健全性はプロトコル全体をみたときの性質でしたが、ゼロ知識性は、ゼロ知識証明プロトコルを直列に繰り返し実行した各1回それぞれついて成り立つ性質です。このことが、直列実行でうまくゼロ知識性が成立する理由となっています。
並列化したプロトコルでは、繰り返しがなくなり1回のプロトコルの実行となりますが、実はこのことがゼロ知識性を示すことを阻む原因となります。
並列化したプロトコル
直列のプロトコルでは、プロトコルのステップ (V1) において だけを送り、以後はそれに対応する値をやりとりしていました。並列実行とは、(V1) で を同時に送り、以後のプロトコルにおいてもそれに対応するものを同時に送ってもらうようにすることを指します。
通常のプロトコルを並列化したとき、健全性と、先ほどのシミュレーション戦略のもとで示されたゼロ知識性が同時に成立するかを考えます。
まずは健全性に注目してみます。証明者Pのグラフ が3彩色不可能な場合、 証明者Pの持つグラフには 個の辺のうちで少なくとも1つ適切でない彩色がされた辺が存在します。先ほどと同様、グラフ の 個の3彩色問題のゼロ知識証明プロトコルを並列実行するとします。このとき、適切な辺が選ばれ続ければ検証者を騙すことができるので、検証者を騙せる確率は となり、直列プロトコルと同様に で上から抑えることができます。この確率は、 が十分大きい場合は並列実行の数 に対して指数関数的に減衰し、無視することができます。
さて、この状況下でゼロ知識性は成立するでしょうか。先ほど利用したシミュレーション戦略をそのまま並列化したとして考えてみましょう。
1つの辺を選んだ時に彩色のつじつまが合っている確率は です。したがって、 個の並列プロトコルを考えると、すべての並列についてつじつまの合う辺を選ぶ状況、つまり確率 を引き当てるまで巻き戻しを行う必要があります。この確率を引き当てるまでの平均回数は、この確率の逆数、つまり 回になります。この平均の巻き戻し回数は明らかに多項式回より大きいです。したがってシミュレータは平均的には多項式時間で動かすことができず、健全性が成り立つ場合にはゼロ知識性は成り立たないことがわかります。
また、対偶を考えれば、ゼロ知識性が成り立つ場合には健全性が成り立たないこともわかります。すなわち、先ほどのシミュレーション戦略を考えている限りでは、健全性とゼロ知識性は両立しません。
よりよいシミュレーション戦略を考えることができれば、愚直な並列化でも健全性とゼロ知識性が両立できる可能性はあります。しかし、そのようなシミュレーションの方法は知られていません。
ゼロ知識性を示せる並列プロトコル構成のためのトリック
このように、愚直な並列実行では健全性とゼロ知識性が両立しているかを示すことが困難であることがわかりました。そこで、うまく並列実行でき、かつそのゼロ知識性が証明できるような仕組みとして、証明者Pがステップ (P1) で3彩色の入れ替えを送る前に、検証者Vが選択する辺たちを送ってしまう、というトリックを使います。ただし、選択する辺は実際のプロトコルにおいてバレてはいけないので、完全秘匿性をもつコミットメントスキームを利用します。一見無駄に見えるこのトリックが、ゼロ知識性を示すシミュレーション戦略の構築に大いに貢献することになります。
それでは、3彩色問題に対する定数ラウンドゼロ知識証明をみていきましょう。
3彩色問題に対する定数ラウンドゼロ知識証明
記号
以下で使用する記号たちを以下のように定めます。
- をコミットするために、一様乱数 を用いた一方向性関数によって構成された、計算量秘匿かつ完全拘束なコミットメントの暗号化関数
- をコミットするために、受け取ったメッセージ と一様乱数 を用いた、完全秘匿かつ計算量拘束なコミットメントの暗号化関数
例えば を何らかの整数値とすれば のような関数が想定されます。ここで は素数、 は をみたすような数（ の生成元）です。
以下ではグラフの辺の集合を としているため、直接上の関数が利用できるわけではありませんが、複数の を利用して構成するなどうまく拡張して利用することが想定されます。
- グラフ は、頂点集合 、辺の集合を をもつ
- ただし、多重辺やループ構造はもたない（このようなグラフを単純グラフとよぶ）
- 各頂点を、塗る色に対応する数字ラベル のいずれかに対応させる写像、つまり3色塗り分けの情報
問題設定
証明者Pはグラフ の3彩色 を知っていることを、 を検証者Vに明かすことなく示したいとします。
共有情報
証明者Pと検証者Vは単純3彩色可能グラフ を共有しているとします。
ただし 、、 とします。
プロトコルの流れ
証明者Pと検証者Vは以下のようなやりとりを行います。
- 証明者Pの予備ステップ (P0)
証明者Pは、検証者Vに最初のメッセージ を送信します。
- 検証者Vの予備ステップ (V0)
検証者Vは、一様独立に 個の辺をグラフから選択し、それを とします。
ここでは とします。
検証者Vは、一様乱数 を選択します。つまり、この一様乱数は の多項式長のビット列から選択されます。
検証者Vは、 を証明者Pに送信します。
- 証明者Pのステップ (P1)
証明者Pは、一様独立に 個の置換（ の並べ替えの仕方） と一様乱数 を選択します。
これを用いて、すべての頂点 と に対して と定めます。
は に割り当てられていた彩色を入れ替える写像です。
すべての一様乱数 に対して を計算します。
証明者Pは、 を検証者Vに送信します。
ここでは、すべての頂点に対して置換を施したものを暗号化したものを送信しています。
- 検証者Vのステップ (V1)
検証者Vは を証明者Pに送信します。
- 証明者Pのステップ (P2)
証明者Pは、(V0)で送られてきていた と、(V1)で送られてきた を用いて証明者P側で を計算し、照らし合わせて一致していることを確認します。
確かに一致していれば、証明者Pは検証者Vに以下の 個の4つ組を送信します。
ここで送信する各4つ組は、 で送った辺のそれぞれに対応します。例えば は に対応しています。次のステップで検証者Vは を手元で計算して検証する必要があるので、 を計算するのに必要となる の並べ替え と、それに対応する一様乱数 を送信しています。
- 検証者Vのステップ (V2)
検証者Vは、 (P1) で送られてきていた たちと、(P2) で送られてきた 個の4つ組を用いて検証者V側で を計算し、照らし合わせて一致していることを確認します。
一致していれば検証者はこれを受け入れ、そうでなければ拒否します。
このプロトコルには、コミットメント方式が以下のように取り入れられています。
完全秘匿かつ計算量拘束なコミットメント方式
(P0)：準備フェーズ
(V0)：コミットフェーズ
(V1)：公開フェーズ
計算量秘匿かつ完全拘束なコミットメント方式
(P1)：コミットフェーズ
(P2)：公開フェーズ
ゼロ知識証明であることの確認
ゼロ知識証明が備えている3つの性質を確認してみます。
- 完全性
証明者Pがグラフ の3彩色を知っていれば、確率1でプロトコルを遂行することができます。
- 健全性
証明者Pがステップ (P1) で3彩色の入れ替えを送る前に、検証者Vは (V0) で選択する辺たちを送っていますが、完全秘匿性をもつコミットメントの形で送っています。そのため、証明者Pは送られてきたこれらの辺をみて (P1) で送る彩色のコミットメントをうまく調節することはできません。さらに、 (P1) で完全拘束性をもつコミットメントを利用しているために、その後の (P2) では (P1) で送信した彩色を変更することができないようになっています。
証明者Pが共通のグラフを入力に持っていなかった場合、少なくとも1つ誤った辺の彩色が存在すると考えられます。この証明者Pが (V0) でコミットされる に対して、(P2)で正しくコミットメントの公開フェーズを行える確率は高々
となります。
- ゼロ知識性
- シミュレータの予備ステップ (M0)
- 検証者Vの予備ステップ (V0)
- シミュレータMのステップ (M1)
- 検証者Vのステップ (V1)
- シミュレータMのステップ (M1’)
- 検証者Vのステップ (V1’)
- シミュレータMのステップ (M2)
ここでは正しくコミットメント方式に従う検証者Vについてのみゼロ知識性を説明します。検証者Vがプロトコルに従わない場合は、以下の説明を修正することによって示されますが、本記事では割愛します。
シミュレーションの流れ
シミュレータMは、検証者Vに最初のメッセージ を送信します。
実際のプロトコルと同様に生成し、 検証者Vは をシミュレータMに送信します。
シミュレータMは、 個のダミー、例えば 個すべてを のコミットとして作成した を作成します。つまり、一様乱数 を生成し、 と に対して とします。そして、これら を検証者Vに送信します。
検証者Vは をシミュレータMに送信します。
シミュレータは を記録し、ステップ (V0) 終了直後までシミュレーションの巻き戻しを行います。
ここで、(M1) に対応するステップを再び行いますが、今度は記録した に対応するコミットだけつじつまが合うようにしてコミットを作成します。すなわち、 について が互いに異なる色となるようなランダムなコミットとし、残りの のコミット についてはダミー、例えば のコミットとして を作成します。そして、これらを検証者Vに送信します。
検証者Vは をシミュレータMに送信します。
検証者がプロトコルに従うことを仮定していることによって、ここまでは実際のプロトコルのやりとりとしてありえる値が作成できているので、 を作成し、これまでにやりとりした値すべて、すなわち , , , , を出力します。
このシミュレーションによってシミュレータから出力された系列は、実際に検証者Vが証明者Pとやりとりした場合に得られるやりとりの系列と見分けがつきません。また、このシミュレーションは平均的には多項式回のステップで終了します。したがってこのプロトコルはゼロ知識性をもつといえます。
検証者Vが必ずしもプロトコルに従わないとすると、 として (V0) で送るのに利用した と、(V1) で送る と、 (V1’) で送る のそれぞれが異なる場合が考えられます。ここでは詳細は省略しますが、そのような状況が起きても平均多項式回のステップで終了するようなシミュレーションを構成することができます。
プロトコルのトリック
このプロトコルでは、ステップ (V0) において、証明者Pがステップ (P1) で3彩色の入れ替えを送る前に、検証者Vが選択する辺たちを送っています。ただし、選択する辺は証明者Pにバレてはいけないので、完全秘匿性をもつコミットメントスキームを利用しています。一見すると無駄なように見えるこのステップですが、これがシミュレーション戦略において巻き戻し回数を減らすトリックとなっています。
実際のプロトコルにおいて、ステップ (V1) で送られてくる辺はステップ (V0) で送られたものと同じでなければ正しいプロトコルのやりとりとしてはありえません。すなわち、ステップ (P1) の段階では次のステップ (V1) で送られてくる辺が決定しています。したがって、シミュレーション戦略内では、(V1)に対応するステップで送られる辺を確認して、 (P1) に対応するステップに巻き戻すことで、(V1) で送られてくる辺にあたるコミットメントを、後で不都合が起きないようにつじつまを合わせて作ることができます（ステップ (M1’) ）。直列プロトコルの場合には、検証者Vから送られてくる辺は証明者Pがコミットを送る前には決まらないため、検証者が確認する辺と偶然つじつまが合うコミットを証明者Pに対応するシミュレータMが行うまで何度も巻き戻しが必要でした。しかし本プロトコルでは、このトリックのおかげで（検証者Vが正しくプロトコルに従う場合は）一度の巻き戻しでシミュレーションを行うことができます。
まとめ
- ゼロ知識証明を愚直に並列化したものがゼロ知識証明となっているかは示されていない
- 計算量秘匿かつ完全拘束なコミットメントと、完全秘匿かつ計算量拘束なコミットメントを利用することで、定数ラウンドで証明が完了するゼロ知識証明プロトコルを構成することができる
- プロトコルの主要なアイデアは、彩色のコミットメントより先に検証者がチェックに利用する辺を送ってしまうことであり、シミュレーション内ではシミュレータが辺を記録して巻き戻すことで、つじつまの合う彩色を選んでコミットメントできるようになる
参考文献
[1] Goldreich O. Foundations of Cryptography: Basic Tools. 1st ed. Cambridge University Press; 2001.