Algorithm for binary less than in MPC

Question

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

Answer 1

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 $

Answer 2

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

Answer 3

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