Given binary shares $[a_{l-1}]_p,...,[a_0]_p, [b_{l-1}]_p,...,[b_0]_p$ such that $a = \sum_{i=0}^{l-1} a_i2^i,b = \sum_{i=0}^{l-1} b_i2^i $ for $a,b \in Z_p$, how to compute $a \overset{?}{\lt} b$ in MPC (the result is not closed)?

  • $\begingroup$ This looks like homework, what have you tried? where are you stuck? $\endgroup$
    – Meir Maor
    Nov 29, 2018 at 12:44

3 Answers 3


find the positions where $a$ and $b$'s bits differ: $c_i=a_i\oplus b_i=a_i+b_i-2a_ib_i$

compute partial or-sums: $d_{l-1}=c_{l-1},\quad d_i=d_{i+1}\vee c_i=a_i+b_i-a_i b_i$

isolate the first differing bit: $e_{l-1}=d_{l-1},\quad e_i=d_i-d_{i+1}$

the result is the corresponding bit in $b$: $\sum e_i b_i $


Here' a good reference on how to achieve that. Unconditionally Secure Constant-Rounds Multi-party Computation for Equality, Comparison, Bits and Exponentiation [pdf is here]. It is mostly the same as the answer by @ngn


I have figured it out.
Since we have the binary shares of $a,b$, a share of their integer value can be computed locally using constant multiplication and sum.
Afterwards a shared random value $r$ can be generated, and $a +r,b+r$ can be also computed.
After opening $a+r,b+r$ the value of the comparison can be calculated locally and without reveling $a,b$.

  • 2
    $\begingroup$ But then you leak some information about $a$ and $b$, e.g. $a-b$ which you don't know before running the protocol. $\endgroup$ Nov 29, 2018 at 16:46
  • $\begingroup$ That's right. Do you know another way to do it, without leaking data ? $\endgroup$ Nov 30, 2018 at 11:20
  • $\begingroup$ What I can recall from memory is a paper in 2010 called "Improved Primitives for Secure Multiparty Integer Computation". You can google it and see whether there are follow-ups from paper citing it. $\endgroup$ Nov 30, 2018 at 11:54
  • $\begingroup$ in a finite field $+r$ might cause an overflow $\endgroup$
    – ngn
    Dec 4, 2018 at 16:36

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.