Welcome to the resource topic for 2013/442
Title:
On Fair Exchange, Fair Coins and Fair Sampling
Authors: Shashank Agrawal, Manoj Prabhakaran
Abstract:We study various classical secure computation problems in the context of fairness, and relate them with each other. We also systematically study fair sampling problems (i.e., inputless functionalities) and discover three levels of complexity for them. 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.
ePrint: https://eprint.iacr.org/2013/442
Talk: https://www.youtube.com/watch?v=WyaiZShN9BQ
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .