Skip to content

対話型ゼロ知識証明

対話型証明システムのうちゼロ知識性を持つものを対話型ゼロ知識証明システム（interactive zero-knowledge proof system）と呼びます。

ゼロ知識証明

ゼロ知識証明とは、証明者があるステートメントが真であることを、検証者に対して真であるという情報以外を何も明かすことなく納得させることができるプロトコルです。形式的には、証明者がステートメント \(\phi\) が言語 \(\mathcal{L}\) の元であること（ \(\phi \in \mathcal{L}\) ）を検証者に納得させることが目的です。

ここで言語 \(\mathcal{L}\) に求められる性質は、 \(\phi\in \mathcal{L}\) かどうかの判定を行うには、「なにかしらの情報」を持っていないと困難であることです。言語 \(\mathcal{L}\) の例として論理式充足可能性問題 \(\mathrm{SAT}\) を考えてみます。 \(\mathrm{SAT}\) は言語です。 \(\phi\) をある論理式として、 \(\phi \in \mathrm{SAT}\) かどうかを判定することは、 \(\mathrm{SAT}\) がNP完全であることから一般的な \(\phi\) に対しては困難ですが、解の一つを与えれば \(\phi \in \mathrm{SAT}\) となることを効率良く判定できます。この解が「なにかしらの情報」であり、ウィットネスと呼びます。ゼロ知識証明では、このウィットネスの情報を一切検証者に明かさずに、 \(\phi \in \mathcal{L}\) を納得させることができます。

ゼロ知識性

言語 \(\mathcal{L}\) の対話型証明システム \((P,V)\) において、入力 \(x \in \mathcal{L}\) に対して証明者 \(P\) と対話した後に効率的に計算できるもの全てが、証明者 \(P\) と対話せず入力 \(x\) からも効率的に計算できるならば、その対話型証明システム \((P,V)\) はゼロ知識性を持つといいます。あるいは、証明者 \(P\) がゼロ知識性を持つといいます。

ゼロ知識性には、知識の漏れなさの度合いが高い順に、パーフェクトゼロ知識性・統計的ゼロ知識性・計算量的ゼロ知識性の3つの定義があります。

パーフェクトゼロ知識性

パーフェクトゼロ知識性の定義を紹介します。

パーフェクトゼロ知識性

任意の確率的多項式時間対話型マシン \(V^*\) に対して、任意の \(x\in \mathcal L\) に対して、以下の式が成り立つような、ある確率的多項式時間アルゴリズム \(M\) が存在するならば、 \((P,V)\) はパーフェクトゼロ知識性を持つという。

\[ \langle P,V^* \rangle (x) \equiv M(x) \]

\(\langle P,V^* \rangle (x)\) は、共通の入力 \(x\) で対話型マシン \(P\) と対話した後の対話型マシン \(V^*\) の出力で、 \(M(x)\) は入力 \(x\) に対するマシン \(M\) の出力です。これはシミュレーションパラダイムに従っており、 \(M\) をシミュレーターと呼びます。

ゼロ知識性の計算複雑性クラス

パーフェクトゼロ知識証明システムを持つ言語のクラスを \(\mathrm{PZK}\) と表記します。同様に、統計的ゼロ知識証明システム、計算量的ゼロ知識証明システムに対しても、それぞれ \(\mathrm{SZK},\mathrm{CZK}\) と表記します。定義から次の式が成り立ちます。

\[ \mathrm{BPP} \subseteq \mathrm{PZK} \subseteq \mathrm{SZK} \subseteq \mathrm{CZK} \subseteq \mathrm{IP} \]

一方向性関数の存在を仮定すると、 \(\mathrm{CZK}=\mathrm{IP}\) となります。他にもいくつかの広く信じられている計算理論の仮定から、次の式が成り立つと考えられています。

\[ \mathrm{BPP} \subset \mathrm{PZK} \subseteq \mathrm{SZK} \subset \mathrm{CZK} = \mathrm{IP} \]

この包含関係から以下のことがわかります。

  • \(\mathrm{NP} \subseteq \mathrm{IP}\) であることから \(\mathrm{NP}\) の全ての言語は計算量的ゼロ知識性を持つ対話型証明システムを構築できる。
  • 対話型証明システムを持つ言語のうち統計的ゼロ知識性を持つ対話型証明システムを構築できないものがある。
  • \(\mathrm{PZK}\) と \(\mathrm{SZK}\) が等しいのかはまだ不明である（未解決問題）。
  • \(\mathrm{BPP}\) の全ての言語はパーフェクトゼロ知識性を持つ対話型証明システムを構築できる。

正直検証者ゼロ知識性

正直検証者ゼロ知識性（honest verifier zero-knowledge）とは、任意の検証者を考えるのではなく、ある特定の検証者に対してのみ考えるゼロ知識性です。

正直検証者ゼロ知識性自体は実用的には意味がありませんが、正直検証者ゼロ知識性を持つパブリックコイン型のプロトコルは、通常のゼロ知識性を持つプロトコルに変換できることが多くあり有用です。