1
$\begingroup$

There are MPC comparison protocols which can securely compute $(a<^?0):=\begin{cases}1,\text{ if }a<0\\ 0,\text{ otherwise}\end{cases}$, where $a$ is an element of a prime-order field (of course one needs a notion of what $"<"$ even means in this case). But to my knowledge, all of them use some kind of bit decomposition protocol which outputs shared bits $[a_0],[a_1],\ldots,[a_k]$ on input $\textstyle \left[\sum^k_{i=0}a_i2^i\right]$. Does anyone know of such a comparison protocol which does not require bit decomposition?

$\endgroup$
2
  • $\begingroup$ Are you interested only in the setting of more than two parties, or are you also looking for solutions in the 2-party setting? $\endgroup$ Mar 12 at 20:46
  • $\begingroup$ I'm curious about both. $\endgroup$ Mar 13 at 21:06

2 Answers 2

2
$\begingroup$

In the two-party setting, there are fast protocols for securely comparing two shared integers that do not go through bit decomposition. For example:

If you want to optimize online communication (but are ok with paying more communication in an input-independent preprocessing phase), then the best approaches rely on function secret sharing, see here and the improvements in here.

If you want low end-to-end communication, then I think this protocol used to be state-of-the-art (disclaimer: I'm the author, and this area evolves, there might be better protocols out there). After a quick Google search, my best bet is that there might be faster protocols (less rounds and communication) in this more recent paper, but I did not read it in full details (I still checked that they don't go through shared bit decomposition).

$\endgroup$
1
  • $\begingroup$ There have been some new results, Professor. For FSS, SIGMA requires 1 eval of DPF for G^{out}={0,1},while the improved one in your answer requires 1 eval of DCF for larger output domain. For the second category, CrypTFlow2 uses a GSV07 style tree structure (KKOT for equa & comp in leaves, OT for bit comp in nodes) and requires logl rounds and comm slightly larger than λl. More recent work like this paper generates ROT with silent OT for better comm. $\endgroup$
    – rzxh
    May 9 at 20:19
0
$\begingroup$

Bit decomposition is sufficient, but not necessary, for comparison. In general, the comparison $a<b$ is equivalent to $0<b-a$, which corresponds to extracting the most significant bit of $x=b-a$. There are many ways of extracting such bit without extracting all of them. See for example:

$\endgroup$
2
  • $\begingroup$ Does this work because the MSB encodes the sign of $b-a$? $\endgroup$ Mar 12 at 19:35
  • $\begingroup$ Yes, correct. The MSB (in two-complement representation) is $1$ if $b-a$ is negative, and $0$ otherwise. $\endgroup$
    – Daniel
    Mar 12 at 21:25

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.