Efficient Constant Round Multi-Party Computation Combining BMR and SPDZ

In this blog, we see an efficient constant round MPC that is fully secure in the presence of malicious adversaries and in the dishonest majority (t < n) case. The crux of the construction lies in combining the protocol of BMR with an efficient protocol for evaluating arithmetic circuits which is secure in the presence of malicious adversaries. Before going into the details of the construction, let's analyse the components separately.

The BMR protocol of Beaver et al. is a variant of Yao's protocol that runs in a multi-party setting in dishonest majority setting with security in the presence of semi-honest adversaries. This protocol demands all parties to jointly constructing a garbled circuit, with the help of a constant round MPC and then computing it. For achieving efficiency, BMR uses offline/online paradigm, where garbled circuit construction happens in offline phase and with the exchange of values corresponding to their inputs, parties can evaluate the circuit in the online phase with less amount of communication. However, in the case of malicious adversaries, security is guaranteed only in the case of honest majority (t< n/2) case (For more information, read here). 

In order to facilitate our required constant round MPC, the BMR protocol is modified so that the garbling and evaluation operations are done over a finite field. In detail, instead of using XOR of bit strings, and hence a binary circuit to instantiate the garbled gate, additions of elements in a finite field are used, and hence an arithmetic circuit. This enables us to use an efficient non-constant round protocol - with security for malicious adversaries - to compute the gate tables of the BMR garbled circuit (and since the computation of these tables is of constant depth, this step is constant round). 

In the  general construction, the new constant-round MPC consists of two phases. In the first (offline) phase, the parties securely compute random shares of the BMR garbled circuit. To achieve efficiency, instead of doing naively, each party locally computes the pseudorandom function as needed for every gate and uses the results as input to the secure computation. From the proof of security, we can see that if a party cheats and inputs incorrect values then no harm is done, since it can only cause the honest parties to abort. Next, in the online phase, all that the parties need to do is reconstruct the single garbled circuit, exchange garbled values on the input wires and locally compute the garbled circuit. (For a detailed look, click here)