Paper 2015/1209

Fast Optimistically Fair Cut-and-Choose 2PC

Alptekin Kupcu and Payman Mohassel


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. Financial Cryptography 2016
secure two-party computationcovert adversariescut-and-choosegarbled circuitsfair secure computationoptimistic fair exchange
Contact author(s)
payman mohassel @ gmail com
2015-12-19: received
Short URL
Creative Commons Attribution


      author = {Alptekin Kupcu and Payman Mohassel},
      title = {Fast Optimistically Fair Cut-and-Choose 2PC},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1209},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.