5
$\begingroup$

There exist protocols for 2-party computation e.g., GMW that use Boolean circuits. I could also use Paillier and arithmetic circuits for a 2 party computation. However after reading about SPDZ is my understanding I could use it to do 2-party computation. Is my understanding correct? Besides the fact that I would have to generate tons of triples, is there any other drawback of using SPDZ for 2-PC? If this is the case why is not widely use for the 2-party case? Should I favor a 3 party setting instead of a 2 party one when using SPDZ?

$\endgroup$
  • $\begingroup$ I think the reason SPDZ is "not widely used for the 2-party case" is that no secure computation protocol is widely used in any case. The technology is still mainly used in theoretical constructions and prototypes. $\endgroup$ – Guut Boy Oct 6 '16 at 8:50
7
$\begingroup$

Your understanding is correct. The SPDZ protocol can be used for any number of two or more parties. In fact, this is one of the strengths of the SPDZ protocol. Namely, many recent secure computation protocols such as the various versions of the Yao protocol or the TinyOT protocol are limited to two parties. So it may sometimes be overemphasized that SPDZ goes beyond two parties.

There is no drawback to using SPDZ with just two parties compared to three parties. Certain aspects such as the required broadcast actually becomes simpler in the two party case. So you should never try to add additional parties beyond what you need, it will only make you application less efficient.

However, there are many trade-offs to consider when choosing a secure computation protocol. Therefore, there could be good reasons to pick an other protocol than SPDZ in a two party setting. For example, SPDZ is based on arithmetic operations. If your application is heavy on Boolean operations, other protocols such as TinyOT which is based on Boolean operations may perform better. Also, SPDZ has round complexity proportional to the depth of the circuit you are evaluating. Yao has constant round complexity for any circuit. So if you are in a high latency setting or evaluating a very deep circuit, Yao may perform better than SPDZ.

$\endgroup$
  • $\begingroup$ Note that Yao outperforms all other approaches for malicious adversaries and Boolean circuits even for fast networks. $\endgroup$ – Yehuda Lindell Oct 6 '16 at 9:33
  • $\begingroup$ As far as I know it has gone back and forth between various protocols. But certainly Yao seems to get a lot more attention than alternatives, so it would not surprise me if this is indeed the fastest currently. As I understand it also depends a lot on the strength of the implementation. I.e., software engineering rather than protocols. $\endgroup$ – Guut Boy Oct 6 '16 at 9:41
  • 1
    $\begingroup$ That said, certainly SPDZ would be a bad choice for anything requiring many Boolean operations compared to Yao. @YehudaLindell do you know if Yao also beats SPDZ on arithmetic (or comes close at least)? $\endgroup$ – Guut Boy Oct 6 '16 at 9:45
  • $\begingroup$ For arithmetic, I don't know and I assume that it depends on the exact application. I was referring to Boolean circuits. $\endgroup$ – Yehuda Lindell Oct 6 '16 at 9:47
5
$\begingroup$

my understanding I could use it to do 2-party computation

You are correct, SPDZ can give secure MPC for any number of parties. It is just a matter of generating enough multiplication triples.

Should I favor a 3 party setting instead of a 2 party one when using SPDZ?

Whichever makes sense in your application is fine.

why is not widely use for the 2-party case?

The only reason to prefer something else is round complexity. In the 2-party case specifically you have the extra option of using protocols based on garbled circuits (i.e., Yao's protocol). Yao's protocol is constant-round, while SPDZ & GMW require interaction for each multiplication gate (so the round complexity is proportional to the depth of the circuit).

Note: the BMR protocol is a constant-round variant of Yao for $n > 2$, but it is much less efficient than something like SPDZ.

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