Join Log in
Score:1
avatar Crypto

zkSnarks: Why does the target polynomial $t(s)$ need to be kept a secret if it's known to both prover & verifier?

et flag
user93353

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

The example used here is that there is a polynomial of degree 3 which the verifier knows has roots 1 & 2.

  • The whole polynomial is $p(x)$

  • The target polynomial $t(x) = (x-1)(x-2)$.

  • The 3rd root comes from $h(x)$, i.e. if 3rd root is 3, then $h(x) = (x-3)$.

  • And $p(x) = h(x). t(x)$.

So it seems the secret here that the prover proves to the verifier is his knowledge of $h(x)$

However, deep into the tutorial, in Section 3.6, where the author adds Non-Interactivity to the protocol, he says the following

Till this point, we had an interactive zero-knowledge scheme. Why is that the case? Because the proof is only valid for the original verifier, nobody else (other verifiers) can trust the same proof since:

  • the verifier could collude with the prover and disclose those secret parameters $s$, $\alpha$ which allows to fake the proof, as mentioned in remark 3.1

  • the verifier can generate fake proofs himself for the same reason

  • verifier have to store $\alpha$ and $t(s)$ until all relevant proofs are verified, which allows an extra attack surface with possible leakage of secret parameters

I understand how $\alpha$ is a secret & needs to be protected but why does $t(s)$ need to be protected - in the interactive version, it was something known by both the prover & verifier, so why while adding Non-Interactivity to the protocol does $t(s)$ suddenly become a secret?

74
0 + 0
Score:2
meshcollider avatar Crypto
gb flag
meshcollider

While the polynomial $t(x)$ itself is known, the specific evaluation at $s$, $t(s)$, is not known.

In the interactive version, the prover computes $g^p$ and $g^h$ in "encrypted space" as the paper calls it, by using the "encrypted" powers of $s$.

The verifier then uses $t(s)$ to check that $g^p = g^{h \cdot t(s)}$, implying $p(x) = h(x) \cdot t(x)$ with high probability.

Because $t(x)$ is known, if $t(s)$ was also known, $s$ could be recovered. This is because the polynomial $t(x) - t(s)$ has $s$ as a root, by definition. Any algorithm that computes roots of polynomials modulo $q$, for example the Cantor–Zassenhaus algorithm, could be used to find $s$. Thus, $t(s)$ must be kept secret.

In order to do so, we also encrypt $t(s)$ giving $g^{t(s)}$, and then use a bilinear pairing to perform the multiplication in the exponent of $g$.

0 + 0
ธงชาติไทย
Elon Musk
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.