从零开始学习 zk-SNARK（二）——多项式的非交互式零知识证明

导读

上一篇文章（多项式的性质与证明）中，作者介绍了如何利用多项式的性质来证明某个多项式的知识，相信大家已经对构造证明有了一些基本的认识。目前的证明协议仍然存在一些缺陷，本文将会针对这些薄弱项进行改进，进而最终构造出关于多项式的零知识证明协议。本文重点：KEA，交互式零知识证明，非交互式零知识证明和 Setup。
—— even@安比实验室

作者：Maksym Petkus
翻译 & 注解：even@安比实验室（even@secbit.io）
校对：valuka@安比实验室
本系列文章已获作者中文翻译授权。

限制多项式

上文说到，多项式的知识其实就是它的系数 c0, c1, …, ci 的知识。协议中我们是通过对秘密值 s 的幂的加密值再进行求幂来对系数进行“赋值”。我们已经限制了 prover 对 s 幂的加密值的选择, 但是这个限制并不是强制的 ，也就是说，prover 可以使用任何可能的方法找到满足下面等式的值 $$Z_p$$ 和 $$Z_h$$

$$Z_p=(Z_h)^{t(s)}$$

再用这两个值来代替 gᵖ 和 gʰ 将它交给 verifier。所以 verifier 需要能够证明 prover 给出的值就是用 s 幂的加密值而不是其它值计算出来的。

我们看一个由一个变量和一个系数组成的一阶多项式的简单例子，对应的 s 的加密值为 E(s) = gˢ。这里我们要做的就是确保 prover 是拿 s 的加密值，即 gˢ ，而不是其他值与系数 c 做同态相乘的。所以结果一定是这个形式（c 为任意值）：

$${(g^s)}^c$$

解决这个问题的一种方法就是用另一个“变换”的加密值做同样的操作，充当类似算术中“校验和”（Checksum） 的作用，以此确保结果是原始值的求幂值。

这个是通过 Knowledge-of-Exponent Assumption (简称 KEA) 方法来实现的，在 [Dam91] 中有介绍，更精准一点（注意 a 和 α(alpha)这两个字符的不同）说：

a）Alice 有一个值 a，她想要 Bob 对其进行任意指数的求幂（这里 a 是一个有限域群的生成器），唯一的要求是只能对 a 进行求幂，为了保证这一点，她要：

• 选择一个随机数 α

• 计算 a' = $${a^\alpha}$$（mod n）

• 提供一个元组 (a, a') 给 Bob, 然后让他对这两个值执行任意的求幂运算，返回结果元组 (b, b')，这里的指数 “α-变换” 依然保持不变，即 $${b^\alpha}$$ = b'(mod n)

b) 因为 Bob 无法从元组 (a, a') 中提取 α 的值，通过暴力破解也难以实现，那就可以推断 Bob 生成有效元组的唯一方法就是执行下面的步骤：

选择一个值 c

计算 b=(a)c(mod n) 和 b' = (a')c (mod n)

回复 (b,b')

--未完待续--