2
$\begingroup$

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.

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

1 Answer 1

Reset to default
4
$\begingroup$

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
$\endgroup$
2
  • $\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
    Commented Nov 11, 2019 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
    Commented Nov 11, 2019 at 19:53

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.