Cryptology ePrint Archive: Report 2017/1186

On Multiparty Garbling of Arithmetic Circuits

Aner Ben-Efraim

Abstract: We initiate a study of garbled circuits that contain both Boolean and arithmetic gates in secure multiparty computation. In particular, we incorporate the garbling gadgets for arithmetic circuits recently presented by Ball, Malkin, and Rosulek (ACM CCS 2016) into the multiparty garbling paradigm initially introduced by Beaver, Micali, and Rogaway (STOC '90). This is the first work that studies arithmetic garbled circuits in the multiparty setting. Our garbled circuits are secure in the semi-honest model, under the same hardness assumptions as Ball et al., and can be efficiently and securely computed in constant rounds assuming an honest majority.

We first extend free addition and multiplication by a constant to the multiparty setting. We further extend to the multiparty setting efficient garbled multiplication gates. The garbled multiplication gate construction we show was previously achieved only in the two-party setting and assuming a random oracle.

Our main technical contribution is in garbling selector gates. Selector gates compute a simple ``if statement" in the arithmetic setting: the gate selects the output value from two input values in $\mathbb{F}_p$, according to a Boolean selector bit; if the bit is $0$ the output equals the value on the first wire, and if the bit is $1$ the output equals the value on the second wire. We show a new and designated garbled selector gate that reduces by approximately $33\%$ the evaluation time from the best previously known constructions that use existing techniques.

On the downside, we find that testing equality and computing exponentiation by a constant are significantly more complex to garble in the multiparty setting than in the two-party setting.

Category / Keywords: Arithmetic Garbled Circuits, Constant Round MPC, Multiparty Garbling

Date: received 6 Dec 2017, last revised 10 Dec 2017

Contact author: anermosh at post bgu ac il

Available format(s): PDF | BibTeX Citation

Version: 20171212:141635 (All versions of this report)

Short URL: ia.cr/2017/1186

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]