Cryptology ePrint Archive: Report 2019/207

MArBled Circuits: Mixing Arithmetic and Boolean Circuits with Active Security

Dragos Rotaru and Tim Wood

Abstract: There are two main ways of performing computation on private data: one method uses linear secret-sharing, in which additions require no communication and multiplications require two secrets to be broadcast; the other method is known as circuit garbling, in which a circuit is somehow randomised by one set of parties and then evaluated by another. There are different advantages and disadvantages to each method in terms of communication and computation complexity. The main disadvantage of secret-sharing-based computation is that many non-linear operations require many rounds of communication. On the other hand, garbled circuit (GC) solutions require only constant rounds. Mixed protocols aim to leverage the advantages of both methods by switching between the two dynamically.

In this work we present the first mixed protocol secure in the presence of a dishonest majority for any number of parties and an active adversary. We call the resulting mixed arithmetic/Boolean circuit a marbled circuit 3 . 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 (Damgaard et al., CRYPTO 12). When evaluating over a WAN network, our online phase is 10 times faster than the plain SPDZ protocol.

Category / Keywords: cryptographic protocols / MPC, Garbled Circuits, Secret Sharing

Date: received 22 Feb 2019

Contact author: dragos rotaru at esat kuleuven be,t wood@kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20190227:025737 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]