本記事では、ゼロ知識証明に関係する基本的ないくつかのトピックを簡単にまとめて紹介します。
イントロダクション
通常の証明は、証明された主張が真であること以上の情報を与えます。例えば、検証者は、その証明の過程を見たことにより、同じ主張に対しては真となる証明を作成する能力を得ます。一方でゼロ知識証明は、証明された主張が真であるという情報だけを与えます。したがって、ゼロ知識証明の検証者は、何度この主張を見たところで、この主張に対する証明を作成することはできません。
このゼロ知識性は、対話化と確率化の導入によって実現されました[4]。
- 対話化 証明者と検証者との対話型プロトコルとする。
- 確率化 証明者と検証者がともに乱数を振ることができ、検証は確率的に行われる。確率化による誤りを許容する。
実用的なプロトコルとするためには、対話回数を極力減らし、また検証の誤り確率を減らし、さらには計算量が少なくて済むことが望ましいです。より効率的なゼロ知識証明プロトコルの構成を目指し、現在でも多くのプロトコルが研究、考案されています。
ゼロ知識証明の健全性とゼロ知識性
ゼロ知識証明において、証明者と検証者の安全性を大きく決定づけているのは健全性とゼロ知識性といえます[4,5]。
健全性
健全性（soundness）とは、証明者の主張が偽である場合に、検証者はそのことを高い確率で見抜く性質です。この性質は証明者による敵対的な振る舞いから検証者を保護する安全性要件といえます。
プロトコルに従うかどうかを厭わない任意の証明者に対して、その計算能力によって大きく3つに分けることができます。
- 計算量的健全性（computational soundness） 計算能力に制限のある証明者を仮定する。
- 統計的健全性（statistical soundness） 無制限の計算能力をもつ証明者を仮定する。
- 完全健全性（絶対健全性：perfect soundness） 無制限の計算能力をもつ証明者を仮定し、その証明者の主張が偽である場合に、検証者は確率1で偽であると見抜く。
なお、完全健全性は統計的健全性の要件を強めたものと考えられるため、完全健全性を統計的健全性の一部とみなし、計算量的健全性と統計的健全性の2つに分ける場合も多いです。
この健全性要件により、ゼロ知識証明は以下の2つに分類できます。
- （狭義の）ゼロ知識証明（ZKP：Zero Knowledge Proof） 無制限の計算能力をもつ証明者に対して健全性を備えることが可能なゼロ知識証明です。つまり、統計的健全性（もしくは完全健全性）を持ちます。
- ゼロ知識アーギュメント（ZKA：Zero Knowledge Argument） 計算能力に制限のある証明者に対して健全性を備えることが可能なゼロ知識証明です。つまり、計算量的健全性を持ちます。
なお、多くの実用的なゼロ知識証明プロトコルは知識のゼロ知識証明であり、健全性は知識健全性（knowledge soundness）とよばれる、上記の健全性よりも強い要件に置き換わります。
知識のゼロ知識証明の場合、証明者と検証者に対する共通の情報に加えて、証明者には補助的な情報（証拠：witness）が与えられます。この証拠は、検証者が証明を受け入れた場合に、証明者とやりとりすることによって高い確率で知識を抽出できる効率的なアルゴリズム（知識抽出器：knowledge extractor）によって抽出することができるもので、その情報を知っているという「証拠」にあたるといえます。知識健全性は、検証者が証明を受け入れた場合に、知識抽出器が存在するという性質です。
ゼロ知識性
ゼロ知識性（zero knowledge）とは、証明者の主張が真であるならば検証者は「主張が真である」こと以外に何の情報も得られない、という性質でした。この性質は検証者による敵対的な振る舞いから証明者を保護する安全性要件といえます。
ゼロ知識性は、プロトコルで検証者が観測するやり取りと、検証者自身でプロトコルのやりとりを模擬したものとを比較したとき、どれくらい見分けがつかないかによって定義されます（識別不可能性による定式化）。このとき、識別不可能性の程度によって大きく3つの段階に分けることができます。
- 計算量的ゼロ知識性（computational zero knowledge） 実際のプロトコルのやりとりと、多項式時間の計算能力をもつ検証者によるやりとりのシミュレーションを多項式回行う。このとき、各回それぞれについて比較しても差がみられない。
- 統計的ゼロ知識性（statistical zero knowledge） 実際のプロトコルのやりとりと、無制限の計算能力をもつ検証者によるやりとりのシミュレーションを多項式回行う。このとき、各回それぞれについて比較しても差がみられない。
- 完全ゼロ知識性（perfect zero knowledge） 実際のプロトコルのやりとりと、無制限の計算能力をもつ検証者によるやりとりのシミュレーションのそれぞれを確率分布として見たときに、それらが分布として等しい。
📎 数学的な定式化
ゼロ知識証明の数学的な定義をここでは簡単に紹介します[1][3]。ゼロ知識証明は、ゼロ知識性をもつ対話証明であるため、まずは対話証明について考えます。
対話証明では、対話を行う証明者と検証者をそれぞれ $P$ と $V$ というチューリング機械（かなり単純化して言えば、入力に対して計算を行い、対応した出力をするもの）によりモデル化します。より具体的には、$P$ は計算量制限のない確率的チューリング機械、 $V$ は計算時間が多項式時間に制限された確率的チューリング機械です。このとき、対話証明は以下のように定義されます。
定義（対話証明）
対話チューリングマシンの組 $(P,V)$ が言語 $L\subset\{0,1\}^*$ に対する（暗号学的な）対話証明であるとは、以下の2性質を持つもののことである。
- 完全性：任意の $x\in L$ に対して $\mathrm{Pr}((P,V)(x)=1)\geq1-\epsilon(|x|)$
- 健全性：任意の $x\notin L$ と任意の $P^*$ に対して $\mathrm{Pr}((P^*,V)(x)=1)\leq \epsilon(|x|)$
ここで $\{0,1\}^*=\bigcup_{k\in\mathbb{N}}\{0,1\}^k$（有限長のビット列の集合）であり、言語 $L$ とは $\{0,1\}$ からなるアルファベットの列の集合です。 $\epsilon(k)$ は暗号学においてnegligibleな関数とよばれるもので、直感的には任意の多項式の逆数よりも漸近的に小さな関数を意味します。数学的には $\forall c>0,\exists K,\forall k\geq K,\epsilon(k)<k^{-c}$ で定義されます。また $(P,V)(x)=1$ は $(P,V)$ に対して $x$ を入力した場合に受理することを表現しています。
次に、ゼロ知識性を定義するために必要となる識別不可能性を定義します。識別不可能性は、2つの確率分布が見分けられないという性質を定式化したものであり、見分けるために利用する能力によって、3つの定義が存在します。
識別不可能性
以下では確率変数族 $\mathcal{X}=\{X_k\}$ と $\mathcal{Y}=\{Y_k\}$ を考える。
- 定義（完全識別不可能性） $\mathcal{X}$ と $\mathcal{Y}$ が完全識別不可能であるとは、任意の $k$ に対して以下が成立することである： $$ X_k=Y_k $$
- 定義（統計的識別不可能性） $\mathcal{X}$ と $\mathcal{Y}$ が統計的識別不可能であるとは、以下が成立することである： $$ \sum_{\alpha\in\{0,1\}^*}\left|\mathrm{Pr}(X_k=\alpha)-\mathrm{Pr}(Y_k=\alpha)\right|<\epsilon(k) $$
- 定義（計算量識別不可能） $\mathcal{X}$ と $\mathcal{Y}$ が計算量識別不可能であるとは、任意の確率的多項式時間アルゴリズム $D$ に対して以下が成立することである： $$ \left|\mathrm{Pr}(D(X_k)=1)-\mathrm{Pr}(D(Y_k)=1)\right|<\epsilon(k) $$
識別不可能性の概念を用いて、ゼロ知識性を定義します。
ゼロ知識性
$(P,V)$ が（完全/統計的/計算量的）ゼロ知識性をもつとは、任意の $x\in L$ と $y\in\{0,1\}^{|x|^c}$ と任意の検証者 $V^*$ に対して、確率的多項式時間チューリング機械 $M_{V^*}$ が存在し、 $\mathrm{View}_{(P,V^*)}(x,y)$ と $M_{V^*}(x,y)$ が $k=|x|$ に関して（完全/統計的/計算量的）識別不可能であることをいう。 ここで
- $\mathrm{View}_{(P,V)}(x,y)$ ： $P$ と $V$ との対話において $V$ が知ることのできる全ての系列からなる確率変数の族。つまり、共通入力 $x\in L$ 、 $V$ の使った乱数、 $P$ からの対話、その他外部入力 $y\in\{0,1\}^{|x|^c}$（ $c$ はある定数） 。
- $M_{V^*}(x,y)$ ：対話証明における $P$ と $V$ の対話を模擬する確率的多項式時間チューリング機械（シミュレータ）。
ゼロ知識性をみたす $(P,V)$ のことをゼロ知識証明といいます。
ゼロ知識証明と計算量クラス
ゼロ知識証明の構成に利用する問題の計算量クラス
ゼロ知識証明の構成に利用する問題として、クラスBPP（確率的多項式時間である程度の成功確率で解ける問題の集合）に属する問題を利用した場合、検証者によってゼロ知識証明プロトコルを利用することなく証明者の知識を求めることができてしまいます。そのため、意味のあるゼロ知識証明を構成する際には、BPPより難しい（と考えられている）計算量クラスの問題を利用します。
統計的健全性を持つ統計的ゼロ知識証明は、代表的にはグラフ同型問題や平方剰余問題を利用することで構成できることが知られていますが、NP完全問題を利用しての構成はできないことが知られています[6]。なお、統計的ゼロ知識証明のすべての問題は、統計的差異（Statistical Difference）という問題に還元できることも知られています[7]。
一方で、健全性またはゼロ知識性のいずれかが計算量的なゼロ知識証明では、一方向性関数の存在を仮定すると、NP問題（実際には対話証明で証明できるどのような問題でも可能ですが）を利用したプロトコルを構成することができます[8,9]。
証明者と検証者の計算能力
プロトコルに従う証明者は、検証者と比較して計算量的な優位性を持っているべきです。そうでなければ、検証者は自身でプロトコルのシミュレーションを行うことで主張の証明を作成できてしまいます。
そこで典型的には、証明者には計算量的な制限を設けない、もしくは、計算能力は多項式時間に制限されているがNP問題の解を持っている、等の設定を置くことが多いです。暗号等への応用を考えた場合は、後者の設定が一般的になされます[4]。
なお、対話証明では一般的に検証者の能力は多項式時間に制限されます。
コミットメント
コミットメント（commitment）とは、ゼロ知識証明を構成するときによく利用される暗号プリミティブの1つで、秘匿性と拘束性の2つの性質を備える2フェーズの対話型プロトコルです。秘匿性と拘束性にも強さの段階（完全・統計的・計算量的）がありますが、秘匿性または拘束性のどちらかが計算量的なものしか構成できないことが知られています。コミットメントの秘匿性がゼロ知識性に、拘束性が健全性に関係します。
代表的なコミットメントの例としては、完全秘匿性と計算量的拘束性を実現できるPedersenコミットメント、完全拘束性と計算量的秘匿性を実現できるElGamalコミットメント等が存在します。
近年のプロトコルでは効率化のために、コミットメントを多項式やベクトルとして行うスキーム等が利用されています。
詳細は「【技術】コミットメント方式とは？」の記事をご覧ください。
シグマプロトコル
シグマプロトコル（Σ-protocol）は、コミット・チャレンジ・レスポンスの3ラウンドのやりとりからなる、知識の証明を行う対話型プロトコルです。完全性と健全性、さらにプロトコルに従う（乱数をきちんと生成する）検証者のみに成立する条件付きゼロ知識性を持ちます。
この条件付きゼロ知識性は、いくつかのステップを踏むことによってゼロ知識性に変形できることも知られており、ゼロ知識証明を構成する際に利用されることがあります。
シグマプロトコルの特徴は、やりとりの回数が規定されていること、ORやANDで結ばれた複合文の証明が容易にできること等が挙げられます。この複合文の証明を応用することにより、ゼロ知識範囲証明を構成することができます。
詳細は「【技術】シグマプロトコルとは」の記事をご覧ください。
ラウンド数の削減
証明の確率化に伴って生じた健全性の誤差を無視できるレベルで小さなものまで減らしたいです。考えられる解決策の1つは、愚直に何度もプロトコルを繰り返し、すべての繰り返しで証明を受け入れることができた場合に限って、証明を受け入れるようにすることです。しかしこの方法を利用すると、同じプロトコルを何度も繰り返すことになるため、その分通信コストや計算時間は増えてしまいます。
そこで、並列化することによりやり取りの回数を減らすことを考えます。しかし、愚直に並列化するとゼロ知識性が保たれないことが知られています。この困難を解決するためにコミットメントが利用されます。以下に様々な言語の仮定のもとで、どのようなラウンド数（やりとりの回数）での証明系が知られているかを、いくつか列挙します。
- グラフ同型問題や平方剰余問題では5ラウンドの完全ゼロ知識証明をもつ[10]
- NP問題を利用した場合、5ラウンドの計算量的ゼロ知識証明系をもつ[11]
- NP問題を利用した場合、（一方向性関数の存在の仮定のもとで）4ラウンドのゼロ知識アーギュメント証明系をもつ[11]
多証明者ゼロ知識証明
お互いに対話することのできない複数の証明者の存在を仮定するゼロ知識証明プロトコルも考案されています。この設定のもとでは、NP問題を利用した場合、2ラウンドの完全ゼロ知識対話証明系をもつことが知られています[12]。
非対話型ゼロ知識証明
究極的には、やり取りなしでゼロ知識証明ができると便利です。しかしながら、標準モデルの下では非対話型ゼロ知識証明を構成できないことが知られています。これを実現するために置く仮定としては
- 信頼できる第三者による事前設定を行う
- ランダムオラクルを仮定する
の大きく2つの方法があります。これらの仮定のもとで、対話型ゼロ知識証明を変換することにより非対話型ゼロ知識証明を得ることができます。実用的に利用されているプロトコルのほとんどは非対話型ゼロ知識証明です。
前者の方式は、後者の方式と比較して（現在では、多くの場合で）計算時間やコストの面で優位性があります。一方、後者の方式は、前者の方式と比較して耐量子性をもつという面で優位性を持ちます[13]。
第三者による事前設定
共通参照情報（Common Reference String）とよばれる、信頼できる第三者のセットアップにより生成された乱数列を利用します。
この設定のもとでは、近年ではzkSNARK（zero-knowledge Succinct Non-interactive ARgument of Knowledge）と呼ばれる手法が多数考案されています。zkSNARKは、どのような主張に対しても一定サイズの証明を生成する特徴（Succinct）を持っています。この手法には、多くの場合で算術回路の充足可能性問題が利用され、ペアリング暗号に基づく方式が採用されています[14,15]。
ランダムオラクルの仮定
ランダムオラクル（Random Oracle）とよばれる、真にランダムな関数の存在を仮定します。実装にはハッシュ関数を利用します。この仮定をおく場合には、第三者による事前設定をおいたものと同じ問題クラスを利用してプロトコルを構成できますが、第三者による事前設定は不要となります。
この設定のもとで、非対話型ゼロ知識証明は、多くの場合、シグマプロトコルを用いて構成した対話型ゼロ知識証明に対して、Fiat-Shamir変換に基づいた手法を施すことで構成されるます。近年の代表的な手法としてはBulletproof[16]やzkSTARK[17]等が知られています。
応用
応用の観点では、ゼロ知識証明は大きく3種類に分けることができます[2]。
- 知識の証明：ある情報を知っている。
- 範囲の証明：ある情報が一定の範囲内である。
- 演算の証明：ある計算の演算結果が正しいものである。
以下では、この観点で分類をした場合の応用例を列挙します[2,5,18]。
知識の証明
- 秘密鍵の知識 暗号文が同じ平文に複号されることを、秘密鍵を明らかにすることなく示すことができます。
- ユーザー認証 IDやパスワードを知っていることを、そのIDやパスワード自身を明らかにすることなく、ユーザーがID利用者本人であることを示すことができます。
範囲の証明
- 電子投票 最も単純には、投票者は0または1の暗号文を投票します。ここで0を不支持、1を支持に対応させます。すべての投票者についてこれを行ったのち、暗号文のままで和をとるなどして、最後に復号することで投票結果を得ます。 しかし、悪意のある投票者が0と1以外の数を投票し、正確な値がわからなくなってしまう可能性があります。そこで、投票者が0または1の暗号文を投票したことを、もとの平文が0と1のどちらに対応するか明らかにしないままで証明するゼロ知識証明を利用することが考えられます。
- ミックスネット ある通信において、送信者が受信者に直接メッセージを送る代わりに、仲介者としてミックスサーバと呼ばれるものを使うことを考えます。このミックスサーバは、$n$ 個の暗号化された入力$(c_1,\ldots,c_n)$ を得て $n$ 個の複号された結果 $(m_1,\ldots,m_n)$ を出力する能力を持ちます。ただし、どの $c_i$ が $m_j$ に対応するかは不明であるようにシャッフルされます。 しかし、本当に入力と出力とが並べ替えの関係となっているかは不明です。そこで、ミックスサーバの出力が、入力の復号の並べ替えとなっていることを、具体的な並べ替えや暗号化に使用した鍵などを明かすことなく示すゼロ知識証明を利用することが考えられます。
- 年齢の認証 想定されるユースケースとして、18歳以上であることを年齢を明かすことなく示すゼロ知識証明が考えられます。
演算の証明
- Verifiable Computation クライアントがある計算を、より計算能力が高いワーカーに委託して計算してもらう状況を考えます。このとき、クライアントはワーカーが正しい計算をして、正しい結果を返してくれているかを確認したいです。 そこで、ワーカーはクライアントを納得させるために非対話証明を作成します。 なお、このユースケースでは、クライアントの計算能力は小さいと考えられるため、証明サイズが小さく、証明の検証にかかるコストが小さい方が望ましいです。
- Proof-Carrying Data ある1つの計算を各パーティに分散させて計算させている状況を考えます。このとき、各パーティが計算の前のステップがすべて正しく実行されたことを確かめたいとします。 このとき、各パーティが自分のステップの計算を正しく実行したこと、さらには、自分の計算の前までのステップのすべてが正しいという証明を見たこと、の2つの事実を、計算結果を明らかにすることなく示すゼロ知識証明を作成し、分散計算で送るものに付加してやりとりを行います。 なお理論的には、知識健全性により、知識抽出器を利用することで原理的には計算の履歴を復元することが可能です。
ゼロ知識証明における代表的な略称
以下に代表的に用いられている略称を列挙します。
- ZKP（zero knowledge proof：ゼロ知識証明）
- ZKA（zero knowledge argument：ゼロ知識アーギュメント）
- ZKIP（zero knowledge interactive proof：対話型ゼロ知識証明）
- NIZK（non-interactive zero knowledge：非対話型ゼロ知識証明）
- CZK（computational zero knowledge：計算量的ゼロ知識）
- SZK（statistical zero knowledge：統計的ゼロ知識）
- PZK（perfect zero knowledge：完全ゼロ知識）
- ZKAoK（zero knowledge argument of knowledge：知識のゼロ知識アーギュメント）
- ZKPoK（zero knowledge proof of knowledge：知識のゼロ知識証明）
- zkSNARK（zero knowledge succinct non-interactive argument of knowledge）
- ZKRP（zero knowledge range proof：ゼロ知識範囲証明）
参考文献
[1] 岡本龍明著. 現代暗号の誕生と発展 : ポスト量子暗号・仮想通貨・新しい暗号. 近代科学社, 2019.
[2] 有限責任監査法人トーマツ. ゼロ知識証明入門. 翔泳社, 2021.
[3] O. Goldreich. Foundations of Cryptography: Basic Tools. Cambridge University Press, USA, 2000.
[4] S. Vadhan. The complexity of zero knowledge. In V. Arvind and S. Prasad, editors, FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, pp. 52–70, Berlin, Heidelberg, 2007. Springer Berlin Heidelberg.
[5] J. Bootle, A. Cerulli, P. Chaidos, and J. Groth. Efficient Zero-Knowledge Proof Systems, pp. 1–31. Springer International Publishing, Cham, 2016.
[6] L. Fortnow. The complexity of perfect zero-knowledge. Proceedings of the nineteenth annual ACM symposium on Theory of computing, 1987.
[7] A. Sahai and S. Vadhan. A complete problem for statistical zero knowledge. J. ACM, Vol. 50, No. 2, p. 196–249, mar 2003.
[8] O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity or all languages in np have zero-knowledge proof systems. J. ACM, Vol. 38, No. 3, p. 690–728, jul 1991.
[9] G. Brassard, D. Chaum, and C. Cr ́epeau. Minimum disclosure proofs of knowledge. J. Comput. Syst. Sci., Vol. 37, pp. 156–189, 1988.
[10] M. Bellare, S. Micali, and R. Ostrovsky. Perfect zero-knowledge in constant rounds. In Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, STOC ’90, p. 482–493, New York, NY, USA, 1990. Association for Computing Machinery.
[11] U. Feige and A. Shamir. Zero knowledge proofs of knowledge in two rounds. In G. Brassard, editor, Advances in Cryptology — CRYPTO’ 89 Proceedings, pp. 526–544, New York, NY, 1990. Springer New York.
[12] M. Ben-Or, S. Goldwasser, J. Kilian, and A. Wigderson. Multi-prover interactive proofs: How to remove intractability assumptions. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, STOC ’88, p. 113–131, New York, NY, USA, 1988. Association for Computing Machinery.
[13] A. Nitulescu. zk-snarks: A gentle introduction. 2020.
[14] B. Parno, J. Howell, C. Gentry, and M. Raykova. Pinocchio: Nearly practical verifiable computation. Commun. ACM, Vol. 59, No. 2, p. 103–112, jan 2016.
[15] J. Groth. On the size of pairing-based non-interactive arguments. In M. Fischlin and J.-S. Coron, editors, Advances in Cryptology – EUROCRYPT 2016, pp. 305–326, Berlin, Heidelberg, 2016. Springer Berlin Heidelberg.
[16] B. Bu ̈nz, J. Bootle, D. Boneh, A. Poelstra, P. Wuille, and G. Maxwell. Bulletproofs: Short proofs for confidential transactions and more. 2018 IEEE Symposium on Security and Privacy (SP), pp. 315–334, 2018.
[17] E. Ben-Sasson, I. Bentov, Y. Horesh, and M. Riabzev. Scalable, transparent, and post-quantum secure computational integrity. IACR Cryptol. ePrint Arch., Vol. 2018, p. 46, 2018.
[18] E. Morais, T. Koens, C. van Wijk, and A. Koren. A survey on zero knowledge range proofs and applications. SN Applied Sciences, Vol. 1, No. 8, p. 946, Jul 2019.
