Score:1

zk-SNARK: Encrypted Polynomial

ch flag

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.

Score:1
sa flag

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

Brendan avatar
ch flag
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](https://en.wikipedia.org/wiki/Modular_exponentiation)
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.