Complete Fairness in Secure Two-Party Computation

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearchpeer-review

  • S. Dov Gordon, Columbia University, Colombia
  • Carmit Hazay
  • Jonathan Katz, University of Maryland
  • ,
  • Yehuda Lindell, Bar-Ilan University

In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness which guarantees, informally, that if one party receives its output, then the other party does too. Cleve [1986] showed that complete fairness cannot be achieved in general without an honest majority. Since then, the accepted folklore has been that nothing non-trivial can be computed with complete fairness in the two-party setting.

We demonstrate that this folklore belief is false by showing completely fair protocols for various nontrivial functions in the two-party setting based on standard cryptographic assumptions. We first show feasibility of obtaining complete fairness when computing any function over polynomial-size domains that does not contain an “embedded XOR”; this class of functions includes boolean AND/OR as well as Yao’s “millionaires’ problem”. We also demonstrate feasibility for certain functions that do contain an embedded XOR, though we prove a lower bound showing that any completely fair protocol for such functions must have round complexity super-logarithmic in the security parameter. Our results demonstrate that the question of completely fair secure computation without an honest majority is far from closed.
Original languageEnglish
JournalAssociation for Computing Machinery. Journal
Volume58
Issue6
Pages (from-to)Article no. 24
Number of pages37
ISSN0004-5411
DOIs
Publication statusPublished - 2011

See relations at Aarhus University Citationformats

ID: 44449458