Paper 2008/303

Complete Fairness in Secure Two-Party Computation

S. Dov Gordon, Carmit Hazay, Jonathan Katz, and Yehuda Lindell

Abstract

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, 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 (STOC 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, and the problem has been treated as closed since the late '80s. In this paper, we demonstrate that this folklore belief is false by showing completely-fair protocols for various non-trivial 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, and 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. This is the full version of the paper that appeared at STOC 2008
Keywords
secure computation
Contact author(s)
jkatz @ cs umd edu
History
2008-07-08: received
Short URL
https://ia.cr/2008/303
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/303,
      author = {S.  Dov Gordon and Carmit Hazay and Jonathan Katz and Yehuda Lindell},
      title = {Complete Fairness in Secure Two-Party Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2008/303},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/303}},
      url = {https://eprint.iacr.org/2008/303}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.