Score:0

zkSnark Intro by Maksym Petkus: Is the polynomial defined over $Z$ or is it defined over $Z_n$?

et flag

I am reading this explanation of zkSnark written by Maksym Petkus - http://www.petkus.info/papers/WhyAndHowZkSnarkWorks.pdf

Here he has a polynomial $p(x) = x^3 − 3x^2 + 2x$

and the homomorphic encryption defined as $E(c) = g^c \bmod 7$

It's a little unclear as to where the polynomial is defined over $Z$ or is it defined over $Z_7$ - it's left a little ambiguous in the text.

This matters in the step where the verifier evaluates $E(h.t) = E(h)^t$. I can better explain my question with $Z_{11}$ instead of $Z_7$, so I am using $Z_{11}$ below.

Let's assume $E(c) = g^c \bmod 11$

Verifier samples at s = 14

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

Prover calculates $E(p(s)) = (9 * 5^{-3} * 9^2) \bmod 11 = 9$

calculates $E(h(s)) = 5$. Sends E(p)= 9 and E(h) = 9 to verifier

Verifier calculates t(s=14) Consider two cases

Case1: Polynomial is over $Z$ In this case, t(s=14) = (13*12) = 156 So $E(h)^t$ = $9^156 \bmod 11 = 9$

So it verifies -> $E(p) = E(h)^t$

Case2: Polynomial is over $Z_{11}$ In this case, t(s=14) = (13*12)%11 = 2 So $E(h)^t$ = $9^2 \bmod 11 = 4$. Here it doesn't verify.

The reason it doesn't verify is because

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

i.e. t(s) needs to be reduced by 10 rather than by 11. However if the polynomial is over $Z_{11}$, then it gets reduced by 11 rather than by 10.

So based on this, I think the polynomial is defined over $Z$ rather than over $Z_7$.

However on page 7, he writes

while theoretically polynomial coefficients $c_i$ can have a vast range of values, in reality, it might be quite limited (6 in the previous example)

Where did the 6 come from here? If it's over $Z$, then co-efficient can be any integer. If he writes it's limited to 6, then it has to be over some $Z_n$. If it was over $Z_7$, then it would be limited to 7 & not 6. If it was over $Z_6$, then it would be limited to 6$.

So is the polynomial defined or $Z$ or is it defined over $Z_7$ or is it defined over $Z_6$?

Score:1
ru flag

What we would like for the most general applications is for $p(x)$ to be defined over $\mathbb Z$. However, there is no general, finite homomorphic cryptographic scheme into which we can injectively map elements of $\mathbb Z$. Instead we have to map into a large prime field (note that section 3.2 elides the use of an integral domain), which should suffice for demonstrating knowledge of $p(x)$ constructed from small integer roots. This group is represented as a prime order subgroup of whatever cryptographic group we’re using (we can work in the full group, but as noted this runs into the problem of not being an integral domain). In the case of the group $(\mathbb Z/7\mathbb Z)^\times$, the group is of order 6 and we should think that for verification purposes $p(x)$ is defined over $\mathbb Z/6\mathbb Z$ if we’re not concerned with working in an integral domain. In your mod 11 example therefore $p(x)$ should be thought of as a polynomial mod 10 (again ignoring problems of non-integral domains). As you can tell, small examples such as this run into all manner of ambiguity problems which become vanishingly unlikely as the size of the subgroup grows relative to the size and number of roots.

et flag
That the group of the polynomial is different from the group of the exponentiation for encryption is a pretty big detail. I am very surprised the author didn't think it important enough to put it in the text. Do you know of other texts or books or sites which cover this part of zkSnark in better detail?
Daniel S avatar
ru flag
The best that I can manage is the remark at the bottom of page 12 of [this paper](https://www.iacr.org/archive/crypto2006/41170094/41170094.pdf)
et flag
The remark talks about subgroups, but in this case, because of the $g^c \bmod m$ = $g^{c \bmod m-1} \bmod m$, I think only one subgroup will work - the polynomial ring formed by $\bmod {m-1}$. Or am I wrong?
Daniel S avatar
ru flag
This will depend on the multiplicative order of $g$ modulo $m$. We will be working in the polynomial ring modulo this order. Petkus is playing a little fast and loose here. Section 3.2 makes it clear that the fundamental theorem of algebra is in use, but this only applies to polynomials over fields (for example $x^3-3x^2+2x$ has six roots in $\mathbb Z/\6\mathbb Z$). For rigour one should use $g$ of prime order (which is the case in cryptographic applications).
et flag
I am looking for rules or steps here - if I want to implement this scheme for a polynomial, then after I define E(c) = g^c mod p, how do I then choose the ring over which the polynomial is defined. Should the polynomial be defined over mod p, mod (p-1) or some other ring. If some other ring, then what is that ring?
Daniel S avatar
ru flag
You should choose a $g$ of order $q$ where $q$ is the largest prime dividing $p-1$. The polynomial is then defined mod $q$.
et flag
Petkus's example doesn't seem to be following this rule. His g is of order 6. His g is not even of prime order, let alone of prime order with the largest prime dividing p-1. He should have chosen a g of order 3, right?
et flag
Also in the foot note of page 16, Petkus asks to choose a g which is a generator of the finite field. Which is not the same as 'choose a g of order q where q is the largest prime dividing p-1'.
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.