Fast and Secure Three-party Computation: The Garbled Circuit Approach
Venue
The 22nd ACM Conference on Computer and Communications Security, ACM (2015)
Publication Year
2015
Authors
Payman Mohassel, Mike Rosulek, Ye Zhang
BibTeX
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.
