5
$\begingroup$

Typically MPC protocols that are secure against semi-honest adversaries recommend the use of the revised GMW multiplication protocol by Gennaro et al. This is not the case against Active adversaries where protocols of the likes of SPDZ, VIFF and Oralndi prefer the use of the well known Beaver's multiplication triple.

My question is the following:

Given that I could use for instance VSS to provide security against active adversaries in the case of Shamir for instance, why is Beavers triple the preferred method. Is it because the randomized factors $(a,b,c)$ can be computed before hand (offline) and hence I would have a faster multiplication protocol given that stuff like PRSS is available under this security model?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I would like to add to the discussion, that the only reason I see Gennaro multiplication would not be a natural fit on some schemes, is that is quite tied to Shamir. The goal is to reduce the degree of the resulting polynomial. In other words, the only way to make it work would be to have an honest majority. $\endgroup$
    – DaWNFoRCe
    Commented Apr 15, 2016 at 12:23
  • $\begingroup$ you need more than an honest majority in the active case. You need more than two-thirds to be honest. $\endgroup$
    – mikeazo
    Commented Apr 15, 2016 at 13:39
  • $\begingroup$ @mikeazo you are right. Moreover active protocols that rely on a broadcast channel (this is specially useful outside the information theoretic model) can use beavers construction to avoid peer-to-peer information exchange in between parties. Using the broadcast channel to open the shares. If this is not the case and Gennaro is used instead, each computational party would have to be a "trusted dealer", requiring stronger cryptographic constructions to guarantee this. $\endgroup$
    – DaWNFoRCe
    Commented Apr 18, 2016 at 14:04
  • $\begingroup$ @Mikeazo In conclusion, is there any other reason to prefer Beaver over BGW-Gennaro multiplication scheme than to eliminate the point-to-point assumption and to have dishonest majority? I was thinking malleability when resharing the local shared product [x] *[y], but if I remember correctly they also address the issue right? $\endgroup$
    – DaWNFoRCe
    Commented Apr 26, 2016 at 17:14

1 Answer 1

Reset to default
11
$\begingroup$

Yes, preprocessing Beaver triples in an offline phase leads to a faster online phase. The online phase of an AND gate requires just two openings plus local computations.

But there are other advantages as well. Define a "linear representation" $[x]$ to be any way of representing/distributing a value $x$ among parties such that the following properties hold:

  1. The adversary's view of $[x]$ is independent of $x$.

  2. Given $[x]$ and $[y]$, it is possible to compute $[x+y]$ via local computations only.

  3. Given $[x]$ and $c$, it is possible to compute $[cx]$ via local computations only.

  4. There is a protocol that opens $[x]$ to reveal $x$, even in the presence of an adversary (can be formulated for any adversarial model).

For example, Shamir secret shares are one possible linear representation, secure against semi-honest adversaries.

If you assume a setup phase in which parties obtain many Beaver triples $[x],[y],[xy]$ on random inputs, as well as many random $[r]$, then you can do MPC in a very straight-forward way.

This recipe for making an MPC protocol is appealing because you just have to define an appropriate linear representation and plug in. This is what SPDZ, MiniMAC, BDOZ, etc., do (plus other optimizations of course).

In particular, these protocols use a linear representation that is secure against a dishonest majority. If you use computational assumptions during the offline phase, then you can in fact generate such Beaver triples. If you just stick to the VSS paradigm then you cannot get security against dishonest majority.

For a good presentation of this MPC paradigm (abstract linear representations + pre-processed Beaver triples), I recommend the video lectures of Claudio Orlandi & Ivan Damgaard from the 2015 Bar-Ilan winter school.

Improve this answer
$\endgroup$
6
  • $\begingroup$ thanks so much for your answer. I would think you would need 2 reconstructions to have a multiplication gate isn't it? If that is the case and I have an honest majority and I'm using either some features of SPDZ or VSS to provide active security. Why would I use Beaver instead of Gennaro then? Gennaro only needs 1 communicational round right? P.S. Now it is clear to me why SDPZ, MiniMAC and all their successors use it.. Thanks so much it was a really nice explanation! $\endgroup$
    – DaWNFoRCe
    Commented Apr 14, 2016 at 16:46
  • $\begingroup$ You're right, it's 2 openings in the online phase -- I've updated accordingly. $\endgroup$
    – Mikero
    Commented Apr 14, 2016 at 19:33
  • $\begingroup$ Good to know! :). Any thoughts on the questions btw? $\endgroup$
    – DaWNFoRCe
    Commented Apr 15, 2016 at 10:00
  • $\begingroup$ Another short question, what would be the difference between the VSS paradigm and what modern active protocols do? $\endgroup$
    – DaWNFoRCe
    Commented Apr 15, 2016 at 12:24
  • 1
    $\begingroup$ The VSS constructions I know about (which are just the basic ones) have $O(n)$ overhead. What that means is that each party's VSS share is $O(n)$ size where $n$ is the total number of parties. In SPDZ for instance each party's share is constant-sized. $\endgroup$
    – Mikero
    Commented Apr 15, 2016 at 19:22

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.