Billion-Gate Secure Computation with Malicious Adversaries

Benjamin Kreuter; abhi shelat; Chih-hao Shen

Paper 2012/179

Billion-Gate Secure Computation with Malicious Adversaries

Benjamin Kreuter, abhi shelat, and Chih-hao Shen

Abstract

The goal of this paper is to assess the feasibility of two-party secure computation in the presence of a malicious adversary. Prior work has shown the feasibility of billion-gate circuits in the semi-honest model, but only the 35k-gate AES circuit in the malicious model, in part because security in the malicious model is much harder to achieve. We show that by incorporating the best known techniques and parallelizing almost all steps of the resulting protocol, evaluating billion-gate circuits is feasible in the malicious model. Our results are in the standard model (i.e., no common reference strings or PKIs) and, in contrast to prior work, we do not use the random oracle model which has well-established theoretical shortcomings.

Metadata

Available format(s): PDF
Publication info: Published elsewhere. published in USENIX Security 2012
Keywords: garbled circuit cut-and-choose circuit-level parallelism
Contact author(s): shench @ virginia edu
History: 2012-08-14: revised; 2012-04-11: received; See all versions
Short URL: https://ia.cr/2012/179
License: CC BY

BibTeX

@misc{cryptoeprint:2012/179,
      author = {Benjamin Kreuter and abhi shelat and Chih-hao Shen},
      title = {Billion-Gate Secure Computation with Malicious Adversaries},
      howpublished = {Cryptology {ePrint} Archive, Paper 2012/179},
      year = {2012},
      url = {https://eprint.iacr.org/2012/179}
}