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.
Category / Keywords: cryptographic protocols / secure two-party computation, garbled circuits Original Publication (with major differences): IACR-CRYPTO-2014 Date: received 3 Feb 2015 Contact author: amaloz at cs umd edu Available format(s): PDF | BibTeX Citation Note: Full version of paper published at CRYPTO 2014. Version: 20150210:222210 (All versions of this report) Short URL: ia.cr/2015/081