I was reading the paper PlonK and in the Round 1 of the claim to achieve zero-knowledge by adding random multiples (of degree one) of the polynomial $Z_H = x^n - 1$ to the secret polynomials.

Here, $H$ is the set containing the $n$-th roots of unity and tipically described as $$H = \{\omega, \dots, \omega^{n-1}, \omega^n = 1\},$$ where $\omega$ is a primitive $n$-th root of unity.

So, the setting is as follows: We have a secret polynomial $s(x)$ such that we have to evaluate at some random point $z \in \mathbb{Z}_p$, begin $z$ and the evaluation $s(z)$ publicly known.

To avoid leaking the knowledge of $s(z)$, they define: $$s'(x) := (b_1x + b_2)Z_H(x) + s(x),$$ and they claim that this is enough to obtain zero-knowledge of $s(z)$.

I have two questions:

  1. Why the multiple of $Z_H(x)$ has degree one and not, for instance, four or 69? In round 2 of PlonK they use the same strategy, but with another polynomial of degree two. Why?
  2. Why is this true? If $z \in H$, then clearly $s'(x)$ leads information about $s(x)$, as $$s'(z) = s(z).$$
  • $\begingroup$ Regarding zero knowledge, did you mean simulator algorithm? $\endgroup$ Aug 19 '21 at 16:36
  • $\begingroup$ @Vadym I meant information-theoretical hiding $\endgroup$
    – Bean Guy
    Aug 19 '21 at 20:04
  • $\begingroup$ Re question 2: could you see all the polynomials are evaluated outside $H$ while creating the proof? $\endgroup$ Aug 20 '21 at 4:44
  • $\begingroup$ @VadymFedyukovych In a future round in PlonK, they evaluate polynomials like $s'(x)$ outside $H$ and send the evaluation to the verifier. Otherwise, an evaluation of $s'(x)$ in an element of $H$ would also reveal the evaluation of $s(x)$. $\endgroup$
    – Bean Guy
    Aug 20 '21 at 7:04
  • $\begingroup$ Could we agree that (1) to leak information about the witness it is required to evaluate $s'()$ on $H$, and (2) this happen with a negligible probability? What did you mean with "otherwise"? "Negligible" above is applicable to signatures and chances to guess some private key. $\endgroup$ Aug 20 '21 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.