1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.