1
$\begingroup$

I am trying to convert a basic program into an arithmetic circuit. I am stuck on the step of converting the greater than operator into an arithmetic circuit. To be specific, I do not know how to convert the following into an arithmetic circuit (where x,y is input):

if x >= y: return 1 else: return 0

To be clear, I need to be able to express this in terms of an ARITHMETIC circuit. Meaning that I need to be able to compute this using only addition and multiplication of numbers (in Z_p).

I've been searching all of the web for solutions, but everything I find tells me how to do this with boolean circuits. I am aware that I can convert the numbers into their bit string and do this boolean way. I would like to know of any alternative way to do this. This show be possible to do with just addition and multiplication, but I cannot figure out how to.

For context, I'm considering this in the case of Multi-Party Computation. Therefore, taking advantage of how I represent my number (i.e. two's complement) will not work because my number will be split into secret shares.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
2
$\begingroup$

I believe this is generally done in MPC by converting the sharing of the field element to some sharing more amenable to comparison. See this (section 6.3), or chapter 9 in Secure Multiparty Computation and Secret Sharing by Cramer et al.

Generically, comparisons are dependent on how you represent values in $\mathbb{F}_p$. For example, in $\mathbb{F}_3$ you might want to say that $1 \leq 2$, but since $-1$ is in the same equivalence class as $1$ any polynomial that computes this (for $\mathbb{F}_3\cong \{0,1,2\}$) would also compute $1 \leq -1$ (for $\mathbb{F}_3\cong\{-1,0,1\}$). You could of course use Lagrange Interpolation to get any polynomial to have arbitrary values, but it'd be difficult to call that polynomial "the comparison polynomial", and your model of arithmetic circuits would have to be with respect to a specific representation of field elements (which sounds non-standard, but I'm no expert).

The book by Cramer et al has some commentary on how comparisons using solely $\mathbb{F}_p$ arithmetic leads to large circuits, so maybe there is actually some "comparison polynomial" (and m preceding paragraph is wrong), but it appears the standard thing to do still is to convert to an easier representation to do comparisons on for efficiency.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks! This was helpful. I also found this link: faui1-files.cs.fau.de/filepool/publications/octavian_securescm/… $\endgroup$
    – user53169
    Jun 26, 2019 at 14:47
  • $\begingroup$ It's worth mentioning that equality checking can be done via arithmetic circuits, although the corresponding polynomial is high degree. Fermat's little theorem states that $a^p\equiv a\mod p$, so for $a$ invertible (so non-zero) in your finite field you have that $a^{p-1}\equiv 1$. Clearly, $0^{p-1}\equiv 0\mod p$, so the function $x\mapsto x^{p-1}$ allows you to check equality against zero in $\mathbb{F}_p$. This generalizes to other finite fields (see this page). $\endgroup$
    – Mark
    Jun 26, 2019 at 21:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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