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
Creative Commons Attribution
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.