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?


1 Answer 1


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$ Commented 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$ Commented Mar 9, 2019 at 17:41
  • $\begingroup$ Yes exactly! That's it $\endgroup$
    – Daniel
    Commented Mar 11, 2019 at 13:50
  • $\begingroup$ At the end of page34, could you explain how they got the matrix b = Qa + p ? $\endgroup$ Commented Mar 11, 2019 at 18:11

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.