Blind Evaluation of Polynomials
m0t0k1ch1.icon < Zcash のブログ記事を読んで zk-SNARKs で用いられている技術について勉強していくシリーズ
---.icon
m0t0k1ch1.icon < 体が出てきた。。自分はまだ群しか知らないが、、一旦目を瞑ろう。。
$ P(X) = a_0 + a_1 \cdot X + a_2 \cdot X^2 + \ldots + a_d \cdot X^d
$ a_0, \ldots, a_d \in F_p
という多項式について、点$ s \in F_pを$ Xに代入すると、以下のようになる。
$ P(s) = a_0 + a_1 \cdot s + a_2 \cdot s^2 + \ldots + a_d \cdot s^d
$ Pを知っている人からすると、$ P(s)は$ 1, s, \ldots, s^dの線型結合である。
また、Homomorphic Hidings で定義した$ E(x) = g^xという HH は$ E(x)と$ E(y)から$ E(x + y)を計算できるので、加算をサポートする HH と言うことにする。 ここで、$ E(x) = g^xは 線型結合をサポートする HH と言うこともできる。すなわち、$ a, b, E(x), E(y)から$ E(ax + by)が計算できるということである。理由は以下。
$ E(ax + by) = g^{ax + by} = g^{ax} \cdot g^{by} = (g^x)^a \cdot (g^y)^b = E(x)^a \cdot E(y)^b
Alice が次数$ dの多項式$ Pを持っていて、Bob が$ s \in F_pを持っているとする($ sは Bob がランダムに選ぶ)。Bob は$ E(P(s))を知るには、以下の 2 つの方法が考えられる。
Alice が Bob に$ Pを伝え、Bob が$ E(P(s))を計算する
Bob が Alice に$ sを伝え、Alice が$ E(P(s))を計算し、結果を Bob に伝える
ここで、
Alice に$ sを知られたくない
Bob に$ Pを知られたくない
という場合でも、線型結合をサポートする HH を利用することで Bob は$ E(P(s))を知ることができる。
1. Bob が Alice に$ E(1), E(s), \ldots, E(s^d)を伝える
2. Alice が$ E(P(s))を計算し、結果を Bob に伝える
このとき、Alice が$ E(P(s))を計算できる理由は以下。
$ E(P(s))
$ = E(a_0 + a_1 \cdot s + a_2 \cdot s^2 + \ldots + a_d \cdot s^d)
$ = E(1)^{a_0} \cdot E(s)^{a_1} \cdot E(s^2)^{a_2} \cdot \ldots \cdot E(s^d)^{a_d}
m0t0k1ch1.icon < ちなみに、Zcash プロトコルでは$ dは最大 2,000,000 程度らしい
m0t0k1ch1.icon < Bob が Alice に伝える情報をシステムにハードコードしたとしても、Alice の$ P(s)が毎回違えばよいと