Cryptology ePrint Archive: Report 2015/081

Amortizing Garbled Circuits

Yan Huang and Jonathan Katz and Vladimir Kolesnikov and Ranjit Kumaresan and Alex J. Malozemoff

Abstract: We consider secure two-party computation in a multiple-execution setting, where two parties wish to securely evaluate the same circuit multiple times. We design efficient garbled-circuit-based two-party protocols secure against malicious adversaries. Recent works by Lindell (Crypto 2013) and Huang-Katz-Evans (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 (TCC 2009, Eurocrypt 2013). In concrete terms, for 40-bit statistical security we obtain a 2x improvement (per execution) in communication and computation for as few as 7 executions, and require only 8 garbled circuits (i.e., a 5x improvement) per execution for as low as 3500 executions. 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.

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

Original Publication (with major differences): IACR-CRYPTO-2014

Date: received 3 Feb 2015

Contact author: amaloz at cs umd edu

Available format(s): PDF | BibTeX Citation

Note: Full version of paper published at CRYPTO 2014.

Version: 20150210:222210 (All versions of this report)

Short URL: ia.cr/2015/081