zk-SNARK:加密多项式

Question

我已经阅读并大致理解了Maksym的zk纸(http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf)。我正在重新阅读它，并试图在我继续的过程中对这些示例进行编码，以获得更好的理解。我犯了(希望是一个简单的)错误，但我不知道在哪里。

在3.3.4加密多项式中，讨论了验证器如何对x的随机值进行采样，对x^1, x^2, \cdots, x^d进行加密，并提供给验证器。我们得到了以下信息：

E(x^3)^1 \cdot E(x^2)^{-3} \cdot E(x)^ 2 = \\ \left(g^{x^3}\right)^1 \cdot \left(g^{x^2}\right)^{-3} \cdot \left(g^x\right)^2 = \\ g^{1x^3} \cdot g^{-3x^2} \cdot g^{2x} = \\ g^{x^3 - 3x^2 + 2x}

在哪里；

E(v) = g^v \mod n

我在纸面上遵循这一点，然而，当我试图单独评估这些陈述时，我得到的第一项和最后一项声明的结果不同。具体而言；

然后\text{let } x = 5, \text{ } g=5, \text{ } n=7 \\ E(x^1)^1 = 3 \\ E(x^2)^1 = 5 \\ E(x^3)^1 = 3

E(x^3)^1 \cdot E(x^2)^{-3} \cdot E(x)^ 2 = 0.216

然而；

g^{x^3 - 3x^2 + 2x} = 1

我不知道我在哪里搞错了。我最好的猜测是，这与没有正确应用模块化运算符有关，我一直盯着这个问题太久了，没有任何进展！任何帮助都会很棒。

Answer 1

你需要做模数运算！

减少模块化n，这是7。注意，3^{-1}=5 \pmod 7由于15减少了mod 7是1.。

然后注意到E(x)=E(x^3)=3,和E(x^2)=5给出

E(x^3) E(x^2)^{-3} E(x)^2=E(x^3)^3 E(x^2)^{-3}=(5 \times 3^{-1})^3 = 1 \pmod 7.