Universal Arguments: 性質の検証

お知らせ
Table of Content

はじめに

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

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

Universal argumentsとは

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

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

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

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

確率的多項式時間のオラクルマシンEであってV^\piy=(M, x, t)を受け入れる確率が(yの長さに対して)十分大きいならば(x, w)\in RPr[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}と表し、mn = |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も十分小さいことを示します。
オラクルマシンの動作を次のように定義します。

  1. 乱数rと一つのi \in [1,m]を選びq_i = Q(y, r, i)とします。
  2. i', i''をランダムに選びreverse-samplingアルゴリズムS_{pcp}(y, i', q_i), (y, i'', q_i)に用いてそれぞれから乱数r', r''を得ます。
  3. 証明者のアルゴリズム\tilde{P_n}に乱数をそれぞれ\alpha,r'\alpha,r''として2組の証明者と検証者のやり取りを行います。
  4. 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システムのオラクルを得る手順は以下の通りです。Tn/\epsilonの多項式で表される数とします。
入力:(y, \alpha)q(証明者のアルゴリズム\tilde{P_n}へのアクセスが可能)
出力:PCPのオラクル\piqビット目の値

  1. i =1,\cdots ,mj = 1, \cdots ,Tに対してPCPシステムの逆サンプリングアルゴリズムS_{pcp}(y, i, q)に対して動作させてr_{i,j}を得る。
  2. i =1,\cdots ,mj = 1, \cdots ,Tに対して証明者のアルゴリズム\tilde{P_n}に乱数として(\alpha r_{i,j})を与えて証明を得る。その証明が「妥当」(検証を通過した)場合には添字の組(i,j)を記録する。
  3. i \in [m]であって3での添字の記録(i,\cdot)(2\delta/3)\cdot T以上となるものがあれば、対応する証明の値\sigma \in \{0, 1\}「候補」として記録する。
  4. 「候補」として記録されたが一意に定まった場合、答えの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の選び方について検証者Vp_{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ビット目

  1. 乱数\alpha \in \{0,1\}^nをランダムに選択(「有用」だと嬉しい)
  2. 上で定義したPCPのオラクルを得るオラクル回復の手順の乱数として\omegaを選ぶ。\omegaはPCPのオラクルを得るオラクル回復の手順のランダム性を決定づけるシード値だと捉えました。
  3. 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の多項式で抑えることができます。

以上で上で定めたオラクルマシンEが弱い知識証明の性質の条件を満たす確率多項式時間のオラクルマシンであることが分かり、弱い知識証明の性質を示すことができました。

まとめ

以上長々と説明してきましたが直感的にまとめると上のオラクルマシンの手順は

「universal argumentsの正しい証明では証明システムの中のクエリーが大体一通りに決まること」とPCPの逆サンプリングを利用して得た乱数を証明者に与えてPCPシステムのオラクルを求め、PCPシステムのエクストラクターに与えて知識を得る

と理解しました。(トンチンカンな理解だったらすみません。)
Universal argumentsは他の証明システムに応用されているということなので今度はこれがどのように応用されているのか見てみようと思います。
最後に私が理解できなかった点をいくつか挙げておきます。

  • claim 3.5.3の証明の中の\sigmaが出力される確率1-2^{-n^2}
  • Extractor for the argument systemの構成の前の文章の\alphaが「有用」となる確率\epsilon /2 - \mu (n)の導出

これらの疑問点や記事の間違いを見つけたら教えて下さい。

参考文献

[1]https://www.wisdom.weizmann.ac.il/~oded/R6/ua.pdf
[2]https://tech.hashport.io/3492/

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