Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
From the PLONK paper.
Page 29, Round 3
The paper doesn't explain the need or the use of the quotient challenge $\alpha$.
I understand why each of the polynomials is multiplied by $\frac {1}{Z_H}$ but don't understand why the second is also multiplied by $\alpha$ & the last by $\alpha^2$ - what purpose does the quotient challenge serve & why are different powers used? I can't find this discussed anywhere in the paper.
The quotient challenge is necessary for soundness. In particular, if the prover wants to show that there exists quotients $q_1=f_1/z_H$, $q_2=f_2/z_H$, and $q_3=f_3/z_H$. To do so, it can instead send $q = (f_1+\alpha f_2+\alpha^2 f_3)/z_H$, where $\alpha$ is a verifier challenge (or the output of Fiat-Shamir). Then, the verifier can query at a random $\beta$ to check the identity $(f_1(\beta)+\alpha f_2(\beta)+\alpha^2 f_3(\beta))-z_H(\beta)q(\beta) = 0$.
Here's a sketch of the proof of soundness. We want to show that $f_1, f_2, f_3$ are zero over $H$. Let's consider the polynomial $$F(X,Y)=f_1(X)+Yf_2(X)+Y^2f_3(X)$$ I will argue that $F(X,Y)$ vanishes for all $x=h\in H$ if and only if $f_1, f_2, f_3$ vanish over $H$. Consider an arbitrary element $h\in H$, $$F(h, Y)=f_1(h)+Yf_2(h)+Y^2f_3(h)=0$$ if and only if $f_1(h)=f_2(h)=f_3(h)=0$. This is because the $Y$ powers are linearly independent.
The verifier can perform a randomized test to check if $F(X,Y)$ vanishes over $H$. First it sends a challenge $Y=\alpha$. Then, the honest prover sends back $q(X)=F(X,\alpha)/z_H$ to prove that the resulting polynomial vanishes on $H$.
Let's consider the probability for which a malicious prover gets caught. There must be at least one element $h'\in H$ such that $f_1(h')+Yf_2(h')+Y^2f_3(h')\neq 0$. Since we queried at a random $\alpha$, by Schwartz-Zippel lemma, $f_1(h')+\alpha f_2(h')+\alpha^2f_3(h')=0$ occurs with probability less than $\frac{2}{|\mathbb{F}|}$. Thus, with high probability, there cannot exist a quotient $q(X)$ such that $F(X, \alpha)=z_H(X)q(X)$. Hence, the $q(X)$ that the malicious prover sent cannot be a valid quotient.
Now the verifier has to check that $q(X)$ is a valid quotient, which requires another randomized check to $X=\beta$ to check $F(\beta, \alpha)=z_H(\beta)q(\beta)$.
