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.
Category / Keywords: foundations / secure computation Publication Info: This is the full version of the paper that appeared at STOC 2008 Date: received 7 Jul 2008 Contact author: jkatz at cs umd edu Available format(s): PDF | BibTeX Citation Version: 20080708:164437 (All versions of this report) Short URL: ia.cr/2008/303 Discussion forum: Show discussion | Start new discussion