Welcome to the resource topic for 2024/223
Title:
GameTheoretically Fair Distributed Sampling
Authors: Sri Aravinda Krishnan Thyagarajan, Ke Wu, Pratik Soni
Abstract:Cleve’s celebrated result (STOC’86) showed that a strongly fair multiparty cointoss is impossible in the presence of majoritysized coalitions. Recently, however, a fascinating line of work studied a relaxed fairness notion called \emph{gametheoretic fairness}, which guarantees that no coalition should be incentivized to deviate from the prescribed protocol.
A sequence of works has explored the feasibility of gametheoretic fairness for \emph{twosided} cointoss, and indeed demonstrated feasibility in the dishonest majority setting under standard cryptographic assumptions. In fact, the recent work of Wu, Asharov, and Shi (EUROCRYPT’22) completely characterized the regime where gametheoretic fairness is feasible. However, this line of work is largely restricted to twosided cointoss, and more precisely on a \emph{uniform} cointoss (i.e., Bernoulli with parameter 1/2). The only exceptions are the works on gametheoretically fair leader election, which can be viewed as a special case of uniform nsided cointoss where n is the number of parties.
In this work, we \emph{initiate} the comprehensive study of gametheoretic fairness for multiparty \emph{sampling from general distributions}. In particular, for the case of msided \emph{uniform} cointoss we give a nearly complete characterization of the regime in which gametheoretic fairness is feasible. Interestingly, contrary to standard fairness notions in cryptography, the composition of gametheoretically fair twosided cointoss protocols does not necessarily yield gametheoretically fair multisided coins. To circumvent this, we introduce new techniques compatible with gametheoretic fairness.
In particular, we give the following results:

We give a protocol from standard cryptographic assumptions that achieves gametheoretic fairness for uniform msided cointoss against half or moresized adversarial coalitions.

To complement our protocol, we give a general impossibility result that establishes the optimality of our protocol for a broad range of parameters modulo an additive constant. Even in the worstcase, the gap between our protocol and our impossibility result is only a small constant multiplicative factor.

We also present a gametheoretically fair protocol for \emph{any} efficiently sampleable moutcome distribution in the dishonest majority setting. For instance, even for the case of m=2 (i.e., twosided cointoss), our result implies a gametheoretically fair protocol for an \emph{arbitrary} Bernoulli coin. In contrast, the work of Wu, Asharov, and Shi only focussed on a Bernoulli coin with parameter 1/2.
ePrint: https://eprint.iacr.org/2024/223
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 .