Score:2

Does the degree of this polynomial matter to achieve zero-knowledge? PlonK question

in flag

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).$$
Vadym Fedyukovych avatar
in flag
Regarding zero knowledge, did you mean simulator algorithm?
Bean Guy avatar
in flag
@Vadym I meant information-theoretical hiding
Vadym Fedyukovych avatar
in flag
Re question 2: could you see all the polynomials are evaluated outside $H$ while creating the proof?
Bean Guy avatar
in flag
@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)$.
Vadym Fedyukovych avatar
in flag
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.
Bean Guy avatar
in flag
@VadymFedyukovych Yes, we totally agree. My concern is more about why the degree of the polynomial $b(x) = b_1x+b_2$ is $1$ and not, for instance $0$ or $2$.
Score:2
kr flag
  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.

Bean Guy avatar
in flag
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).
et flag
@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"
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.