Paper 2017/214

Low Cost Constant Round MPC Combining BMR and Oblivious Transfer

Carmit Hazay and Peter Scholl and Eduardo Soria-Vazquez

Abstract

In this work, we present a new universally composable, actively secure, constant round multi-party protocol for generating BMR garbled circuits with free-XOR and reduced costs. Specifically, the cost of garbling an AND gate is essentially the same as securely evaluating one AND gate using any non-constant-round, GMW-style multi-party computation (MPC) protocol, with a small additive communication overhead that is linear in the security parameter. We further introduce a second realization of the preprocessing phase that is less generic but more efficient, by building on optimized multi-party `TinyOT'-style protocols based on information-theoretic message authentication codes. An interesting consequence of our work is that, with current techniques, constant round MPC for binary circuits is not much more expensive than practical, non-constant round protocols. We estimate that the concrete communication cost of our preprocessing protocol improves upon previous works by up to three orders of magnitude, and with low computational complexity. We also improve asymptotically by reducing the overall communication complexity from $O(n^3)$ to $O(n^2)$, and our construction is even highly competitive in the two-party setting.

Note: Updated complexity analysis.