4
$\begingroup$

My secure multi-party computation (MPC) in need is simply to determine if a sum of two private variable is bigger than a given value $y$, as

$f(x_0, x_1) = [(x_0 + x_1) > y]$

in which the value of sum itself (i.e., $x_0+x_1$) is deemed private and $y$ is publicly known. The output of this function is yes or no.

I am aware of many MPC protocols out there, mostly based on boolean circuit (as in Yao's protocol) or arithmetic circuit. But I have no experiences of benchmarking these protocols, and I want to ask which (existing) protocols are more suitable for my computation?

Update: based on the answer from @mikeazo, arithmetic circuit is good at addition and boolean at comparison. Since my function $f(\cdot)$ involves with both, so the question is really which out of these two circuits can do both (comparison and addition) better?

Update2: I am also thinking if possible to decompose $f(\cdot)$ into separate parts, one for comparison and one for addition. And use different/corresponding circuits for each part. Is it such adaptive framework out there that can do this?... maybe this way, it can be even more efficient.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ Can you describe in more detail who performs the computation and who needs to learn the output? Also, how many parties should be involved, just 2? How large are the inputs (32 bit, 64 bit, 2000 bits)? $\endgroup$
    – mikeazo
    Jun 10, 2013 at 13:37
  • $\begingroup$ OP is for $2$ parties: values $x_0$ and $x_1$ are for each party, respectively. Generally, $2$ parties are OK but more than $2$, say $10$'s are possible in my case (but not rigidly). Input size is unspecified in my problem yet... but how does it matter in this problem? I want to know... $\endgroup$
    – Richard
    Jun 10, 2013 at 18:22
  • 1
    $\begingroup$ @Richard, yes, the input size is likely to matter (at least if you use a boolean circuit). $\endgroup$
    – D.W.
    Jun 10, 2013 at 18:45
  • $\begingroup$ If input size is needed, I would start from the small, say 32 bits. $\endgroup$
    – Richard
    Jun 11, 2013 at 3:33
  • 4
    $\begingroup$ I would like to point out that this problem is equivalent to a joint computation of $x_0 > y - x_1$, hence it is the millionaire problem; the most efficient solution for that problem will be the most efficient solution for this. $\endgroup$
    – poncho
    Jun 11, 2013 at 16:22

1 Answer 1

Reset to default
5
$\begingroup$

The answer is definitely yes. You should be able to do what you are looking for. The computation is very simplistic, so using existing MPC protocols will be efficient. Many of the existing protocols are able to evaluate a few blocks of AES using MPC per second, so this computation will be no problem.

Typically MPC works by translating your function into a circuit (either boolean or arithmetic). In the 2 party case, you are probably best off using Yao's approach. There are newer constructions that you could use and that would probably still be efficient, but they do use some heavy public key crypto and I'm not aware of any publicly available implementations. For Yao's approach, I'd recommend the MightBeEvil framework. I believe Yao's approach is most commonly (if not always) used with boolean circuits. Another option is Fairplay.

In the multi-party case (more than 2 parties), garbled circuits won't do (at least not with publicly available implementations). Your options here are really Viff and Fairplay-MP. Viff uses arithmetic circuit representations while Fairplay-MP uses boolean circuits. Viff has a specialized protocol from Toft for comparison to help mitigate some of the problems with comparison in arithmetic circuits (more on this in a moment).

Adversary Model
You don't mention adversary model in your post, but I thought I'd say a little on this. You have 3 choices in the literature: semi-honest (or honest-but-curious), covert, and malicious (or Byzantine). Fairplay, Fairplay-MP, and MightBeEvil all only support semi-honest adversaries while Viff has support for both. Theoretically any of Fairplay, Fairplay-MP and MightBeEvil could be made to support malicious adversaries, but they don't out of the box and would require significant work (not to mention publishing to make sure you didn't make any mistakes).

If you are not familiar with the difference, semi-honest assumes that corrupt parties will follow the protocol as specified and only use information gleaned during the execution to violate privacy. Malicious makes none of these assumptions (parties can deviate all they want from the protocol and will always be caught, caught with overwhelming probability). I am not aware of any implementations available publicly that support covert adversaries. FYI, a covert adversary is one who will deviate but doesn't want to be caught, so you only have to define the protocol such that the probability of catching a deviating adversary is high (as opposed to overwhelming).

Boolean vs Arithmetic
Both approaches have their strengths and weaknesses. In arithmetic circuits, addition is cheap but comparison is much more expensive. The opposite is true in boolean circuits. I believe that, for example, in the MightBeEvil framework, they have built in circuits for say a 32 bit adder but not a 2000 bit adder. Thus, input size will make a difference here. On the arithmetic side, you only have to define the underlying field large enough to support the input size. This will have an effect on performance, but not as large as in the boolean circuit approach.

Comparison in boolean circuits is relatively easy. Simply start with most significant bits and compare the bits using a single bit comparison operation. Scan from MSb to LSb, stopping when a difference is found. Whoever has the 1 bit in this case is the larger of the two. On the arithmetic side, things are more complicated which is why Viff uses a specialized protocol from Toft. For small input sizes, it probably won't make a huge difference.

Improve this answer
$\endgroup$
6
  • $\begingroup$ That's a great review!. one question though: since my function involves with both addition and comparison, kinda fall in btwn what arithmetic and boolean circuit excels in. so the question is really who can do both better?.. I will update the OP in a moment and will look into Viff (looks like its adapt btwn circuit and arithmetic based on computation)... interesting. $\endgroup$
    – Richard
    Jun 11, 2013 at 14:52
  • $\begingroup$ Not sure. For such a simple function, it probably doesn't matter much. Remember with Viff you will need at least 3 parties (4 for the malicious protocol). They don't all have to have inputs though. $\endgroup$
    – mikeazo
    Jun 11, 2013 at 20:53
  • $\begingroup$ Function is simple, but number of evaluation is potentially big, like run the inputs thousand time, so a little perf. improvement for single evaluation matters to the application... correct me if wrong. $\endgroup$
    – Richard
    Jun 12, 2013 at 11:59
  • $\begingroup$ In that case, I'd test the two methods and see which works best. One question, would you be able to run the function on thousands of inputs in parallel? I came across this recently, don't know all the details yet, and don't believe there are any public implementations, but there is a way to run MPC in a SIMD (single instruction, multiple data) fashion. See section 8.4 of Damgard's book. $\endgroup$
    – mikeazo
    Jun 12, 2013 at 12:09
  • $\begingroup$ packed ss is very interesting! My system should be able to run it in parallel. my concerns are really how hard (or how much effort) I should put to incorporate that into existing MPC platform, like FairplayMP. $\endgroup$
    – Richard
    Jun 12, 2013 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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