Cryptology ePrint Archive: Report 2010/284

Secure Two-Party Computation via Cut-and-Choose Oblivious Transfer

Yehuda Lindell and Benny Pinkas

Abstract: Protocols for secure two-party computation enable a pair of parties to compute a function of their inputs while preserving security properties such as privacy, correctness and independence of inputs. Recently, a number of protocols have been proposed for the efficient construction of two-party computation secure in the presence of malicious adversaries (where security is proven under the standard simulation-based ideal/real model paradigm for defining security). In this paper, we present a protocol for this task that follows the methodology of using cut-and-choose to boost Yao's protocol to be secure in the presence of malicious adversaries. Relying on specific assumptions (DDH), we construct a protocol that is significantly more efficient and far simpler than the protocol of Lindell and Pinkas (Eurocrypt 2007) that follows the same methodology. We provide an exact, concrete analysis of the efficiency of our scheme and demonstrate that (at least for not very small circuits) our protocol is more efficient than any other known today.

Category / Keywords: cryptographic protocols / secure two-party computation, efficiency, DDH

Publication Info: An extended abstract appeared in TCC 2011; this is the full version.

Date: received 13 May 2010, last revised 18 Sep 2011

Contact author: lindell at cs biu ac il

Available format(s): PDF | BibTeX Citation

Version: 20110918:075640 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]