Given an arithmetic circuit, are there any examples of turning it into a system of bilinear equations, with the end goal of turning it into a matrix?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
4
I don't know if this is exactly what you mean, but you can always consider each one of the wire values in the circuit as variables, and then create an equation per gate which represents the relation that the corresponding wires must have.
For example, if the wires labeled as variables $x$ and $y$ are the inputs of a multiplication gate, whose output is $z$, then you would obtain the equation $x\cdot y - z = 0$. Similarly for addition gates. Overall, you would get a system of $N$ (non-homogeneous) quadratic equations in $n$ variables, where $N$ is the numbers of gates and $n$ is the number of wires.
-
$\begingroup$ Could you also include multiplication by a constant number in the field, and addition? I'm looking for a paper where I saw it was done, but having the hardest time to find it $\endgroup$ Mar 9, 2019 at 17:39
-
$\begingroup$ Found it! P34: eprint.iacr.org/2016/263.pdf But I'm not sure it's the same as what you outlined? $\endgroup$ Mar 9, 2019 at 17:41
-
-
$\begingroup$ At the end of page34, could you explain how they got the matrix b = Qa + p ? $\endgroup$ Mar 11, 2019 at 18:11