零知识证明|2.什么是多项式盲计算？

上一篇介绍了什么是同态隐藏。假设取$E(x) = g^x$E(x)=gx，则$E(x+y)$E(x+y)可以通过$E(x)$E(x)和$E(y)$E(y)计算出来：

$E(x+y) = E(x) \cdot E(y)$E(x+y)=E(x)⋅E(y)

实际上，不仅仅支持加法，支持所有"线性组合"的同态隐藏，比如$E(ax + by)$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$E(ax+by)=gax+by=gax⋅gby=(gx)a⋅(gy)b=E(x)a⋅E(y)b

需要注意的是，上面的加法和乘法运算都是模p运算。

假设现在有一个d次多项式$P(X) = a_0 + a_1 \cdot X + a_2 \cdot X^2 + … + a_d \cdot X^d$P(X)=a0​+a1​⋅X+a2​⋅X2+…+ad​⋅Xd，其中的系数$a_0,…,a_d \in \{0, p-1\}$a0​,…,ad​∈{0,p−1}是Alice需要保护的秘密。根据上面的特性，我们可以计算出$E(P(X))$E(P(X))：

$E(P(X)) = E(1)^{a_0} \cdot E(X)^{a_1} \cdot E(X^2)^{a_2} … \cdot E(X^d)^{a_d}$E(P(X))=E(1)a0​⋅E(X)a1​⋅E(X2)a2​…⋅E(Xd)ad​

现在Bob想来验证Alice是不是真的知道这些秘密，于是他决定随机指定一个数$s$s，要求Alice计算$E(P(s))$E(P(s))等于多少。但是，Bob不想直接把$s$s的值告诉Alice，也就是说，这个$s$s是Bob的秘密。显然，这又需要一次同态隐藏，也就是说，Bob把下面这些值提供给Alice：

$E(s), E(s^2), E(s^3), …, E(s^d)$E(s),E(s2),E(s3),…,E(sd)

然后Alice就可以根据上面的公式计算$E(P(s))$E(P(s))的值：

$E(P(s)) = E(1)^{a_0} \cdot E(s)^{a_1} \cdot E(s^2)^{a_2} … \cdot E(s^d)^{a_d}$E(P(s))=E(1)a0​⋅E(s)a1​⋅E(s2)a2​…⋅E(sd)ad​

最终的效果是：在Bob不知道P(X)中的系数是多少，而Alice也不知道s等于多少的情况下，完成多项式的验证。这就是所谓的"多项式盲计算"。

下面举个例子来加深理解，假设$P(X) = 1 + 2X + 3X^2, E(x) = 3^x, p = 7$P(X)=1+2X+3X2,E(x)=3x,p=7：

Bob想验证$s=2$s=2这一点上的$E(P(s))$E(P(s))的值，那么他需要提供这2个值：$E(s) = 2, E(s^2) = 4$E(s)=2,E(s2)=4

然后Alice根据这3个值计算$E(P(s))$E(P(s))的值然后返回给Bob：

$E(P(s)) = E(1)^1 \cdot E(s)^2 \cdot E(s^2)^3 = 3 \cdot 4 \cdot 64 |_{mod7} = 768|_{mod7} = 5$E(P(s))=E(1)1⋅E(s)2⋅E(s2)3=3⋅4⋅64∣mod7​=768∣mod7​=5

最后，我们来看一下$E(P(2))$E(P(2))是不是真的等于5：

$E(P(2)) = E(1 + 2 \cdot 2^1 + 3 \cdot 2^2) = E(17|_{mod6}) = E(5) = 3^5|_{mod7} = 243|_{mod7} = 5$E(P(2))=E(1+2⋅21+3⋅22)=E(17∣mod6​)=E(5)=35∣mod7​=243∣mod7​=5

实际上，这背后依赖的理论基础是Schwartz-Zippel引理：在一个很大的集合中随机选择一组数，满足某个多项式取值的概率几乎为0。因此，随机选一个点，然后在Alice不知道该点的值的情况下，提供多项式的值以供Bob验证。

那么问题来了：Bob怎么验证Alice提供的$E(P(s))$E(P(s))的值对不对呢？且听下回分解。

更多文章欢迎关注“鑫鑫点灯”专栏：https://blog.****.net/turkeycock
或关注飞久微信公众号：