The Knowledge of Coefficient Test and Assumption
m0t0k1ch1.icon < Zcash のブログ記事を読んで zk-SNARKs で用いられている技術について勉強していくシリーズ
---.icon
m0t0k1ch1.icon < そりゃそうだ!!
これを正す方法については後々説明するが、ここではその方法の基礎である Knowledge of Coefficient (KC) Test にフォーカスする。
以前のように、離散対数問題が困難である位数$ |G| = pである群$ Gの生成元を$ gとする。これからは、乗法的にでなく加法的に書くのが便利なのでそうする。すなわち、$ \alpha \in F_pのとき、$ \alpha \cdot gは$ gを$ \alpha回足し合わせたものとする。
m0t0k1ch1.icon < $ Gは加法群ということになった(加法群の生成元は、その整数倍で全ての元が表せる)
$ \alpha \in F_p^*のとき、$ a, b \neq 0と$ b = \alpha \cdot aを満たすような$ Gの元のペア$ (a, b)を α-pair と呼ぶことにすると、KC Test は以下のように行われる。
1. Bob がランダムな$ \alpha \in F_p^*と$ a \in Gを選び、$ b = \alpha \cdot aを計算する
2. Bob が Alice に α-pair$ (a, b)を伝える
3. Alice が異なる α-pair$ (a', b')を返す
4. Bob が$ (a', b')が α-pair かどうか検証する(Bob は$ \alphaを知っているので、$ b' = \alpha \cdot a'を確認すればよい)
Alice は$ \alphaを知っていれば、$ Gの中から適当に$ a'を選び、$ b' = \alpha \cdot a'を計算し、$ (a', b')を返せばよい。しかし、Alice が$ \alphaについて知っている情報は$ \alpha \cdot aと$ Gだけであり、$ Gの中では離散対数問題が困難なので、$ \alphaを見つけることはできない。では、$ \alphaを知らない Alice はどうやって$ (a', b')を返せばよいのか?
$ \gamma \in F_p^*を使って$ (a', b') = (\gamma \cdot a, \gamma \cdot b)を計算すればよい。このとき、
$ b' = \gamma \cdot b = \gamma\alpha \cdot a = \alpha(\gamma \cdot a) = \alpha \cdot a'
であり、確かに$ (a', b')は α-pair になっている。すなわち、The Knowledge of Coefficient Assumption(KCA)とは
Bob が選んだ複数の$ a, \alphaに対応する$ (a, b)に対して Alice が正しい$ (a', b')を無視できない確率で返せるのであれば、Alice は$ a' = \gamma \cdot aとなるような$ \gammaを知っている
ということである。
m0t0k1ch1.icon < あくまで、こうやったら Alice も α-pair つくれるよねという話