2
$\begingroup$

As a beginner in cryptography and zk-SNARKs, I am currently working through the paper "Why and How zk-SNARK Works".

There, I don't understand the last section at the bottom of page 15:

While in such protocol the prover’s agility is limited he still can use any other means to forge a proof without actually using the provided encryptions of powers of $s$, for example, if the prover claims to have a satisfactory polynomial using only 2 powers $s^3$ and $s^1$ , that is not possible to verify in the current protocol.

I think I understood the previous sections and chapters well. In this specific subchapter, the author shows introduces strong homomorphic encryption and then presents a zk-SNARK (like?) protocol, where the verifier provides encrypted powers of a secret value to the prover, and the prover then convinces the verifier of having a polynomial $p$, of which $t$ is part of. But I don't understand how using only $s^3$ and $s^1$, the prover could fool the verifier - and is it only 3 and 1, or also with other degrees? I would be happy if you could explain it well-understandable.

$\endgroup$
1
  • $\begingroup$ I guess the mentioned example is related to the polynomial $p(x)=x^3-3x^2+2x$. In this instance, acutally $t(x)=(x-1)(x-2)$ and $h(x)=x$. In other words, if there are no restrications on the dishonest prover, then he can let $p(x)=(x-1)(x-2)(3x+9)=3x^3-21x+18$ and $h(x)=(3x+9)$ using only $x^3$ and $x^1$. Therefore, we need to employ KEA assumption to restrict the polynomial. $\endgroup$
    – X.H. Yue
    Mar 14 at 8:13

1 Answer 1

0
$\begingroup$

The paper says

While in such protocol the prover’s agility is limited he still can use any other means to forge a proof without actually using the provided encryptions of powers of $s,$ for example, if the prover claims to have a satisfactory polynomial using only 2 powers $s^3$ and $s^1$, that is not possible to verify in the current protocol.

I think you have misunderstood this statement. It is essentially saying that if the verifier does not restrict the prover, or rather the protocol design does not restrict the prover, it is likely that there exist some other (probably higher degree) polynomials that will pass the test.

This becomes clearer as one reads on into the following page. To restrict the prover means that the prover will have to prove that he/she hasn't used any exponents of $s$ other than the two that are required to obtain the result. This is achieved by the KEA mechanism, described further on.

enter image description here

$\endgroup$
2
  • $\begingroup$ I don't think "restricting the polynomial" & "KEA" is talking about using higher exponent terms. It's about fixing the problem of the prover ignoring the $E(s^n)$s sent by the verifier & creating his own $E(p)$ & $E(h)$ - that's what the KEA prevents. $\endgroup$
    – user93353
    Jun 22, 2022 at 10:02
  • $\begingroup$ The prover knows $g$ (it's the same as $E(1)$). He assumes some random number say $r=6$. He calculates $E(h) = g^r \bmod p$. He then calculates $E(p) = {(g^t)}^r$. He sends this $E(h)$ & $E(p)$ to the verifier. Verifier calculates ${E(h)}^t$ - it will match with the $E(p)$ sent by the prover. This is the thing which KEA is used to prevent. So verifier has sent something which verifies right even though he has totally ignored the $E(s^1)$, $E(s^2)$, $E(s^3)$ etc sent by verifier $\endgroup$
    – user93353
    Jun 22, 2022 at 10:06

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.