### Amortizing Garbled Circuits

Yan Huang, Jonathan Katz, Vladimir Kolesnikov, 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.

Note: Full version of paper published at CRYPTO 2014.

Available format(s)
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2014
Keywords
secure two-party computationgarbled circuits
Contact author(s)
amaloz @ cs umd edu
History
Short URL
https://ia.cr/2015/081

CC BY

BibTeX

@misc{cryptoeprint:2015/081,
author = {Yan Huang and Jonathan Katz and Vladimir Kolesnikov and Ranjit Kumaresan and Alex J.  Malozemoff},
title = {Amortizing Garbled Circuits},
howpublished = {Cryptology ePrint Archive, Paper 2015/081},
year = {2015},
note = {\url{https://eprint.iacr.org/2015/081}},
url = {https://eprint.iacr.org/2015/081}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.