Paper 2015/081
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.
Metadata
- Available format(s)
-
PDF
- 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
- 2015-02-10: received
- Short URL
- https://ia.cr/2015/081
- License
-
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}
}
