0
$\begingroup$

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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? $\endgroup$
    – user93353
    Commented Oct 16, 2021 at 0:44
  • $\begingroup$ The best that I can manage is the remark at the bottom of page 12 of this paper $\endgroup$
    – Daniel S
    Commented Oct 16, 2021 at 4:40
  • $\begingroup$ 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? $\endgroup$
    – user93353
    Commented Oct 16, 2021 at 9:31
  • $\begingroup$ 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). $\endgroup$
    – Daniel S
    Commented Oct 18, 2021 at 19:52
  • $\begingroup$ 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? $\endgroup$
    – user93353
    Commented Oct 19, 2021 at 7:04

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.