ZK-SNARKs 多項式のブラインド評価
要約
Aliceがある多項式P(X)(例えばx^2+x+17 mod 29)を持っているとき、BobはXにs(例えば3)を代入したP(s)(例えば、この場合は0)を暗号化したE(P(s))を知りたい。ただしBobはsを直接送りたくないし、AliceはPを直接教えたくない。
多項式
多項式のブラインド評価はZK-SNARKsの核。
$ \mathbb F_pのサイズはpである。つまり、$ \mathbb F_p= \{0,1,\cdots ,p-1\}
次元dの多項式 Pを
$ P(X) = a_0 + a_1\cdot X + a_2\cdot X^2 + ...... + a_d\cdot X^d
と定義する。($ \{ a_0, a_1,\cdots,a_d\}はFpの要素)
s（$ \mathbb F_pの要素）でPを評価する場合、合計は以下のように計算される
$ P(s) = a_0 + a_1\cdot s + a_2\cdot s^2 + ..... + a_d\cdot s^d
a: weights
1, s, ,,,,,, sd : weighted sum
HHの線型性
HHはlinear combinations(線型結合)もサポートしている。つまり、
a,b, E(x), E(y)を所与として、
$ 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 と Bobを想定する。
Aliceが次元dの多項式Pを持っていると仮定する。$ P(X) = a_0 + a_1\cdot X + a_2\cdot X^2 + ...... + a_d\cdot X^d
Bobが$ \mathbb F_pの要素sを持っており、E(P(s))を知りたいとする。
この場合、2つの方法が考えられる。
AliceがPをBobに送りBobがE(P(s))を計算する。
BobがsをAliceに送りAliceがE(P(s))を計算した上でBobに値を返す。
多項式のブラインド評価では、BobにE(P(s))をPなしで、Aliceがsなしで計算を行う。一見不可能に思えるが解法は以下のようになる。
BobがAliceに、$ E(1), E(s),....,E(s^d)を送る
AliceがE(P(s))を計算し、BobにE(P(s))の値を送る。Eがlinear combinationsをサポートしていて、P(s)がlinear combinationsなので計算可能。
$ E(x)=g^x\ {\rm mod}\ pの場合、具体的には、
$ E(P(s))=E(a_0 + a_1\cdot s + a_2\cdot s^2 + ..... + a_d\cdot s^d)\\=E(1)^{a_0}\cdot E(s)^{a_1}\cdot \cdots \cdot E(s^d)^{a_d}