Low Cost Constant Round MPC Combining BMR and Oblivious Transfer
- PDF / 4,433,298 Bytes
- 55 Pages / 439.37 x 666.142 pts Page_size
- 87 Downloads / 199 Views
Low Cost Constant Round MPC Combining BMR and Oblivious Transfer Carmit Hazay Bar-Ilan University, Ramat Gan, Israel [email protected]
Peter Scholl · Eduardo Soria-Vazquez Aarhus University, Aarhus, Denmark [email protected] [email protected] Communicated by Jonathan Katz Received 2 December 2017 / Revised 13 April 2020
Abstract. In this work, we present two new actively secure, constant-round multiparty 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 F2 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 experiments 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. Keywords. MPC, BMR, Constant rounds, Concrete efficiency.
© International Association for Cryptologic Research 2020
C. Hazay et al.
1. Introduction Secure multi-party computation (MPC) protocols allow a group of n parties to compute some function f on the parties’ private inputs, whilst preserving a number of security properties such as privacy and correctness. The former property implies data confidentiality; namely, nothing leaks from the protocol execution but the computed output. The latter requirement implies that the protocol enforces the integrity of the computations made by the parties; namely, honest parties learn the correct output. Modern, practical MPC protocols typically fall into two main categories: those based on secret sharing [10,18,20,26,28,41], and those based on garbled circuits [9,15,31–34,38,46]. When it comes to choosing a protocol, many different factors need to be taken into account, such as the function being evaluated, the latency and bandwidth of the network and the adversary model. Secret-sharing-based protocols tend to have lower communication requirements in terms of bandwidth, but require a large number of rounds of communication, which increases with the circuit depth of the function. In this approach, the parties first secretshare their inputs and then evaluate the circuit gate by gat
Data Loading...
