Amortizing Yao Garbled Circuits

Motivated by a recent line of work improving the performance of secure two-party computation (2PC), we consider 2PC in the practically important multiple execution setting, where two parties wish to securely evaluate the same circuit t times. We design efficient garbled circuit-based two-party protocols secure against malicious adversaries. Recent works by Lindell (Crypto 2013), Huang-Katz-Evans (Crypto 2013), and Mohassel-Riva (Crypto 2013) have obtained optimal complexity for cut-and-choose performed over garbled circuits in the single execution setting. We show that it is possible to obtain much lower amortized overhead for cut-and-choose in the multiple execution setting. Our efficiency improvements result from a novel way to combine a recent technique of Lindell (Crypto 2013) with LEGO-based cut-and-choose techniques (Eurocrypt 2013, TCC 2009). In concrete terms, for 40 bits of statistical security we obtain improvement _>=2x for t as low as 7 in communication/computation costs per execution, and require only 8 garbled circuits (i.e., an improvement >= 5x) per execution for t = 3500. Our results suggest the exciting possibility that secure two-party computation in the malicious setting can be less than an order of magnitude more expensive than in the semi-honest setting.