証明システム

証明システム（proof system）とは、証明者と検証者という2つのパーティーが居て、証明者が証明の生成を行い、検証者がその証明の検証を行うプロトコルのことです。

証明システムでは検証者は証明者を信頼しません。もし証明者を信頼してよいなら、そもそも証明など必要無く証明者が言っていることをそのまま信じれば良いからです。

一方で、証明者が検証者を信頼するかどうかは、その証明システムの目的によって変わります。証明者にとってゼロ知識性が必要な証明システムにおいては検証者を信頼しません。証明者の秘密情報が検証者に漏れることが危惧されるからです。ただし、ゼロ知識性を考える場合においても、先述した正直検証者ゼロ知識性のように、検証者を信頼することがあります。

証明システムでは、証明の生成よりも証明の検証のほうが簡単である状況、すなわち、複雑性が小さい状況を考えます。検証者よりも証明者に負担がかかるということです。

この証明者の作業と検証者の作業の複雑性の非対称性は、計算複雑性クラス \(\mathrm{NP}\) と関連付けることができます。クラス \(\mathrm{NP}\) に属する言語 \(\mathcal{L}\) において、 \(x\in \mathcal{L}\) かどうかを判定する時間は多項式時間ですが、その判定をするために必要な情報を生成する時間は多項式時間とは限りません。多項式時間で計算可能な関係 \(R_{\mathcal{L}}\) を用いて、この言語 \(\mathcal{L}\) を、

\[ \mathcal{L} \coloneqq \lbrace x : \exists y,\ (x,y) \in R_{\mathcal{L}} \land |y| \le \operatorname{poly}(|x|) \rbrace \]

と定義できますが、この \(y\) を生成することを証明の生成、 \((x,y) \in R_{\mathcal{L}}\) を判定することを証明の検証と考えることができます。実際、クラス \(\mathrm{NP}\) の全ての言語に対して証明システムを構築できます。

証明システムが持つべき性質は、完全性と健全性の2つです。どちらの性質も前で説明しましたが、改めて説明すると、完全性とは証明者が提示するステートメントが真である場合に検証者は真であることがわかる性質で、健全性とは証明者が提示するステートメントが偽である場合に検証者は偽であることがわかる性質です。