Paper 2013/081

Efficient Secure Two-Party Computation Using Symmetric Cut-and-Choose

Yan Huang, Jonathan Katz, and Dave Evans


Beginning with the work of Lindell and Pinkas, researchers have proposed several protocols for secure two-party computation based on the cut-and-choose paradigm. In existing instantiations of this paradigm, one party generates $\kappa$ garbled circuits; some fraction of those are ``checked'' by the other party, and the remaining fraction are evaluated. 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.

Note: Minor fix in Section 4.1.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. This is a long version of a Crypto 2013 paper
Contact author(s)
jkatz @ cs umd edu
2013-06-07: last of 2 revisions
2013-02-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yan Huang and Jonathan Katz and Dave Evans},
      title = {Efficient Secure Two-Party Computation Using Symmetric Cut-and-Choose},
      howpublished = {Cryptology ePrint Archive, Paper 2013/081},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.