4
$\begingroup$

From GGPR13

Section 7.1, Page 42

($v_0(x) +\sum_{k=1}^m a_k \cdot v_k(x)) \cdot (w_0(x) +\sum_{k=1}^m a_k \cdot w_k(x)) - (y_0(x) +\sum_{k=1}^m a_k \cdot y_k(x))$

If you notice, the term $a_k$ is there only for $k = 1$ to $m$. The first terms $v_0, w_0, y_0$ have been brought outside the summation - i.e. equivalent to setting $a_0 = 1$

Likewise in Groth16

Section 2.3, Page 9

The equations will be over $a_0 = 1$ and variables $a_1, \dots a_m \in F$ and be of the form

$\sum a_iu_{i,q} \cdot \sum a_iv_{i,q} = \sum a_iw_{i,q}$

Here they don't bring the first term out with no co-efficient but specify $a_0 = 1$

I understand that $a_0$ can be made 1 by dividing all other coefficients with the previous $a_0$ but why is it done?


Also, in site or blog which explains Groth16 - for e.g. Groth16 under the hood, I can't find the examples actually enforcing this $a_0=1$ at all - they just seem to ignore this.

$\endgroup$
4
  • $\begingroup$ My guess, they are monic and 1 doesn't add to security. $\endgroup$
    – kelalaka
    Commented Jun 28 at 11:53
  • $\begingroup$ My question is why do they need to be monic? And what do you mean "1 doesn't add to security"? $\endgroup$
    – user93353
    Commented Jun 28 at 13:32
  • $\begingroup$ It is common to keep the polynomials monic. It reduces the computation and keeps them simple. Once monic, the attacker knows the value 1. $\endgroup$
    – kelalaka
    Commented Jun 28 at 17:25
  • $\begingroup$ Attackers know the value 1 is bad, right? Also how does it reduce computation? $\endgroup$
    – user93353
    Commented Jun 30 at 12:33

1 Answer 1

1
+50
$\begingroup$

$a_0$ is set to 1 to capture any quadratic polynomial in $\textbf{m}$ variables. This is because a quadratic polynomial may contain low-degree monomials, i.e., degree-1 and degree-0 monomials.

Observe that if $a_0$ is not set to 1 and is considered as an addition variable, then it becomes a quadratic polynomial in $\mathbf{m+1}$ variables. Also, there won't be a degree-0 monomial in the equation, thus not capturing a general quadratic equation.

Now, consider the following polynomials.

$$\sum_{i=0}^m a_i u_{i} \cdot \sum_{i=0}^{m} a_i v_i = \sum_{i=0}^m a_i w_i$$ $$\sum_{i=0}^m b_i u_{i} \cdot \sum_{i=0}^{m} b_i v_i = \sum_{i=0}^m b_i w_i$$

where in the first polynomial we restrict that $a_0 = 1$, i.e., it is a polynomial in $m$ variables whereas the second one is in $m+1$ variables. Clearly, a solution $(d_1, \dots, d_m)$ for the first equation implies $(1, d_1 \dots, d_m)$ is a solution to the second. Whereas a solution $(e_0, e_1, \dots, e_m)$ to the second equation can be used to build a solution to the first equation only when $e_0 \neq 0$. In other words, solving the first equation is harder than solving the second one. Hence, revealing $a_0 = 1$ does not make it easier!

$\endgroup$

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.