Cryptology ePrint Archive: Report 2017/1004

Garbled Protocols and Two-Round MPC from Bilinear Maps

Sanjam Garg and Akshayaram Srinivasan

Abstract: In this paper, we initiate the study of \emph{garbled protocols} --- a generalization of Yao's garbled circuits construction to distributed protocols. More specifically, in a garbled protocol construction, each party can independently generate a garbled protocol component along with pairs of input labels. Additionally, it generates an encoding of its input. The evaluation procedure takes as input the set of all garbled protocol components and the labels corresponding to the input encodings of all parties and outputs the entire transcript of the distributed protocol.

We provide constructions for garbling arbitrary protocols based on standard computational assumptions on bilinear maps (in the common random/reference string model). Next, using garbled protocols we obtain a general compiler that compresses any arbitrary round multiparty secure computation protocol into a two-round UC secure protocol. Previously, two-round multiparty secure computation protocols were only known assuming witness encryption or learning-with errors. Benefiting from our generic approach we also obtain two-round protocols (i) for the setting of random access machines (RAM programs) while keeping the (amortized) communication and computational costs proportional to running times, (ii) making only a black-box use of the underlying group, eliminating the need for any expensive non-black-box group operations and (iii) satisfying semi-honest security in the plain model.

Our results are obtained by a simple but powerful extension of the non-interactive zero-knowledge proof system of Groth, Ostrovsky and Sahai [Journal of ACM, 2012].

Category / Keywords: foundations /

Original Publication (with major differences): FOCS 2017

Date: received 9 Oct 2017, last revised 1 Dec 2017

Contact author: akshayaram at berkeley edu

Available format(s): PDF | BibTeX Citation

Note: This version fixes a claim that was previously made for the case of black-box protocols.

Version: 20171202:050218 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]