3色塗り分け問題を利用したゼロ知識証明プロトコルの紹介

Table of Contents

はじめに

本記事では、Practical Relativistic Zero-Knowledge for NP[1] の解説を行います。
この記事で紹介されるプロトコルの、モチベーションと実験による実現は相対論的ゼロ知識証明の実験による実現[3]に記載されているので、先に一読していただけると理解が進むと思います。

まず、既存研究の問題点とこのプロトコルのモチベーション、記号の定義を解説し、最後にプロトコルについて記述します。

既存研究の問題点

NP困難を活かしたゼロ知識証明のプロトコルはあるものの、現実では実装されていない。

その一例として、Relativistic (or 2-prover 1-round) zero-knowledge　protocol for NP secure against quantum　adversaries.(Andr´e Chailloux, Anthony Leverrier) [2]で提案されている、ハミルトン閉路の存在判定を用いるゼロ知識証明のプロトコルがある。
このプロトコルでは、頂点が500個のグラフにハミルトン閉路が存在するか検証するのに、長さが数100ビットのビットコミットメントを250,000回行う必要がある。
数100ビットという通信量の多さから、このプロトコルの実現には、検証者同士で、100km以上距離を離す必要があり、現実では実装されなかった。

モチベーション

この論文では、3色塗り分け問題を用いたゼロ知識証明のプロトコルを提案する。
このプロトコルでは、辺とビットを通信するだけなので、一回あたりの通信量が削減でき、
検証者同士の距離を大幅に短くすることが可能になる。

記号の定義

頂点 $V$ と辺 $E$ から成る有限無向グラフを $G=(V, E)$ と定義する。
また、 $j>i$ に対して、辺 $e\in E$ を $(i,j)$ と定義する。
更に、各辺 $e,e' \in E$ に対して、 $e$ と $e'$ が一つの頂点 $i\in V$ を共有することを、 $e\cap e' =i \in V$ と定義する。
また、等号関係について、 $(a,b)\# (c,d)$ は、 $a\neq c$ と $b\neq d$ が共に成り立つことと定義する。
$(a,b)\neq (c,d)$ は、 $a\neq c$ または $b\neq d$ が成り立つことと定義する。
最後に、検証者が、 $P_1$ に送信するものが $(e,r,s)$ になり、 $P_2$ に送信するものが $(e',r',s')$ になる、確率分布を $\mathcal{D'_g}＝\{(p'(e,r,s,e',r',s'),((e,r,s),(e',r',s'))\}_{e,e'\in E,r,s,r',s'\in \mathbb{F_3}}$ と定義する。
以下のプロトコルの設計上、確率が以下の不等式を満たすように設定する。
$p'(e,r,s,e',r,t)\geq \frac{1-\epsilon}{16|E|}(\frac{|\{e'\}\cap Edges(i)|}{|Edges(i)|}+\frac{|\{e'\}\cap Edges(j)|}{|Edges(j)|})$
$p'(e,r,s,e,-r,-s)\geq \frac{\epsilon}{4|E|}$
なお、 $Edges(i)$ は頂点 $i$ で繋がっている辺のことで
$Edges(i):=\{(j,i)\in E\}_{j < i} \cup \{(j,i)\in E\}_{j > i}$

プロトコル

検証者 $V$ の目的は、有限体 $\mathbb{F_3}=\{0,1,2\}$ に属し、かつ証明者 $P_1$ , $P_2$ が共有している $c_1,c_2,...c_l \in \mathbb{F_3}$ がある性質を満たすかどうか検証して、証明者が3色塗り分けの解を知っているかどうか検証することである。
まず、証明者 $P_1$ , $P_2$ は、任意の頂点 $i \in V$ に対して $b _i \in \mathbb{F_3}$ と $G:\{(i,c_i)| c_i \in \mathbb{F_3}\}_{i \in V}$ をマスキングする。
コミットフェーズでは、
$r,s,t,r',s',t' \in \mathbb{F^*_3}$ で、検証者 $V$ は $(((i,j),r,s),((i',j'),r',s'))\in _\mathcal{D'_g}(E \times \mathbb{(F^*_3)^2})^2$ を選ぶ。
次に、検証者 $V$ は $((i,j),r,s)$ を $P_1$ へ、 $((i',j'),r',s')$ を $P_2$ へ送信する。
証明者 $P_1$ は、 $(i,j)\in E$ ならば、 $w_i=b_i・r+c_i$ と $w_j=b_j・s+c_j$ を送信する。
同様に、証明者 $P_2$ も、 $(i',j')\in E$ ならば、 $w'_{i'}=b_{i'}・r'+c_{i'}$ と $w'_{j'}=b_{j'}・s'+c_{j'}$ を送信する。
チェックフェーズは $i,j,i',j'$ の値によって、4通りに分岐する。
$(i,j)=(i',j')$ と $(r',s') \#(r,s)$ が共に成り立つならば、検証者 $V$ は $w_i+w_i' \neq w_j+w_j'$ が成り立つかどうかの真偽を受け取る。
$(i,j)=(i',j')$ と $(r',s') = (r,s)$ が共に成り立つならば、検証者 $V$ は $(w_i=w_i')\land(w_j=w_j')$ が成り立つかどうかの真偽を受け取る。
$(i,j)\cap(i',j')=i$ と $r'=r$ が共に成り立つならば、検証者 $V$ は $w_i=w_i'$ が成り立つかどうかの真偽を受け取る。
$(i,j)\cap(i',j')=j$ と $s'=s$ が共に成り立つならば、検証者 $V$ は $w_j=w_j'$ が成り立つかどうかの真偽を受け取る。

まとめ

本記事では、3色塗り分け問題を利用したゼロ知識証明のプロトコルを紹介しました。
元論文であるPractical Relativistic Zero-Knowledge for NPでは、完全性、健全性、ゼロ知識性を確率的に定義し、このプロトコルでそれらの性質が成立することを証明しているので、興味のある方は是非ご一読下さい。