In this paper, we present a cut-and-choose protocol for secure computation based on garbled circuits, with security in the presence of malicious adversaries, that vastly improves on all previous protocols of this type. Concretely, for a cheating probability of at most $2^{-40}$, the best previous works send between 125 and 128 circuits. In contrast, in our protocol 40 circuits alone suffice (with some additional overhead). Asymptotically, we achieve a cheating probability of $2^{-s}$ where $s$ is the number of garbled circuits, in contrast to the previous best of $2^{-0.32s}$. We achieve this by introducing a new cut-and-choose methodology with the property that in order to cheat, \emph{all} of the evaluated circuits must be incorrect, and not just the \emph{majority} as in previous works. The security of our protocol relies on the Decisional Diffie-Hellman assumption.
Category / Keywords: cryptographic protocols / Original Publication (with major differences): IACR-CRYPTO-2013 Date: received 16 Feb 2013, last revised 7 Feb 2015 Contact author: lindell at biu ac il Available format(s): PDF | BibTeX Citation Note: A minor error in the protocol was discovered, and has been fixed in this version. Version: 20150208:062920 (All versions of this report) Short URL: ia.cr/2013/079