1
$\begingroup$

I've read through, and roughly understand, Maksym Petkus' zk-SNARK paper (http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf). I'm re-reading it, and trying to code up the examples as I go along to gain a better understanding. I'm making (hopefully a simple) mistake, but I'm not sure where.

In 3.3.4 Encrypted Polynomial, the paper discusses how the verifier can sample a random value for $x$, encrypt $x^1, x^2, \cdots, x^d$, and provide them to the prover. We're given the following;

$$ 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} $$

where;

$$ E(v) = g^v \mod n $$

I follow this on paper, however, when I try to evaluate the statements individually, I get different results for the first and last statement. Concretely;

$$ \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 $$ then $$ E(x^3)^1 \cdot E(x^2)^{-3} \cdot E(x)^ 2 = 0.216 $$ However; $$ g^{x^3 - 3x^2 + 2x} = 1 $$

I'm not sure where I'm making a mistake. My best guess is that it's something to do with not applying the modulo operator correctly, I've been staring at the problem too long with no progress! Any help would be fantastic.

$\endgroup$

1 Answer 1

1
$\begingroup$

You need to do modular arithmetic!

Reduce modulo $n$ which is 7. Note that $3^{-1}=5 \pmod 7$ since $15$ reduced mod $7$ is $1.$

Then noting $E(x)=E(x^3)=3,$ and $E(x^2)=5$ gives

$$ 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. $$

$\endgroup$
1
  • $\begingroup$ Thank you - this had been driving me crazy for a couple of days! I hadn't worked with modular exponentiation with negative exponents before, so I didn't understand this at first; Reduce modulo 𝑛 which is 7. Note that 3−1=5(mod7) since 15 reduced mod 7 is 1. If anyone comes across this question in future, and also isn't familiar, this page helped me understand what's going on - Wikipedia: Modular exponentiation $\endgroup$
    – Brendan
    Commented Jan 5, 2023 at 23:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.