Cryptology ePrint Archive: Report 2015/931

Fast and Secure Three-party Computation: The Garbled Circuit Approach

Payman Mohassel and Mike Rosulek and Ye Zhang

Abstract: Many deployments of secure multi-party computation (MPC) in practice have used information-theoretic three-party protocols that tolerate a single, semi-honest corrupt party, since these protocols enjoy very high efficiency.

We propose a new approach for secure three-party computation (3PC) that improves security while maintaining practical efficiency that is competitive with traditional information-theoretic protocols. Our protocol is based on garbled circuits and provides security against a single, malicious corrupt party. Unlike information-theoretic 3PC protocols, ours uses a constant number of rounds. Our protocol only uses inexpensive symmetric-key cryptography: hash functions, block ciphers, pseudorandom generators (in particular, no oblivious transfers) and has performance that is comparable to that of Yao's (semi-honest) 2PC protocol.

We demonstrate the practicality of our protocol with an implementation based on the JustGarble framework of Bellare et al. (S&P 2013). The implementation incorporates various optimizations including the most recent techniques for efficient circuit garbling. We perform experiments on several benchmarking circuits, in different setups. Our experiments confirm that, despite providing a more demanding security guarantee, our protocol has performance comparable to existing information-theoretic 3PC.

Category / Keywords: cryptographic protocols / secure computation, garbled circuits, three-party

Original Publication (in the same form): ACM CCS 2015

Date: received 23 Sep 2015

Contact author: payman mohassel at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20150927:092340 (All versions of this report)

Short URL: ia.cr/2015/931

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]