<p>I believe this is generally done in MPC by converting the sharing of the field element to some sharing more amenable to comparison. See <a href="https://eprint.iacr.org/2016/969" rel="nofollow noreferrer">this</a> (section 6.3), or chapter 9 in <em>Secure Multiparty Computation and Secret Sharing</em> by Cramer et al.</p>

<p>Generically, comparisons are dependent on how you represent values in <span class="math-container">$\mathbb{F}_p$</span>. For example, in <span class="math-container">$\mathbb{F}_3$</span> you might want to say that <span class="math-container">$1 \leq 2$</span>, but since <span class="math-container">$-1$</span> is in the same equivalence class as <span class="math-container">$1$</span> any polynomial that computes this (for <span class="math-container">$\mathbb{F}_3\cong \{0,1,2\}$</span>) would also compute <span class="math-container">$1 \leq -1$</span> (for <span class="math-container">$\mathbb{F}_3\cong\{-1,0,1\}$</span>). 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).</p>

<p>The book by Cramer et al has some commentary on how comparisons using solely <span class="math-container">$\mathbb{F}_p$</span> 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.</p>

CC BY-SA 4.0
2019-06-26T14:47:28.757Z
Thanks! This was helpful. I also found this link: https://faui1-files.cs.fau.de/filepool/publications/octavian_securescm/smcint-scn10.pdf
user53169
CC BY-SA 4.0
2019-06-26T21:56:20.667Z
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](https://en.wikipedia.org/wiki/Frobenius_endomorphism#Fixed_points_of_the_Frobenius_endomorphism)).
Mark Schultz-Wu
CC BY-SA 4.0
2019-06-26T04:21:29.493Z
2019-06-26T04:21:29.493Z
Mark Schultz-Wu
<p>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):</p>

<p><code>if x &gt;= y:
    return 1
else:
    return 0</code></p>

<p>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).</p>

<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.</p>

<p>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.</p>

CC BY-SA 4.0
2019-06-27T16:40:22.703Z
Possibly useful: https://crypto.stackexchange.com/q/54007/351, https://crypto.stackexchange.com/q/59441/351, https://crypto.stackexchange.com/q/46885/351, https://crypto.stackexchange.com/q/42019/351, https://crypto.stackexchange.com/q/60154/351
D.W.
<cc.complexity-theory><lo.logic><arithmetic-circuits><circuits>
How to build comparison operator (comparator) in an arithmetic circuit
user53169
# How to build comparison operator (comparator) in an arithmetic circuit

(Asked by: username_0 on 2019-06-25)

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.

**Tags:** cc.complexity-theory, lo.logic, arithmetic-circuits, circuits

> **Comments:**
> **username_1**: Possibly useful: https://crypto.stackexchange.com/q/54007/351, https://crypto.stackexchange.com/q/59441/351, https://crypto.stackexchange.com/q/46885/351, https://crypto.stackexchange.com/q/42019/351, https://crypto.stackexchange.com/q/60154/351  

---

## 1 answers

### Answer by username_2 on 2019-06-26. Score: 2

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](https://eprint.iacr.org/2016/969) (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.

> **Comments:**
> **username_0**: Thanks! This was helpful. I also found this link: https://faui1-files.cs.fau.de/filepool/publications/octavian_securescm/smcint-scn10.pdf  
> **username_2**: 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](https://en.wikipedia.org/wiki/Frobenius_endomorphism#Fixed_points_of_the_Frobenius_endomorphism)).  

---

