Paper 2020/162

A Secret-Sharing Based MPC Protocol for Boolean Circuits with Good Amortized Complexity

Ignacio Cascudo and Jaron Skovsted Gundersen

Abstract

We present a new secure multiparty computation protocol that allows for evaluating a number of instances of a boolean circuit in parallel, with a small online communication complexity per instance of $10$ bits per party and multiplication gate. Our protocol is secure against an active adversary corrupting a dishonest majority. The protocol uses an approach introduced recently in the setting of honest majority and information-theoretically security, based on the algebraic notion known as reverse multiplication friendly embeddings, which essentially transforms a batch of evaluations of an arithmetic circuit over a small field into one evaluation of another arithmetic circuit over a larger field. To obtain security against a dishonest majority, we combine this approach with the well-known SPDZ protocol that provides security against a dishonest majority but operates over a large field. As SPDZ and its variants, our protocol operates in the preprocessing model. Structurally our protocol is most similar to MiniMAC, a protocol which bases its security on the use of error-correcting codes, but our protocol has a communication complexity which is half of that of MiniMAC when the best available binary codes are used. With respect to certain variant of MiniMAC that utilizes codes over larger fields, our communication complexity is slightly worse; however, that variant of MiniMAC needs a much larger preprocessing than ours. We also show that our protocol also has smaller amortized communication complexity than Committed MPC, a protocol for general fields based on homomorphic commitments, if we use the best available constructions for those commitments. Finally, we construct a preprocessing phase from oblivious transfer based on ideas from MASCOT and Committed MPC.