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, 2021 at 16:36
  • $\begingroup$ @Vadym I meant information-theoretical hiding $\endgroup$
    – Bean Guy
    Aug 19, 2021 at 20:04
  • $\begingroup$ Re question 2: could you see all the polynomials are evaluated outside $H$ while creating the proof? $\endgroup$ Aug 20, 2021 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, 2021 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, 2021 at 7:48

1 Answer 1

  1. the degree of the blinding polynomial that you're multiplying with the vanishing polynonial $Z_H$ has to be sampled from $F_d[X]$ with $d$ greater or equal to the number of evaluations in the protocol (openings). Every evaluation given to the verifier leaks some information about your polynomial, so you need to prevent that by randomizing your polynomial. Mir protocol has a nice blogpost that explains why you can't have $d$ smaller than the number of evaluations. My understanding is that for a fixed witness (the polynomial is fixed except for the blinding factors), you want a bijective function between your blinding coefficients and the openings. To prove that, prove that your function is surjective and injective.

  2. the probability that $z \in H$ is negligible, but you could design a protocol that prevents you from having $z \in H$ I believe.

  • 1
    $\begingroup$ I don't know why they don't prove that this is enought to achieve zero-knowledge in the PlonK protocol. At least, they could have pointed to the paper the idea is based on (I think it has to do with some paper from Groth, but I have not found it). $\endgroup$
    – Bean Guy
    Feb 1, 2022 at 8:25
  • $\begingroup$ @BeanGuy, David - I don't get where exactly the blog explains that you need a blinding polynomial whose degree is at minimum same at the number of evaluations. I assume the $k$ used in the blog is the number of evaluations. The post chooses a blinding polynomial which of degree less than k - i.e. $\mathbb F_{<k​}[x]$. It also says further ahead "namely the unique degree <k" $\endgroup$
    – user93353
    Jul 5, 2023 at 8: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.