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$
$\endgroup$
-
$\begingroup$ This looks like homework, what have you tried? where are you stuck? $\endgroup$ – Meir Maor Nov 29 '18 at 12:44
$\begingroup$
$\endgroup$
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 $
$\begingroup$
$\endgroup$
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$.
-
1$\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$ – Changyu Dong Nov 29 '18 at 16:46
-
$\begingroup$ That's right. Do you know another way to do it, without leaking data ? $\endgroup$ – David Barishev Nov 30 '18 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$ – Changyu Dong Nov 30 '18 at 11:54
-
$\begingroup$
$\endgroup$
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
