You are looking at a specific version 20190227:025737 of this paper. See the latest version.

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)
PDF
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
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.