Paper 2012/179

Billion-Gate Secure Computation with Malicious Adversaries

Benjamin Kreuter, abhi shelat, and Chih-hao Shen


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.

Available format(s)
Publication info
Published elsewhere. published in USENIX Security 2012
garbled circuitcut-and-choosecircuit-level parallelism
Contact author(s)
shench @ virginia edu
2012-08-14: revised
2012-04-11: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.