2
$\begingroup$

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

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

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 $

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • 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$ in a finite field $+r$ might cause an overflow $\endgroup$ – ngn Dec 4 '18 at 16:36
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.