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に対して、ee'が一つの頂点i\in Vを共有することを、e\cap e' =i \in Vと定義する。
また、等号関係について、(a,b)\# (c,d)は、a\neq cb\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_iw_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)が共に成り立つならば、検証者Vw_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')=ir'=rが共に成り立つならば、検証者Vw_i=w_i'が成り立つかどうかの真偽を受け取る。
(i,j)\cap(i',j')=js'=sが共に成り立つならば、検証者Vw_j=w_j'が成り立つかどうかの真偽を受け取る。

まとめ

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

参考文献

[1] Practical Relativistic Zero-Knowledge for NP
https://drops.dagstuhl.de/opus/volltexte/2020/12109/pdf/LIPIcs-ITC-2020-4.pdf

[2] ハミルトン閉路の存在判定を用いるゼロ知識証明のプロトコルを提案した論文
Relativistic (or 2-prover 1-round) zero-knowledge protocol for NP secure against quantum adversaries.(André Chailloux, Anthony Leverrier)

[3] 相対論的ゼロ知識証明の実験による実現 https://tech.hashport.io/2989/

タイトルとURLをコピーしました