# How many parties are needed to compute multiplication with BGW?

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.

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

## 1 Answer

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.

• 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? – macco Nov 11 '19 at 19:07
• 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. – Yehuda Lindell Nov 11 '19 at 19:53