ゼロ知識証明と計算量クラス
はじめに
本記事では、ゼロ知識証明について計算量クラスの観点から紹介します。
証明系で扱う主張の定式化
証明系で行いたいことは、証明者の「ある命題が真である」という主張を検証者に納得してもらうことです。この主張は決定問題によって定式化されます。
あらゆる事象は符号化を施すことである長さの0と1からなるビット列で表現できます。ビット列全体 の部分集合を と書き、これを言語とよびます。 を考えると自然に、ある が に属するかどうかを議論できるようになります。ある が に属するかどうかを決定（判定）する問題のことを決定問題といいます。
この決定問題に対してある関数（アルゴリズム） を、 ならば 、 ならば となるように定めれば、この によって言語を として特徴づけることができます。そのため以下では言語のことも問題とみなし、同じように扱うことにします。
決定問題の考え方を用いて「ある命題が真である」ということを「ある決定問題の答えがYesである」つまり、ある と言語 を用いて「 は に属する」「 」として定式化することにします。
例えば「 が素数である」という主張であれば、 は素数 を用いて「 」と定式化します。
クラスNP
まずは非対話の最も単純な証明系、証明者が検証者に一方的に何かを送りつけると証明が完了するものを考えてみましょう。ここで、証明者の計算能力は必ずしも制限がないが、検証者の計算能力は多項式時間に制限されているとします。証明系が「よい」性質をもつとすれば、以下の2つの性質を備えるとするのが自然と考えられます。
- 完全性： ならば証明者は検証者を納得させることができる
- 健全性： ならばいかなる証明者も検証者を納得させることができない
また、検証者自身で証明者が示したいことを証明者からの情報なしに検証できてしまっては証明系の意味がないので、そのようなことのない、証明系として意味のあるクラスに属する言語を利用したいです。
これらの条件を満たすのがクラス に属する言語です。クラス の定義をフォーマルに書き下すと以下のようになります。
- 定義（クラス ）
言語 がクラス に属しているとは、ある多項式時間アルゴリズム が存在して、 の時かつその時に限り、ある であって をみたすものが存在することである。
なお、このような のことを の証拠（witness）といいます。
クラス の定義を言い換えると、クラス とは「証拠 が与えられれば かどうかを多項式時間で判定することができるクラス」であるといえます。つまり であることを示すために、証明者が証拠 を計算して（または、証明者の計算能力も多項式時間に制限されていれば、何らかの方法で証拠を手に入れて）検証者に送れば、検証者は かどうかを多項式時間で検証することができ、非対話の証明系となっています。定義では が検証者に対応しており、 が と出力することが検証者が正しいと納得することに対応します。
また、 であれば によって検証者は納得できます（完全性）が、 である場合はいかなる「証拠」 を送っても となるので検証者を納得させることができません（健全性）。したがって、クラス から導かれる証明系は「よい」性質を備えていることも確認できます。
例を挙げてみます。クラス に属する問題の例としては充足可能性問題、ナップサック問題、グラフ同型問題などが知られていますが、ここではグラフ同型問題を例にとって説明します。グラフ同型問題は「グラフ が同型か（頂点同士のつながり方は同じか）？」を決定（判定）する問題です。
証明者は2つのグラフ が同型であることを検証者に納得させたいとします。このとき、2つのグラフ の同型写像 （それぞれのグラフの頂点同士を、辺によるつながり方が同じになっているように対応させる写像）を用意して検証者Vに送れば、検証者は を使うことによって が確かに同型であることを検証することができます。この検証は多項式時間で行うことができ、実際に が同型であれば必ず検証は成功します。一方で、 が同型でない場合には、検証に成功することはありません。
グラフとグラフ同型についての補足：グラフとは、下の図に示すような頂点（点に対応します）と辺（頂点を結ぶ線に対応します）の集合からなる構造体のことです。2つのグラフが同じ数だけ頂点を持ち、かつ頂点が辺によって同じつながり方をしているときにグラフは同型であるといいます。例えば、下の図に示している2つのグラフは同型です。なぜなら、右側のグラフの下側2頂点cとdを持って左右の場所を入れ替えれば、左側のグラフに一致するからです。この対応関係を与える写像 は によって定まり、これがこの2つのグラフ間の同型写像です。
対話証明系
上で説明したような を利用した送りつけるタイプの証明に対して、証明者と検証者間の対話を許容し、さらに検証者の確率的挙動も許容したものを考えます。このような証明系が対話証明であり、対話証明をもつ計算量クラスが です。フォーマルに書き下すと以下のように定義されます。
- 定義（対話証明）
- 完全性：任意の に対して
- 健全性：任意の と任意の に対して
（計算量に制限のない）アルゴリズム と確率的多項式時間アルゴリズム のペア が言語 に対する対話証明であるとは、以下の2性質を持つもののことである。
ここで はnegligibleな関数（無視できる関数）とよばれるもので、任意の多項式 に対してある が存在し、任意の に対して が成り立つ関数です。
- 定義（クラス ）
対話証明をもつ言語が属する計算量クラスをクラス という。
クラス はクラス の条件を緩和したものであるため、明らかに がわかります。
また 、つまりクラス は決定性チューリング機械で多項式領域を使って解ける問題のクラスであることが知られています[3]。
証明系に対して対話化を行ったものも であることが知られているため、対話化の恩恵を受けるには検証者の確率化が必要となります。
対話証明を考えるモチベーション
証明系は非対話で決定論的に実行可能な非常に効率的な証明系となっているように見えます。しかし一方で、このことが融通の効かない事態を引き起こしているという事実も存在しています。対話を可能とし、さらに確率性を導入するという条件の緩和を行うモチベーションを以下にいくつか紹介します。
- 必ずしも利用したい命題が 問題であるとは限らない
例えば、 問題は 問題に含まれるかどうかは現在わかっていません。 問題とは 問題の補問題のことで、 問題のYesとNoを反転させたような問題のことです（ に限らず、ある計算量クラスに対して接頭辞に を付加したものは補問題を考える計算量クラスです）。 問題の例として、先ほど紹介したグラフ同型問題の補問題であるグラフ非同型問題を利用した証明系を考えてみます。グラフ非同型問題は「グラフ と は非同型か？」を決定する問題です。この証明系では、グラフ と はグラフ同型でないことを検証者に納得させることが目的になりますが、証拠として写像を1つ送ることで証明を行うことはおそらく不可能です。そこで、対話や確率性を導入することによってクラスとして扱える言語が増えるため、グラフ非同型問題を利用した証明ができるようになるかもしれません（し、実際証明ができるようになります）。
- しばしば証拠のサイズがコストとなる
利用する 問題によっては証拠のサイズが大きいものとなることがあります。その場合、計算時間や通信量が増大してしまいますが、証明者と検証者の間の対話を可能にすることで、通信量や計算時間を減らすことができる場合があります。この考え方はPCP定理やSNARGといった、計算量を減らして検証を行う概念に関連します。
- ゼロ知識性を付加できる
対話化と確率化によってゼロ知識性を付加することができます。後のセクションで詳しく説明します。
クラスAM
クラス はゼロ知識証明とともに考案された概念ですが、同時期に類似の概念としてクラス が考案されました。ゼロ知識証明周辺の計算量クラスの包含関係の多くはクラス を利用して示されています。
- 定義（クラス ）
対話証明であって、検証者から証明者へのメッセージが検証者によって生成された乱数であるようなものをArthur–Merlinプロトコルという。Arthur–Merlinプロトコルをもつ言語が属する計算量クラスをクラス という。
Arthur–MerlinプロトコルはArthurとMerlinが対話を行うプロトコルですが、対話証明の用語と対応づければArthurが検証者でMerlinが証明者となります。
整数 に対して と書くとき、はじめの通信を検証者から証明者への通信とする、ラウンド数（通信回数）が 回のArthur–Merlinプロトコルをもつ計算量クラスとします（この場合に限らずラウンド数が 回のプロトコルを持つクラスの場合に をつけることにします）。クラス 自体は 、すなわち検証者が乱数を証明者に送り、証明者が検証者にメッセージを送って、検証者が検証を行うプロトコルを持つ計算量クラスとして定義されます。しかしながら に対して であることが知られています。
と の違いは、 では検証者が乱数自体を証明者に送るが、 では検証者が使用した乱数に基づいて決まるメッセージを証明者に送るという点にあります。このように のプロトコルは証明者にも乱数が見えることからパブリックコインプロトコル、対照的に のプロトコルはプライベートコインプロトコルとよばれることがあります。
明らかに ですが、驚くべきことに であることが知られています。この事実は、検証者は乱数を隠そうが公開しようが検証能力はほとんど変わらないということを示しています[3]。
クラス に対して、はじめの通信が証明者スタートのプロトコルをもつ計算量クラスをクラス といいます。 証明系に対して確率化のみを行ったものはクラス となることが知られています。
ゼロ知識対話証明
ゼロ知識証明（ゼロ知識対話証明）は、対話証明にゼロ知識性を付加した証明です。定式化の方法を紹介したのち、ここまでに紹介した計算量クラスとの関係性を説明します。
シミュレーションと識別不可能性
ゼロ知識証明では、検証者は証明者からその主張が正しいということ以外の情報を得ることなく証明が行われます。この「検証者が情報を得ていない」ということはシミュレーションによって定式化できます。
プロトコルで行われるやりとりは、実際には、証明者からの影響が含まれるはずです。しかし、プロトコルのやりとりと見分けがつかないようなやりとりを、証明者だけが知り得る情報（秘密情報）を利用せず検証者が知り得る情報（公開情報）だけで再現（シミュレーション）できるのであれば、証明者の主張が正しいということ以外の情報を得ていないといえそうです。
「見分けがつかない」という言葉は、見分ける対象を確率変数と考え、その2つの確率変数に対して識別不可能性として定式化することができます。見分ける能力の強さに応じて3つの定義が存在します。
- 定義（識別不可能性）
- 完全識別不可能性
- 統計的識別不可能性
- 計算量的識別不可能性
確率変数 と に対して完全 / 統計的 / 計算量的識別不可能性は以下のように定義される：
任意の に対して と の従う分布が同一である。
任意の に対して が成り立つ。
任意の確率的多項式時間アルゴリズム と任意の に対して が成り立つ。
これらを直感的に述べると、完全識別不可能性は2つの見分ける対象が完全に同じ、統計的識別不可能性は2つの見分ける対象がほとんど同じ（多項式回観測しても見分けがつかない）、計算量識別不可能性は多項式時間では2つの見分ける対象の違いがわからない、となります。
したがって「検証者が実際に見ている世界と識別不可能な情報をシミュレート」するのがゼロ知識性であるといえます。
以下では確率変数 と とか識別不可能であることを と書くことにします。ただし、識別不可能性の程度（完全 / 統計的 / 計算量的）によって「 」の意味を取り替えることにします。
ゼロ知識証明
前のセクションで述べた言葉を使ってゼロ知識性を定義します。ある入力 に対して、検証者Vが観測した実際のプロトコルのやりとりを と書き、シミュレーションで得たやりとりを と書くことにします。このとき、ゼロ知識性はフォーマルには以下のように表現できます。
- 定義（ゼロ知識性）
（計算量に制限のない）アルゴリズム と多項式時間アルゴリズム のペア が言語 に対してゼロ知識性をもつとは、任意の に対してあるシミュレータ が存在して、任意の に対して が成り立つことである。
この「 」の意味が完全 / 統計的 / 計算量的識別不可能性であるかによって完全 / 統計的 / 計算量的ゼロ知識性が定まります。
これによりゼロ知識証明が定義できます。ゼロ知識証明は対話証明にゼロ知識性を付加したものですが、フォーマルに書き下すと以下のようになります。
- 定義（ゼロ知識証明）
- 完全性：任意の に対して
- 健全性：任意の と任意の に対して
- ゼロ知識性：任意の に対してあるシミュレータ が存在して、任意の に対して
（計算量に制限のない）アルゴリズム と多項式時間アルゴリズム のペア が言語 に対するゼロ知識証明であるとは、以下の3性質を持つもののことである。
先ほどと同様に「 」の意味が完全 / 統計的 / 計算量的識別不可能性であるかによって完全 / 統計的 / 計算量的ゼロ知識証明が定まります。
ゼロ知識証明をもつ計算量クラスは、ゼロ知識性の強さそれぞれに対して定まります。
- 定義（クラス / / ）
計算量的 / 統計的 / 完全ゼロ知識証明をもつ言語が属する計算量クラスをそれぞれクラス / / という。
ゼロ知識性に仮定する能力の程度から明らかに です。
一方向性関数の存在を仮定すれば が成り立つことが知られています。したがって であることとあわせれば すなわち、 問題を利用すれば計算量的ゼロ知識証明を作れることがわかります。または、 完全問題を利用すれば具体的に計算量的ゼロ知識証明が構成できることがわかるので、任意の 問題が 完全問題に多項式時間で書き換えられる（多項式還元）ことを利用すれば であることを示すことができます。
一方で、 問題を利用することでは統計的ゼロ知識証明や完全ゼロ知識証明を作ることはできそうもないということが知られています。定義から ですが、一方で であると信じられています。また一方で である（特に である）ことが示されています。したがって だったとすれば、これは であるということになりますが、これは多項式階層（ であると信じられているというようなことをより一般の計算量クラスに対して考えたもの）が崩壊してしまうことが導けるため だと考えられています。
また、 であることが知られています[2]。
ゼロ知識アーギュメント
ゼロ知識証明の場合には 問題の利用によって統計的ゼロ知識証明を作ることはできませんでした。しかし、証明者の計算能力に制限を与えることで、統計的ゼロ知識性をもった証明を作ることができます。証明において証明者の計算能力を多項式時間に制限したものをアーギュメントといいます。
ゼロ知識証明において証明者の計算能力を多項式時間に制限することでゼロ知識アーギュメントというものが得られます。
- 定義（ゼロ知識アーギュメント）
- 完全性：任意の に対して
- 健全性：任意の と任意の確率的多項式時間機械 に対して
- ゼロ知識性：任意の に対してあるシミュレータ が存在して、任意の に対して
多項式時間アルゴリズムのペア が言語 に対するゼロ知識アーギュメントであるとは、以下の3性質を持つもののことである。
先ほどと同様に「 」の意味が完全 / 統計的 / 計算量的識別不可能性であるかによって完全 / 統計的 / 計算量的ゼロ知識アーギュメントが定まります。
このとき、クラス , , がゼロ知識証明と同様に定義できます。
- 定義（クラス / / ）
計算量的 / 統計的 / 完全ゼロ知識アーギュメントをもつ言語が属する計算量クラスをそれぞれクラス / / という。
ゼロ知識アーギュメントはゼロ知識証明を包含します。すなわち , , が成り立ちます。 このことは、ゼロ知識アーギュメントがゼロ知識証明の健全性を弱めたものであるということに注目すると理解できます。ゼロ知識アーギュメントの健全性における の計算量は多項式時間に制限されていますが、ゼロ知識証明では制限がありません。したがって、 に対して が を騙せる確率 の最大値はゼロ知識アーギュメントの方がゼロ知識証明よりも小さくなる（もしくは同じ）はずです。よって、ゼロ知識証明の健全性が成り立つならば、ゼロ知識アーギュメントの健全性が成り立ちます。一方で、ゼロ知識アーギュメントの健全性が成り立つ場合には、多項式時間より大きい計算量をもつ であれば となってしまう可能性があり、必ずしもゼロ知識証明の健全性が成り立つとは限りません。
ゼロ知識証明では となり統計的ゼロ知識性を得ることはできませんでしたが、（一方向性関数の存在を仮定のもとで）証明者の計算能力を制限したアーギュメントの場合には 、すなわち任意の 問題を用いて統計的ゼロ知識性をもつアーギュメントを作れることが知られています[2]。
最後にここまで述べた計算量クラスの包含関係をまとめたものを示します。 は を意味しています。なお、 は決定問題のうち、多項式時間で決定ができる言語が属するクラスです。
まとめ
- 証明をするときに使う「ある命題が真である」という主張は決定問題で表現される
- の考え方を緩和することで が得られ、証明を行うにあたって表現力が向上する
- だが だと考えらている
- だが証明者の計算能力を制限すれば となる
参考文献
[1] O. Goldreich. The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press, 2001.
[2] G. Couteau. Zero-knowledge proofs for secure computation. Theses, Université Paris sciences et lettres, November 2017.
[3] S. Arora and B. Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2006.
[4] F. Tramèr. Cs 355 - topics in cryptography lecture 3: Interactive proofs, April 2019. https://crypto.stanford.edu/cs355/19sp/lec3.pdf
[5] 岡本龍明. 暗号理論における安全性概念 (中央大学数学教室講究録 2), April 2008.