Universal Arguments：性質の検証 | HashPort技術ブログ

Table of Contents

はじめに

本稿では以前の記事[2]に続いて[1]で提案されたuniversal argumentsと呼ばれる証明システムについて解説します。具体的に構成されたプロトコルが本当にuniversal argumentsの性質を満たしていることを確認します。
本稿で用いられている記号や定義については適宜[2]を参照して下さい。

定義の確認と示すべきこと

Universal argumentsとは

効率の良い検証(Efficient Verification)
相対的に効率の良い証明者による完全性(Completeness via a relatively-efficient prover)
計算量的健全性(Computational soundness)
弱い知識証明の性質(A weak proof-of-knowledge property)

の四つの性質を満たす証明システムでした。このうち効率の良い検証、相対的に効率の良い証明者による完全性についてはプロトコルの定義から成り立つことが簡単に分かります。弱い知識証明の性質を仮定すると、検証者が受け入れる確率が十分に高い証明であれば弱い知識証明の性質によって存在が保証されたオラクルマシンが出力するオラクルによって証明が正しい確率も高くなるので、計算量的健全性も成り立ちます。よってuniversal argumentsの性質を示すためには弱い知識証明の性質を示せば良い事が分かります。

弱い知識証明の性質(A weak proof-of-knowledge property)の証明

弱い知識証明の性質(A weak proof-of-knowledge property)とは以下のような性質でした。

確率的多項式時間のオラクルマシン $E$ であって $V^\pi$ が $y=(M, x, t)$ を受け入れる確率が（ $y$ の長さに対して）十分大きいならば $(x, w)\in R$ と $Pr[E^\pi (x, i)=w_i]>2/3$ を満たす $w = w_1,\cdots w_t$ が存在する。

この定義にあるオラクルマシン $E$ の動作を定義します。

記号と用語の定義

以下では証明者のアルゴリズムを表す回路族を $\{ \tilde{P_n} \}_n$ 、証明を $y$ 、その長さを $n=|y|$ として $Pr[(\tilde{P_n}, V)(y)=1]>\epsilon := 1/p(n)$ とします（ $p$ は多項式）。さらにuniversal argumentsの構成で存在を仮定したハッシュ関数の族を $\{ h_{\alpha} \}$ とします。またPCPシステムのエラー率を入力長 $n$ に対して $\epsilon (n) =2^{-n}$ とします。
また以下のように用語を定義します。

i番目のクエリーとは $q_i = Q_{PCP}(y, r, i)$ 。
i番目の返答とは証明者 $\tilde{P_n}$ が送った $q_i$ に対応するラベル $l'_{q_i}$ 。
i番目の返答の対応する認証とは $\gamma_{i,j}$ を $q_i$ のjビットの接頭辞とした時の $(l'_{\gamma_{i,j}0}, l'_{\gamma_{i,j}1})$ の $j=0,\cdots d-1$ についての列。
i番目の返答が「妥当」とは、その対応する認証が検証者の検証(V3)を通過すること。
返答 $\sigma$ が $(i, q)$ に対して $\delta$ -strongとは、i番目のクエリーが $q$ であった時の証明者 $\tilde{P_n}$ の返答が $\sigma$ である確率が $\delta$ 以上であること。
qが $\delta$ -矛盾の返答を持つとはが $(i, q)$ に対して $\delta$ -strongで $1$ が $(j, q)$ に対して $\delta$ -strongとなるような $i,j(i=j$ でも良い)が存在すること。

オラクルマシンの構成

(V1)で送ったハッシュ関数のためのランダム値が $\alpha$ のときに検証者がメッセージ $y$ を受け入れる条件付き確率を $p_{y, \alpha}$ と表し、 $m$ を $n = |y|$ の多項式で抑えられる、PCPシステムのクエリーの数とします。
これらを用いて弱い知識証明の性質(A weak proof-of-knowledge property)の条件を満たすオラクルマシン $E$ の動作を定義します。
そのためにまずuniversal argumentsの証明システムの性質をいくつか示します。

