Cryptology ePrint Archive: Report 2016/1190

Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model

Ran Canetti and Oxana Poburinnaya and Muthuramakrishnan Venkitasubramaniam

Abstract: Yao's garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable two-message, two-party secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds?

We answer this question in the affirmative. We define a new type of encryption, called {\sf functionally equivocal encryption (FEE),} and show that when Yao's scheme is implemented with an FEE as the underlying encryption mechanism, it becomes secure against such adaptive adversaries. We then show how to implement FEE from any one way function.

Combining our scheme with non-committing encryption, we obtain the first two-message, two-party computation protocol, and the first constant-round multiparty computation protocol, in the plain model, that are secure against semi-honest adversaries who can adaptively corrupt all parties. A number of extensions and applications are described within.

Category / Keywords: cryptographic protocols / adaptive security, Yao garbled circuits, secure computation

Date: received 30 Dec 2016

Contact author: oxanapob at bu edu, canetti@bu edu, muthuv@cs rochester edu

Available format(s): PDF | BibTeX Citation

Version: 20170101:153642 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]