Cryptology ePrint Archive: Report 2015/1209

Fast Optimistically Fair Cut-and-Choose 2PC

Alptekin Kupcu and Payman Mohassel

Abstract: Secure two party computation (2PC) is a well-studied problem with many real world applications. Due to Cleve's result on general impossibility of fairness, however, the state-of-the-art solutions only provide security with abort. We investigate fairness for 2PC in presence of a trusted Arbiter, in an optimistic setting where the Arbiter is not involved if the parties act fairly. Existing fair solutions in this setting are by far less efficient than the fastest unfair 2PC.

We close this efficiency gap by designing protocols for fair 2PC with covert and malicious security that have competitive performance with the state-of-the-art unfair constructions. In particular, our protocols only requires the exchange of a few extra messages with sizes that only depend on the output length; the Arbiter's load is independent of the computation size; and a malicious Arbiter can only break fairness, but not covert/malicious security even if he colludes with a party. Finally, our solutions are designed to work with the state-of-the-art optimizations applicable to garbled circuits and cut-and-choose 2PC such as free-XOR, half-gates, and the cheating-recovery paradigm.

Category / Keywords: cryptographic protocols / secure two-party computation, covert adversaries, cut-and-choose, garbled circuits, fair secure computation, optimistic fair exchange

Original Publication (with major differences): Financial Cryptography 2016

Date: received 17 Dec 2015

Contact author: payman mohassel at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20151219:174950 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]