# Algorithm for binary less than in MPC

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)?

• This looks like homework, what have you tried? where are you stuck? Nov 29 '18 at 12:44

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$$.

• But then you leak some information about $a$ and $b$, e.g. $a-b$ which you don't know before running the protocol. Nov 29 '18 at 16:46
• That's right. Do you know another way to do it, without leaking data ? Nov 30 '18 at 11:20
• 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. Nov 30 '18 at 11:54
• in a finite field $+r$ might cause an overflow
– ngn
Dec 4 '18 at 16:36