Maksym介绍的zkSnark :多项式是在$Z$上定义的还是在$Z_n$上定义的？

Question

我正在阅读由Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf编写的对zkSnark的解释。

这里他有一个多项式

p(x) = x^3 − 3x^2 + 2x

定义为E(c) = g^c \bmod 7的同态加密

对于多项式是在Z上定义的还是在Z_7上定义的，还有点不清楚--它在文本中留下了一些不明确的地方。

这在验证器评估E(h.t) = E(h)^t的步骤中很重要。我可以更好地用Z_{11}而不是Z_7来解释我的问题，所以我在下面使用Z_{11}。

让我们假设E(c) = g^c \bmod 11

验证者样本，S= 14

E(s^0)= 5, E(s^1)= 9, E(s^2) = 5, E(s^3) = 9

验证器计算E(p(s)) = (9 * 5^{-3} * 9^2) \bmod 11 = 9

计算E(h(s)) = 5。将E(p)= 9和E(h) =9发送给验证者

验证器计算t(s=14)考虑两种情况

Case1:多项式在Z上，t(s=14) = (13*12) = 156 So E(h)^t = 9^156 \bmod 11 = 9

因此，它验证了-> E(p) = E(h)^t

Case2:多项式在Z_{11}上，t(s=14) = (13*12)%11 =2，所以E(h)^t = 9^2 \bmod 11 = 4。但这并不能证实。

它不验证的原因是

g^c \bmod m = g^{c \bmod m-1} \bmod m

也就是说，t(s)需要减少10，而不是11，但是如果多项式是Z_{11}上的，那么它就会减少11而不是10。

基于此，我认为多项式是在Z上而不是在Z_7上定义的。

然而，在第7页，他写道

虽然理论上多项式系数c_i可以有很大的范围，但实际上，它可能是相当有限的(在前面的例子中有6个)

六号是从哪来的？如果它是在Z上，那么共同效率可以是任何整数。如果他写的是限制在6，那么它必须是通过一些Z_n。如果它是在Z_7上，那么它将被限制在7，而不是6。如果它是在Z_6上，那么它将被限制在6美元。

那么多项式是定义的还是Z的，还是在Z_7上定义的，还是在Z_6上定义的呢？

Answer 1

对于最通用的应用程序，我们想要的是在p(x)之上定义\mathbb Z。然而，没有一般的有限同态密码体制，我们可以内射映射元素的\mathbb Z。相反，我们必须映射到一个大素数域(请注意，第3.2节介绍了积分域的使用)，这应该足以演示由小整数根构造的p(x)知识。这个组被表示为我们使用的任何密码群的素数序子群(我们可以在完整的组中工作，但正如所指出的，这会遇到不属于整数域的问题)。在组(\mathbb Z/7\mathbb Z)^\times的情况下，组是6级的，我们应该认为，为了验证目的，如果我们不关心在一个整体域中工作，p(x)是在\mathbb Z/6\mathbb Z之上定义的。因此，在您的mod 11示例中，应该将p(x)视为多项式mod 10 (再次忽略非积分域的问题)。如你所知，像这样的小例子遇到了各种各样的模糊问题，随着子群的规模相对于根的大小和数量的增长，这些问题变得几乎不可能了。