1
$\begingroup$

The BGW protocol gives us security aginst a dishonest minority of parties, with round complexity linear in the function's circuit depth. Several works (like ABT18 or LLW20) use the BGW protocol to get 2-round MPC by reducing the functions degree to 2.

However, I don't see how BGW gives us a 2-round protocol. You need one round to share the inputs, one round for the multiplications and one final round to reconstruct the result, resulting in a 3-round protocol. What am I missing here? How can the multiplication round be merged into the input sharing or the reconstruction round?

$\endgroup$

1 Answer 1

0
$\begingroup$

Well, I've thought about it a while back and figured it out.
You have the input sharing round and the reconstruction round. Every round beyond that is used for degree-reduction of the secret sharing. Since the Shamir Secret Sharing in this context (honest majority) supports up to one non-interactive multiplication, you don't need to perform a degree reduction for the last multiplication.
For example, a degree 2 function is computed in two rounds:

  1. An input sharing round.
  2. Non-interactive multiplication of the shares to compute the degree-2 function.
  3. A reconstruction round.

A degree-3 function would require an additional degree-reduction round after step 2 - totalling 3 rounds.

$\endgroup$

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.