Paper 2019/207

MArBled Circuits: Mixing Arithmetic and Boolean Circuits with Active Security

Dragos Rotaru and Tim Wood

Abstract

Most modern actively-secure multiparty computation (MPC) protocols involve generating random data that is secret-shared and authenticated, and using it to evaluate arithmetic or Boolean circuits in different ways. In this work we present a generic method for converting authenticated secret-shared data between different fields, and show how to use it to evaluate so-called ``mixed'' circuits with active security and in the full-threshold setting. A mixed circuit is one in which parties switch between different subprotocols dynamically as computation proceeds, the idea being that some protocols are more efficient for evaluating arithmetic circuits, and others for Boolean circuits. One use case of our switching mechanism is for converting between secret-sharing-based MPC and garbled circuits (GCs). The former is more suited to the evaluation of arithmetic circuits and can easily be used to emulate arithmetic over the integers, whereas the latter is better for Boolean circuits and has constant round complexity. Much work already exists in the two-party semi-honest setting, but the $n$-party dishonest majority case was hitherto neglected. We call the actively-secure mixed arithmetic/Boolean circuit a marbled circuit. Our implementation showed that mixing protocols in this way allows us to evaluate a linear Support Vector Machine with $400$ times fewer AND gates than a solution using GC alone albeit with twice the preprocessing required using only SPDZ (Damgård et al., CRYPTO '12), and thus our solution offers a tradeoff between online and preprocessing complexity. When evaluating over a WAN network, our online phase is $10$ times faster than the plain SPDZ protocol.

Note: Added full version