Paper 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.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint. MINOR revision.
- Keywords
- MPCGarbled CircuitsSecret Sharing
- Contact author(s)
- dragos rotaru @ esat kuleuven be,t wood @ kuleuven be
- History
- 2019-10-16: revised
- 2019-02-27: received
- See all versions
- Short URL
- https://ia.cr/2019/207
- License
-
CC BY