3
$\begingroup$

In Groth16 Page 14

The prover does

$C = \frac {\sum_{i = l+1}^m a_i ( \beta u_i(x) + \alpha v_i(x) + w_i(x)) + h(x)t(x)}{\delta} + As + r\beta − rs\delta$

And the verifier

$A \cdot B = \alpha \cdot \beta + \frac {\sum_{i=0}^{l} a_i (\beta u_i(x) + \alpha v_i(x) + w_i(x)) }{\gamma} \cdot \gamma + C \cdot \delta$

On Page 15, an explanation is given

The role of $\gamma$ and $\delta$ is to make the two latter products of the verification equation independent from the first product, by dividing the left factors with $\gamma$ and $\delta$ respectively. This prevents mixing and matching of elements intended for different products in the verification equation.

I am unable to understand this - what does it mean "two latter products of the verification equation independent from the first product"

What is the mixing & matching being talked about & what kind of attack is prevented by doing this?

$\endgroup$

1 Answer 1

1
$\begingroup$
  1. "Two latter products of the verification equation independent from the first product" - Recall that from the construction, $A, B, C$ are linear combinations of $$\sigma = \left ( \alpha, \beta, \gamma, \delta, \{x^i\}^{n−1}_{i=0} , \left\{ \frac{\beta u_i(x)+ \alpha v_i(x)+ w_i(x)}{\gamma} \right\}^{\ell}_{ i=0} , \left\{ \frac{\beta u_i(x)+ \alpha v_i(x)+w_i(x)}{\delta} \right\}^{m}_{i=\ell+ 1}, \left\{ \frac{x^i t(x)}{\delta} \right\}^{n−2}_{i=0} \right )$$ As mentioned on page 15, we can view $A, B$ and $C$ as formal polynomials in indeterminates $\alpha, \beta, \gamma, \delta, x$. Now the product $C \cdot \delta$ does not contain a term $\alpha \beta$, making it independent from the first product (which is $\alpha \beta$) in the verification equation. Similarly, because of $\gamma$, the second product (which is just a linear polynomial in $\alpha$ and $\beta$) in the verification equation is also independent of $\alpha \beta$.
  2. "This prevents the mixing and matching of elements" - By meticulously using $\gamma$ and $\delta$, the right-hand side of the verification equation does not contain unnecessary factors of $\alpha^2, \beta^2, \frac{1}{\delta^2}, \frac{1}{\gamma^2},$ etc. (see proof of Theorem 1). Eventually, this will help one to show that $A$ and $B$ given by the (malicious) affine prover will be of the form $A = \alpha + A(x) + A_{\delta} \delta $ and $B = \alpha + B(x) + B_{\delta} \delta $ which is very similar to the $A$ and $B$ generated in the $\mathsf{Prove}(R, \sigma, a_1, \dots , a_m)$. And later continues to extract the witness $a_{\ell+1}, \dots, a_{m}$. Since, these calculations does not take into consideration the behaviour of the adversary/prover, the scheme is secure against unbounded adversaries also as stated in Theorem 1 (refer to the definition of statistical knowledge soundness against affine prover strategies).
$\endgroup$
1
  • 1
    $\begingroup$ It may take me a little while to understand your answer, so please bear with me. If the bounty expires, I will add a new bounty to give you if I accept the answer $\endgroup$
    – user93353
    Commented Jul 8 at 6:01

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.