返答はほとんどstrongであること

ここでは検証者が $\delta$ -strongな返答だけを受け取って証明を受け入れる確率が $p_{y, \alpha}-2m\delta$ であることを示します。 $\delta$ -strongな返答であって検証者が受け入れる証明が最大でどのくらいあるかを考えます。検証者が受け入れる証明は全て「妥当」です。その返答を $i$ 番目のクエリー $q_i$ に対する $\sigma \in \{0, 1\}$ であると固定すると場合を考えると、「妥当」であって $\delta$ -strongな返答ではない確率はその定義から $\delta$ 以下です。 $q_i$ を動かしてもこの確率は変わらず、 $i \in [1,m], \sigma \in \{0, 1\}$ の全ての組み合わせについて和を取った $2m\delta$ が最大の確率です。したがって検証者が $\delta$ -strongな返答だけを受け取って証明を受け入れる確率は $p_{y, \alpha}-2m\delta$ となります。

返答の矛盾は珍しいこと

ここでは $\delta$ -矛盾の返答を持つようなクエリーは十分に少ないことを示します。 $\eta_\alpha$ を $\delta$ -矛盾の返答を持つようなクエリーを検証者が作る確率であるとします。 $\delta$ -矛盾の返答からハッシュ関数 $h_{\alpha}$ の衝突を見つける確率多項式時間のオラクルマシンを構成し、このオラクルマシンの成功確率が $\eta_\alpha /m$ の多項式で下から抑えられることを示すことでハッシュ関数の衝突確率が十分に低いという仮定から $\eta_\alpha$ も十分小さいことを示します。
オラクルマシンの動作を次のように定義します。

乱数 $r$ と一つの $i \in [1,m]$ を選び $q_i = Q(y, r, i)$ とします。
$i', i''$ をランダムに選びreverse-samplingアルゴリズム $S_{pcp}$ を $(y, i', q_i), (y, i'', q_i)$ に用いてそれぞれから乱数 $r', r''$ を得ます。
証明者のアルゴリズム $\tilde{P_n}$ に乱数をそれぞれ $\alpha,r'$ と $\alpha,r''$ として2組の証明者と検証者のやり取りを行います。
2のreverse-samplingアルゴリズムによって乱数を決めたことから2組のやり取りの検証者のクエリーはそれぞれi', i''番目がq_iになっており、そのクエリーに対する、2組のやり取りの返答がどちらも「妥当」で異なっていれば、以下の二点からハッシュ関数h_{\alpha}の衝突が根から葉に至るハッシュ木の構成の中で生じていることが分かり、ハッシュ木の衝突を見つけることができます。
- 証明者が(P1)で送った証明木の根と深さの組は2組のやりとりで同じであること
- 証明木の葉であるクエリー $q_i$ に対する返答は2組のやり取りで異なっていること

1で選んだ $q_i$ が $\delta$ -矛盾である確率は $\eta_\alpha /m$ であり、その場合には4で2組のやり取りの返答がどちらも「妥当」で異なっている確率は $\sigma /m$ なので、合わせてこのオラクルマシンの成功確率は $\eta_\alpha \sigma ^2/m^3$ となります。
以上で $\delta$ -矛盾の返答を持つようなクエリーが十分に少ないことを示すことができました。

PCPのオラクルを得る手順

ここでは最終的なオラクルマシンを構成するためにPCPシステムで検証者 $V_{PCP}$ が用いるオラクル $\pi$ を得る手順を定めます。
$\delta= p_{y, \alpha}/2m$ として $\delta$ -strongで $\delta/2$ -矛盾ではない返答を「良い返答」と呼びます。実際には「良い返答」ではない、つまり $\delta$ -strongな返答を持たないクエリーや $\delta/2$ -矛盾な返答を持つクエリーも存在し得ますが、上で示した事実からこれらの存在はとても珍しいです。
PCPシステムのオラクルを得る手順は以下の通りです。 $T$ を $n/\epsilon$ の多項式で表される数とします。
入力： $(y, \alpha)$ と $q$ (証明者のアルゴリズム $\tilde{P_n}$ へのアクセスが可能)
出力：PCPのオラクル $\pi$ の $q$ ビット目の値

