Paper 2017/1004

Garbled Protocols and Two-Round MPC from Bilinear Maps

Sanjam Garg and Akshayaram Srinivasan


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].

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

Available format(s)
Publication info
Published elsewhere. MAJOR revision.FOCS 2017
Contact author(s)
akshayaram @ berkeley edu
2017-12-02: revised
2017-10-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sanjam Garg and Akshayaram Srinivasan},
      title = {Garbled Protocols and Two-Round MPC from Bilinear Maps},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1004},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.