Let's say we have 3 parties and each one of them has a different secret number. Every party wants to learn the product of all the 3 numbers without learning about the other inputs.

With the BGW protocol: Can we do this with 3 parties, or do we need 5 parties to do this? I am confused because BGW states that we need $2t+1$ parties to reconstruct the solution, which would be 5.

  • $\begingroup$ t is the degree of the polynomial that they select. Thus for 3 parties t = 2. Thus 2t+1=5 $\endgroup$ – macco Nov 11 '19 at 17:15

The BGW protocol has a semi-honest and a malicious version. For semi-honest, a simple honest majority is enough. In that case, 3 parties can run the protocol, with security against one (semi-honest) corrupted party. For malicious adversaries, BGW requires $t < n/3$ meaning that with one corrupted party, you need at least 4 parties; with up to two corrupted parties, you need at least 7 parties.

| improve this answer | |
  • $\begingroup$ Assuming that there are no corrupted parties, can 3 parties all choose a polynomial of degree 2, so that all 3 parties are needed to reconstruct the solution? Or must they use a polynomial of degree 1, such that any 2 parties can reconstruct the solution? $\endgroup$ – macco Nov 11 '19 at 19:07
  • 1
    $\begingroup$ If there are no corrupted parties then you don't need MPC. Send the inputs to one party and let them just compute the result. $\endgroup$ – Yehuda Lindell Nov 11 '19 at 19:53

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.