Our results include the following:
-Fair exchange cannot be securely reduced to the problem of fair coin-tossing by an r-round protocol, except with an error that is $\Omega(1/r)$.
-Finite fair {\em sampling} problems with rational probabilities can all be reduced to fair coin-tossing and unfair 2-party computation (or equivalently, under computational assumptions). Thus, for this class of functionalities, fair coin-tossing is complete.
-Only sampling problems which have fair protocols without any fair setup are the trivial ones in which the two parties can sample their outputs independently. Others all have an $\Omega(1/r)$ error, roughly matching an upper bound for fair sampling from Moran et al. (TCC 2009).
-We study communication-less protocols for sampling, given another sampling problem as setup, since such protocols are inherently fair. We use spectral graph theoretic tools to show that it is impossible to reduce a sampling problem with {\em common information} (like fair coin-tossing) to a sampling problem without (like 'noisy' coin-tossing, which has a small probability of disagreement).
The last result above is a slightly sharper version of a classical result by Witsenhausen from 1975. Our proof reveals the connection between the tool used by Witsenhausen, namely 'maximal correlation', and spectral graph theoretic tools like Cheeger inequality.
Category / Keywords: foundations / fairness, secure computation, impossibility, common information, cheeger constant Publication Info: This is the full version of the paper in CRYPTO 2013. Date: received 13 Jul 2013, last revised 21 Jul 2013 Contact author: sagrawl2 at illinois edu Available format(s): PDF | BibTeX Citation Version: 20130721:145542 (All versions of this report) Short URL: ia.cr/2013/442 Discussion forum: Show discussion | Start new discussion