Cryptology ePrint Archive: Report 2012/179

Billion-Gate Secure Computation with Malicious Adversaries

Benjamin Kreuter and 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.

Category / Keywords: garbled circuit, cut-and-choose, circuit-level parallelism

Publication Info: published in USENIX Security 2012

Date: received 4 Apr 2012, last revised 14 Aug 2012

Contact author: shench at virginia edu

Available format(s): PDF | BibTeX Citation

Version: 20120814:181412 (All versions of this report)

Short URL: ia.cr/2012/179

Discussion forum: Show discussion | Start new discussion