$i =1,\cdots ,m$ と $j = 1, \cdots ,T$ に対してPCPシステムの逆サンプリングアルゴリズム $S_{pcp}$ を $(y, i, q)$ に対して動作させて $r_{i,j}$ を得る。
$i =1,\cdots ,m$ と $j = 1, \cdots ,T$ に対して証明者のアルゴリズム $\tilde{P_n}$ に乱数として $(\alpha r_{i,j})$ を与えて証明を得る。その証明が「妥当」(検証を通過した)場合には添字の組 $(i,j)$ を記録する。
$i \in [m]$ であって3での添字の記録 $(i,\cdot)$ が $(2\delta/3)\cdot T$ 以上となるものがあれば、対応する証明の値 $\sigma \in \{0, 1\}$ を「候補」として記録する。
「候補」として記録されたが一意に定まった場合、答えの $q$ 番目のPCPのオラクルをとしてその値を出力する。(一意に定まらなかった場合の動作は未定義。)

この手順を以下 $E_0$ と呼びます。

PCPのオラクルを得る確率の見積もり

ここまで検証者がメッセージを受け入れる確率について $p_{y,\alpha}\geq \epsilon /2$ を仮定してきました。
今、示すべき弱い知識証明の性質(A weak proof-of-knowledge property)の元々の仮定から $Pr[(\tilde{P_n}, V)(y)=1]>\epsilon := 1/p(n)$ が成り立つことを思い出すと(簡単な計算から)少なくとも割合 $\epsilon/2$ の $\alpha$ がこの仮定を満たすことが分かります。
また上でハッシュ関数の衝突確率が矛盾が生じる確率で下から抑えられることを示しました。
これら二つの事実を用いると以下の仮定

$p_{y,\alpha}\geq \epsilon /2$ が成り立つ
$\delta/2$ -矛盾ではない返答を持つクエリーを検証者が作る確率が最大でも $p_{y, \alpha}/4$ となる

がほとんどの場合に成り立つことが分かります。
実際この仮定が成り立つ確率は $\epsilon /4$ より大きくなります。
この仮定を満たすような乱数 $\alpha$ を「有用」と呼びます。
乱数 $\alpha$ が「有用」なときには次の主張

上のPCPのオラクルを得る手順 $E_0$ が「 $V_{PCP}^{\pi} (y)=1$ となる確率が $p_{y, \alpha}/4 \geq \epsilon /8$ となるオラクル $\pi$ 」を出力する確率は $1-2^{-n}$ 以上である。

が成り立つことを以下のように示せます。
全ての「良い」クエリーに対してその定義から、ある $i\in [m]$ と返答 $\sigma \in {0, 1}$ であって「 $\sigma$ が $\delta$ -strongで $\overline{\sigma}$ が $\delta/2$ -strongではない」という性質を満たすものが存在します。このことから確率 $1-|\pi|(m+1)2^{-n^2}>1-2^{-n}$ で $E_0$ の出力は「良い」クエリーqについては $\pi$ のq番目のビットが $\delta$ -strongな値(0または1)と等しくなります。このことと上で示した「返答がほとんどstrongである」という性質から乱数 $r$ の選び方について検証者 $V$ が $p_{y, \alpha}/4$ の確率で良いクエリーだけを作り、かつ $\delta$ -strongな返答だけを受け取って証明を受け入れることが従います。このとき検証者 $V$ が証明を受け入れるのは $V_{PCP}^{\pi}$ も証明を受け入れるときに限るので上の主張を示せました。

Universal Argumentの知識を得るオラクルマシン

PCPのオラクルを得る手順 $E_0$ とPCPシステムで存在が保証されたオラクルマシン $E_{PCP}$ を組み合わせることで、弱い知識証明の性質(A weak proof-of-knowledge property)の中にあるuniversal argumentの証明者の知識を得るオラクルマシン $E$ の動作を以下のように定めることができます。

