Low cost constant round MPC combining BMR and oblivious transfer

Abstract

In this work, we present two new actively secure, constant round multi-party computation (MPC) protocols with security against all-but-one corruptions. Our protocols both start with an actively secure MPC protocol, which may have linear round complexity in the depth of the circuit, and compile it into a constant round protocol based on garbled circuits, with very low overhead.

1. Our first protocol takes a generic approach using any secret-sharing-based MPC protocol for binary circuits, and a correlated oblivious transfer functionality.
2. Our second protocol builds on secret-sharing-based MPC with information-theoretic MACs. This approach is less flexible, being based on a specific form of MPC, but requires no additional oblivious transfers to compute the garbled circuit.

In both approaches, the underlying secret-sharing-based protocol is only used for one actively secure $F_2$ multiplication per AND gate. An interesting consequence of this is that, with current techniques,constant round MPC for binary circuits is not much more expensive than practical, non-constant round protocols.

We demonstrate the practicality of our second protocol with an implementation, and perform ex-periments with up to 9 parties securely computing the AES and SHA-256 circuits. Our running times improve upon the best possible performance with previous protocols in this setting by 60 times.

This is the Journal version of the Asiacrypt 2017 paper with the same name.