Welcome to the resource topic for 2024/223
Title:
Game-Theoretically Fair Distributed Sampling
Authors: Sri Aravinda Krishnan Thyagarajan, Ke Wu, Pratik Soni
Abstract:Cleve’s celebrated result (STOC’86) showed that a strongly fair multi-party coin-toss is impossible in the presence of majority-sized coalitions. Recently, however, a fascinating line of work studied a relaxed fairness notion called \emph{game-theoretic fairness}, which guarantees that no coalition should be incentivized to deviate from the prescribed protocol.
A sequence of works has explored the feasibility of game-theoretic fairness for \emph{two-sided} coin-toss, 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 game-theoretic fairness is feasible. However, this line of work is largely restricted to two-sided coin-toss, and more precisely on a \emph{uniform} coin-toss (i.e., Bernoulli with parameter 1/2). The only exceptions are the works on game-theoretically fair leader election, which can be viewed as a special case of uniform n-sided coin-toss where n is the number of parties.
In this work, we \emph{initiate} the comprehensive study of game-theoretic fairness for multi-party \emph{sampling from general distributions}. In particular, for the case of m-sided \emph{uniform} coin-toss we give a nearly complete characterization of the regime in which game-theoretic fairness is feasible. Interestingly, contrary to standard fairness notions in cryptography, the composition of game-theoretically fair two-sided coin-toss protocols does not necessarily yield game-theoretically fair multi-sided coins. To circumvent this, we introduce new techniques compatible with game-theoretic fairness.
In particular, we give the following results:
-
We give a protocol from standard cryptographic assumptions that achieves game-theoretic fairness for uniform m-sided coin-toss against half- or more-sized 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 worst-case, the gap between our protocol and our impossibility result is only a small constant multiplicative factor.
-
We also present a game-theoretically fair protocol for \emph{any} efficiently sampleable m-outcome distribution in the dishonest majority setting. For instance, even for the case of m=2 (i.e., two-sided coin-toss), our result implies a game-theoretically 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 .