入力： $(y, i)(y=(M, x, t),\;i\in [t])$ ( $n=|y|, \delta = \epsilon/4m$ とし、証明者のアルゴリズムを $\tilde{P_n}$ へのアクセスが可能)
出力：証明者の知識の $i$ ビット目

乱数 $\alpha \in \{0,1\}^n$ をランダムに選択(「有用」だと嬉しい)
上で定義したPCPのオラクルを得るオラクル回復の手順の乱数として $\omega$ を選ぶ。 $\omega$ はPCPのオラクルを得るオラクル回復の手順のランダム性を決定づけるシード値だと捉えました。
1と2で得た乱数 $\alpha、\omega$ を固定した上で、PCPシステムで存在が保証されたオラクルマシン $E_{PCP}$ とPCPのオラクルを得る手順 $E_0$ を同時に起動させて、(証明者の知識の $i$ ビット目であるとされた)出力を得ます。出力が正しい確率が十分大きくなるまで $E_{PCP}$ の乱数を変えてオラクル回復を繰り返し最も多い回数出力された答えを出力します。

ここで3の二つの手順を「同時に起動させる」とは $E_{pcp}$ に入力 $(y, i)$ を与えてアルゴリズムを実行し、オラクルへのアクセスが求められるたびに求められた位置を $q$ ビット目として $\tilde{P_n}, y, q$ を入力としてPCPのオラクルを得るオラクル回復の手順を実行し、オラクルへのアクセスを実現するという意味です。

オラクルマシンの成功確率と実行時間

$\alpha$ が「有用」なときにはその定義から検証者が少なくとも $\epsilon /8$ の確率で納得するようなオラクル $\pi$ を出力するような乱数 $\omega$ が選ばれる確率が $1-2^{-n}$ となります。このような乱数 $\omega$ を「 $\alpha$ -有用」と呼ぶことにして、「 $\alpha$ -有用」な $\omega$ を選んだ場合には $\epsilon /8$ が無視できる確率であることとPCPの知識証明の性質(A proof-of-knowledge property)から $2/3$ の確率で $E$ の最後の $E_{PCP}$ の出力が正しいことになります。言い換えれば最後の出力が間違っている確率は最大でも $1/3$ となります。この条件を満たす $E_{PCP}$ の乱数 $\rho$ を選んだとき「 $E_{PCP}$ の乱数を変えてオラクル回復を繰り返し最も多い回数出力された答えを出力する」という方法を取ることで、入力長の多項式回数の繰り返し回数で出力が間違っている確率を $2^{-2n}$ で抑えることができます。このときには全てのビットが正しい確率も $1-t2^{-2n}\geq 1-2^{-n}$ となります。正しい出力を出力する $E_{PCP}$ の乱数 $\rho$ を「 $(\alpha ,\omega)$ -有用」と呼ぶことにします。
以上を全て考慮すると乱数を『 $\alpha$ が「有用」で $\omega$ が「 $\alpha$ -有用」で $\rho$ が「 $(\alpha ,\omega )$ -有用」』となるように選ぶ確率は $(\epsilon /4)\cdot (1-2^{-n})\cdot (1-2^{-n})>\epsilon /5 = 1/5p(n)$ （元々 $\epsilon =1/p(n)$ と定義していた）となるので多項式 $p'(n)$ を $p'(n)=5p(n)$ と定めることで $E$ の成功確率は弱い知識証明の性質の条件を満たします。
さらに $E$ の実行時間はPCPの知識を得る手順 $E_0$ に支配され、さらにこれは証明者のアルゴリズム $\tilde{P_n}$ へのアクセスを呼び出す回数に支配されます。この回数は手順の中の $T$ の多項式、つまり $n/\epsilon$ の多項式で抑えられるので $\epsilon =1/p(n)$ であったことから結局 $n$ の多項式で抑えることができます。