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

Publication
Oct 12, 2015
Abstract

 Many deployments of secure multi-party computation (MPC) in practice have used information-theoretic three-party protocols that tolerate a {\em 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, {\em 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.  

  • The ACM Conference on Computer and Communications Security (CCS) (ACM CCS 2015)
  • Conference/Workshop Paper

BibTeX