多项式的非交互式零知识证明

简介上一篇文章（多项式的性质与证明）中，作者讲解了如何利用多项式的性质来证明某个多项式的科学知识，坚信大家早已对结构证明有了一些基本的了解。目前的证明协议依然不存在一些缺失，本文将不会针对这些脆弱项展开改良，进而最后结构出有关于多项式的零科学知识证明协议。

本文重点：KEA，交互式零科学知识证明，非交互式零科学知识证明和 Setup。作者：Maksym Petkus翻译成注释：[emailprotected]安比实验室（[emailprotected]）编辑：[emailprotected]安比实验室本系列文章已获得作者中文翻译许可。容许多项式上文说到，多项式的科学知识只不过就是它的系数 c0, c1, …, ci 的科学知识。

协议中我们是通过对秘密值 s 的幂的加密值再行展开欲幂来对系数展开“赋值”。我们早已容许了 prover 对 s 幂的加密值的自由选择, 但是这个容许并不是强迫的 ，也就是说，prover 可以用于任何有可能的方法寻找符合下面等式的值 zp 和 zh解决问题这个问题的一种方法就是用另一个“转换”的加密值做到某种程度的操作者，当作类似于算术中“校验和”（Checksum） 的起到，以此保证结果是完整值的欲幂值。这个是通过 Knowledge-of-Exponent Assumption (全称 KEA) 方法来构建的，在 [Dam91] 中有讲解，更加精准一点（留意 a 和 α(alpha)这两个字符的有所不同）说道：a）Alice 有一个值 a，她想 Bob 对其展开给定指数的欲幂（这里 a 是一个受限域群的生成器），唯一的拒绝是不能对 a 展开欲幂，为了确保这一点，她要：· 自由选择一个随机数 α· 计算出来 a' = a α(mod n)· 获取一个元组 (a, a') 给 Bob, 然后让他对这两个值继续执行给定的欲幂运算，回到结果元组 (b, b')，这里的指数 “α-转换” 仍然维持恒定，即 bα = b'(mod n)b) 因为 Bob 无法从元组 (a, a') 中萃取 α 的值，通过暴力破解也难以实现，那就可以推测 Bob 分解有效地元组的唯一方法就是继续执行下面的步骤：· 自由选择一个值 c· 计算出来 b=(a)c(mod n) 和 b' = (a')c (mod n)· 恢复 (b,b')c) 有了恢复的元组和 α，Alice 就可以检验等式：结论是：· Bob 在元组的两个值的计算出来上都用了同一个指数（即 c）· Bob 不能用 Alice 原本的元组来维持 α 关系· Bob 告诉指数 c，因为结构检验值 (b,b′) 的唯一方式是用同一个指数· Alice 并不知道 c，这和 Bob 不告诉 α 的原因一样· 虽然 c 是被加密的，但它的有可能给定范围并不充足大到维持其零科学知识的性质，这个问题我们将在后面“零科学知识”那一节解决问题。

最后这个协议获取了一个证明给 Alice ，Bob 显然是用他告诉的某个值对 a 展开欲幂的，而且他也无法做到别的任何操作者，例如：乘法，乘法，因为这样就不会毁坏 α-转换关系。在同态加密中，欲幂是对被加密值展开乘法运算。

我们可以应用于这个结构到一个非常简单的系数多项式 f(x) = c⋅ x的例子中：这个结构“容许” prover 不能用 verifier 获取的加密的 s 展开计算出来，因而 prover 不能将系数 c 赋给 verifier 获取的多项式。现在我们可以拓展这种单项式上的方法到多项式上，因为计算出来是再行将每项的分配分离计算出来然后再行 “同态地” 互为加在一起的（这个方法是 Jens Groth 在 [Gro10] 中讲解的）。所以如果等价 prover 一个指数为 s 的幂以及它们的转换的加密值，他就可以计算出来完整的和转换后的多项式，这里也必需要符合某种程度的校验。对于阶数为 d 的多项式：现在我们就可以保证 prover 是用了 verifier 获取的多项式而不是其它值做到计算出来的了，因为别的方法不需要维持 α-转换。

本文来源：千亿体育官网登录入口-www.hammerheadiiibooks.com