We introduce here the idea of symmetric cut-and-choose protocols, in which each party generates $\kappa$ circuits to be checked by the other party. The main advantage of our technique is that the number $\kappa$ of garbled circuits can be reduced by a factor of 3 while attaining the same statistical security level as in prior work. Since the number of garbled circuits dominates the costs of the protocol, especially as larger circuits are evaluated, our protocol is expected to run up to 3 times faster than existing schemes. Preliminary experiments validate this claim.
Category / Keywords: cryptographic protocols / Publication Info: This is a long version of a Crypto 2013 paper Date: received 16 Feb 2013, last revised 7 Jun 2013 Contact author: jkatz at cs umd edu Available format(s): PDF | BibTeX Citation Note: Minor fix in Section 4.1. Version: 20130607:193152 (All versions of this report) Short URL: ia.cr/2013/081