はじめに
本記事では、コミットメント方式の応用例として、NP完全問題のひとつである3彩色問題に関するゼロ知識対話証明について紹介します。同時に、コミットメントの種類を変えることによって構成できる完全ゼロ知識アーギュメントについても紹介します。
ゼロ知識証明とは何かについては以下の記事をご覧ください。
準備：グラフ
以下の長方形内部の区切られた領域を、隣り合う領域が異なる色となるように、3色だけで塗り分けることはできるでしょうか？
ここで、もう少し単純化するために、すべての領域を点で表現し、隣り合っている領域同士を線で結んでみます。
すると、いま考えている領域の塗り分け問題を、点の集合と、その点同士を結ぶ線だけからなる図式、すなわちグラフで捉えることができるようになりました。
なお、今回用意した領域たちは以下のように3色で塗り分けることができます。
グラフ理論においては、その点たちを頂点（vertex）といい、線を辺（edge）といいます。また、頂点の集合を $V$ 、辺の集合を $E$ （ $E$ は $V$ の2元部分集合族となります）で表し、そのペア $G=(V,E)$ をグラフ（graph）と定義します。
3彩色問題
ここでは、NP完全問題のひとつとして、3彩色問題を取り上げます。
NP完全問題とは、NP問題（多項式時間で正しい解を求めることは難しいが、解を提示されればその検証は多項式時間で可能であるような問題）であり、かつ他の任意のNP問題を多項式時間で書き換えると、その問題に変換できるようなもののことです。言い換えれば、NP問題のうちで最も難しい問題といえます。
現在では、NP完全問題を多項式時間で解けるアルゴリズムは存在しないと考えられているので、その解をゼロ知識証明の知識として用いることで、プロトコルの安全性を担保できます。
3彩色問題とは「与えられたグラフについて、辺で結ばれたどの2つの頂点も異なる色となるように、すべての頂点を3色で塗り分けることができるか？」というものです。
📎なお、一般に $k$ 彩色問題、すなわち「与えられたグラフについて、辺で結ばれたどの2つの頂点も異なる色となるように、すべての頂点を $k$ 色で塗り分けられるか？」という問題は、 $k$ が3以上であればNP完全問題であることが知られています。
3彩色問題に対するゼロ知識証明
ここでは、証明者が3彩色問題の答えを知っているという知識のゼロ知識証明について説明します。
3彩色問題に限らず、NP完全問題に対するゼロ知識証明を構成する際には、コミットメントが必要となります。コミットメントについては以下の記事をご覧ください。
【技術】コミットメント方式とは？ – プライバシーテック研究所
ゼロ知識証明は、無制限の計算能力をもつ証明者に対して健全性が成り立つような手法です。この健全性要件を満たすために、以下では計算量的秘匿かつ完全拘束なコミットメントを利用することになります。詳しくは後述します。
以下では、乱数 $s$ を用いた計算量的秘匿かつ完全拘束なコミットメントの暗号化関数を $C_s$ と表記することにします。
問題設定
証明者Pはグラフ $G$ の3彩色 $\psi:V\to\{1,2,3\}$ を知っていることを、 $\psi$ を検証者Vに明かすことなく示したいとします。
$\psi$ は各頂点を、塗る色に対応する数字ラベル $\{1,2,3\}$ のいずれかに対応させる写像、つまり3色塗り分けの情報です。
共有情報
証明者Pと検証者Vは多重辺やループのない3彩色可能グラフ $G=(V,E)$ の情報を共有しているとします。
ただし $n=|V|$、$V=\{1,\ldots,n\}$ です。
プロトコルの流れ
証明者Pと検証者Vは以下のようなやりとりを行います。
- 証明者Pのステップ (P1)
証明者Pはランダムに $\{1,2,3\}$ の置換 $\pi$ と独立に乱数 $s_1,\ldots,s_n\in\{0,1\}^n$ を選択します。
すべての頂点 $v\in V$ に対して $\varphi(v)=\pi(\psi(v))$ と定め、乱数 $s_v$ に対して $c_v = C_{s_v}(\varphi(v))$ 計算します。
証明者Pは検証者Vに $c_1,\ldots,c_n$ を送ります。
📎 $\varphi$ は3色塗り分けの色をランダムに入れ替えを意味する写像です。
- 検証者Vのステップ (V1)
検証者Vはランダムに $(u,v)\in E$ を選択し、証明者Pに送ります。
- 証明者Pのステップ (P2)
証明者Pは検証者から $(u,v)$ を受け取ると、 $(s_u,\varphi(u))$ と $(s_v,\varphi(v))$ を検証者Vに送ります。
- 検証者Vのステップ (V2)
検証者Vは受け取った $(s_u,\varphi(u))$ と $(s_v,\varphi(v))$ について、 $\varphi(u)$ と $\varphi(v)$ が $\{1,2,3\}$ 上の値をとっていること、さらに $u$ と $v$ の色を $\varphi$ によって入れ替えても異なる色となっているはずなので、 $\varphi(u)\neq\varphi(v)$ となっていることも確認します。
問題がなければ、 $C_{s_u}(\varphi(u))$ と $C_{s_v}(\varphi(v))$ を計算し、(P1)で送られていた $c_u$ と $c_v$ とこれらを比較して一致していることを確認します。
すべての条件にクリアすれば、検証者Vは証明者Pの主張を受け入れ、そうでなければ拒否します。
上記のステップを十分な回数繰り返せば、これはゼロ知識証明となります。
ゼロ知識証明であることの確認
ゼロ知識証明が備えている3つの性質を順に確認してみます。
- 完全性
証明者Pがグラフ $G$ の3彩色を知っていれば、確率1でプロトコルを遂行することができます。
- 健全性
証明者Pが実際にはグラフ $G$ の3彩色を知らない場合、証明者Pの持つグラフには少なくとも1つ適切でない辺があるので、 $1/|E|$ の確率で検証者Vは拒否することになります。すなわち、このプロトコルを十分な回数 $k|E|$ 回だけ繰り返せば、証明者の主張が偽であるときに偽であると見抜ける確率は $$ 1-\left(1-\frac{1}{|E|}\right)^{k|E|}\approx1-e^{-k} $$ となり、十分高い確率で偽であることを見抜けることになります。
- ゼロ知識性
検証者Vがプロトコルの各繰り返しで見ることになる頂点の組の色は、置換 $\pi$ の効果により、毎回ランダムな異なる2色でしかありません。よって、検証者Vは証明者Pの主張以外の情報は一切得ていません。
ただし、このプロトコルの場合、ゼロ知識性は検証者Vが制限された計算能力をもつ場合に対してのみ成立します。その理由は以下で述べます。
コミットメントについて
コミットメントを利用することで、上で示したプロトコルの健全性とゼロ知識性が保証されます。
- コミットメントの秘匿性（hiding）
秘匿性により、証明者Pが (P1) で送った頂点たちが何であったのかは検証者Vには分かりません。これがゼロ知識性を保証しています。
- コミットメントの拘束性（binding）
拘束性により、証明者Pは (P1) と (P2) で異なる頂点の組を暗号化して送ると、そのことが検証者Vにバレてしまい、証明者Pの主張は拒否されます。ゆえに、証明者Pは (P1) と (P2) では同じ頂点の組を送らねばなりません。しかし、グラフ $G$ の3彩色を知らない証明者Pが用意した彩色の仕方で、プロトコルの各繰り返しで送る頂点の組の彩色が異なる確率は非常に低いです。これが健全性を保証しています。
ここでは、計算量的秘匿かつ完全拘束なコミットメントを利用していました。実は、用いるコミットメント方式が、健全性とゼロ知識性の強さを決定しているといえます。もう少し詳しく述べると以下のようになります。
- コミットメントの計算量的秘匿性（computationally hiding）
計算量的秘匿性により、検証者Vが制限された計算能力をもつ場合、証明者Pが (P1) で送った頂点たちが何であったのか見分けることはできません。一方で、検証者Vが無制限の計算能力をもつ場合には、コミットメントとして送られてきた値から逆算して、暗号化前の値を求めることができてしまいます。そのため、検証者は見た頂点とその色との対応関係という情報を得ることになってしまいます。
したがって、ゼロ知識性は制限された計算能力をもつ検証者Vに対して成立します（計算量的ゼロ知識性）。
- コミットメントの完全拘束性（perfectly binding）
完全拘束性により、グラフ $G$ の3彩色を知らない証明者Pは、無制限の計算能力があろうと、(P1) と (P2) で異なる頂点を暗号化しても同じ値となるものを発見することは難しいです。
したがって、健全性は無制限の計算能力をもつ証明者Pに対して成立します（完全健全性）。
ここで、上で示したプロトコルで用いた計算量的秘匿かつ完全拘束なコミットメントを、完全秘匿かつ計算量的拘束なコミットメントに取り替えてみます。すると、プロトコルの性質は以下のように変化します。
- コミットメントの完全秘匿性（perfectly hiding）
完全秘匿性により、 証明者Pが (P1) で送った頂点たちが何であったのかは無制限の計算能力をもつ検証者Vであっても分かりません。
したがって、ゼロ知識性は無制限の計算能力をもつ検証者Vに対して成立します（完全ゼロ知識性）。
- コミットメントの計算量的拘束性（computationally binding）
計算量的拘束性により、グラフ $G$ の3彩色を知らない証明者Pが制限された計算能力をもつ場合、(P1) と (P2) で異なる頂点を暗号化しても同じ値となるものを発見することは難しいです。一方で、グラフ $G$ の3彩色を知らない証明者Pが無制限の計算能力をもつ場合には、 (P1) と (P2) で異なる頂点の組であっても同じ暗号の値となるものを容易に発見できるので、それらの値を使うことで本来は偽である主張が受け入れられてしまう場合があります。
したがって、健全性は制限された計算能力をもつ証明者Pに対して成立します（計算量的健全性）。
NP完全問題に対するゼロ知識証明において、ゼロ知識性は制限された計算能力をもつ検証者に対してのみ成り立つことが知られています。しかし、コミットメントを取り替えることで、健全性は弱まってしまいますが、ゼロ知識性を無制限の計算能力をもつ検証者に対しても成立するようにできることがわかります。
ゼロ知識証明は、ゼロ知識性をもつ対話証明でした。対話証明は完全健全性を持ちます。すなわち、無制限の計算能力をもつ証明者に対して健全性が成り立つようなスキームです。一方で、健全性が制限された計算能力をもつ証明者に対してのみ成り立つ場合の対話証明を、通常の対話証明と言い分けてアーギュメントと言うことがあります。つまり、アーギュメントは計算量的健全性を持ちます。上でみたように、完全秘匿かつ計算量拘束なコミットメントを利用した場合には、ゼロ知識性をもつアーギュメントとなっていることがわかります。このようなゼロ知識証明をゼロ知識アーギュメント（zero-knowledge argument）といいます。少しややこしいので簡単にまとめると
- ゼロ知識証明＝対話証明（完全性＋完全健全性）＋ゼロ知識性
- ゼロ知識アーギュメント＝アーギュメント（完全性＋計算量的健全性）＋ゼロ知識性
となります。特に、今回の場合ゼロ知識性が無制限の計算能力をもつ証明者に対しても成立する（完全ゼロ知識性）ので、完全ゼロ知識アーギュメント（perfect zero-knowledge argument）ともいいます。
ゼロ知識証明と完全ゼロ知識アーギュメントの使い分け
このように、コミットメントの種類によって得られるゼロ知識証明と完全ゼロ知識アーギュメントの間には、健全性とゼロ知識性の間にトレードオフがあることがわかります。
どちらのコミットメントを利用したプロトコルにするかは、どちらの性質を優先的にしたいかに依存します。
- ゼロ知識証明の方が望ましいと考えられる場合
利用者の計算資源が非常に大きい場合など、完全な意味でその利用者が不正を行えないことが望まれれば、完全健全性をもつゼロ知識証明を利用する方が望ましいと考えられます。
- 完全ゼロ知識アーギュメントの方が望ましいと考えられる場合
健全性はそのプロトコルが実行されている間のみ要求されるものですが、ゼロ知識性はプロトコルの実行後にも必要となる可能性があります。そのような場合には、完全ゼロ知識性をもつ完全ゼロ知識アーギュメントを利用する方が望ましいと考えられます。
まとめ
- NP完全問題に対するゼロ知識証明の構成には計算量的秘匿かつ完全拘束なコミットメントを用いる
- 代わりに完全秘匿かつ計算量的拘束なコミットメントを用いることで完全ゼロ知識アーギュメントが得られる
- ゼロ知識証明と完全ゼロ知識アーギュメントは健全性とゼロ知識性との間でトレードオフがある
参考文献
[1] Goldreich O. Foundations of Cryptography: Basic Tools. 1st ed. Cambridge University Press; 2001.
[2] 岡本龍明. 現代暗号の誕生と発展: ポスト量子暗号・仮想通貨・新しい暗号. 近代科学社; 2019.
