Alice seeks an information-theoretically secure source of private random data. Unfortunately, she lacks a personal source and must use remote sources controlled by other parties. Alice wants to simulate a coin flip of specified bias $\alpha$, as a function of data she receives from $p$ sources; she seeks privacy from any coalition of $r$ of them. We show: If $p/2 \leq r < p$, the bias can be any rational number and nothing else; if $0 < r < p/2$, the bias can be any algebraic number and nothing else. The proof uses projective varieties, convex geometry, and the probabilistic method. Our results improve on those laid out by Yao, who asserts one direction of the $r=1$ case in his seminal paper [Yao82]. We also provide an application to secure multiparty computation.
Alice seeks an information-theoretically secure source of private random data. Unfortunately, she lacks a personal source and must use remote sources controlled by other parties. Alice wants to simulate a coin flip of specified bias α, as a function of data she receives from p sources; she seeks privacy from any coalition of r of them. We show: If p/2≤r<p, the bias can be any rational number and nothing else; if 0<r<p/2, the bias can be any algebraic number and nothing else. The proof uses projective varieties, convex geometry, and the probabilistic method. Our results improve on those laid out by Yao, who asserts one direction of the r=1 case in his seminal paper [Yao82]. We also provide an application to secure multiparty computation.
In secure multiparty computation, mutually distrusting users in a network want to collaborate to compute functions of data which is distributed among the users. The users should not learn any additional information about the data of others than what they may infer from their own data and the functions they are computing. Previous works have mostly considered the worst case context (i.e., without assuming any distribution for the data); Lee and Abbe (2014) is a notable exception. Here, we study the average case (i.e., we work with a distribution on the data) where correctness and privacy is only desired asymptotically. For concreteness and simplicity, we consider a secure version of the function computation problem of Körner and Marton (1979) where two users observe a doubly symmetric binary source with parameter p and the third user wants to compute the XOR. We show that the amount of communication and randomness resources required depends on the level of correctness desired. When zero-error and perfect privacy are required, the results of Data et al. (2014) show that it can be achieved if and only if a total rate of 1 bit is communicated between every pair of users and private randomness at the rate of 1 is used up. In contrast, we show here that, if we only want the probability of error to vanish asymptotically in blocklength, it can be achieved by a lower rate (binary entropy of p) for all the links and for private randomness; this also guarantees perfect privacy. We also show that no smaller rates are possible even if privacy is only required asymptotically.
Secure coin-tossing is typically modeled as an input-less functionality, where parties with no private inputs jointly generate a fair coin. In the dishonest majority setting, however, a strongly fair coin-tossing protocol is impossible. To circumvent this barrier, recent work has adopted the weaker notion of game-theoretic fairness, where adversaries are rational parties with preferences for specific outcomes, seeking to bias the coin in their favor. Yet these preferences may encode secret information, making prior protocols that assume preferences are public, fundamentally incompatible with privacy. We initiate a comprehensive study of privacy-preserving game-theoretically fair coin-tossing, where the preferences of honest parties remain private. We propose a simulation-based security framework and a new ideal functionality that reconciles both preference-privacy and game-theoretic fairness. A key ingredient is a certifying authority that authenticates each party’s preference and publishes only aggregate statistics, preventing misreporting while hiding parties' preferences. The functionality guarantees that every honest party receives an output: either a uniform coin; or, if an adversary deviates, a coin that does not increase the adversarial coalition's expected utility. Within this framework, we construct a protocol realizing our ideal functionality under standard cryptographic assumptions that works for both binary and general m -sided coin-tossing. Our binary scheme matches the corruption threshold of Wu-Asharov-Shi (EUROCRYPT '22); our multi-sided scheme builds on Thyagarajan-Wu-Soni (CRYPTO '24) with a corruption guarantee depending on the coalition's preference counts. Technically, our protocols combine authenticated preferences with an anonymous communication layer that decouples identities from preference-dependent actions, together with a deviation-penalty mechanism that enforces game-theoretic fairness. Our work is the first to reconcile game-theoretic fairness with preference privacy, offering new definitional tools and efficient protocols for rational multi-party computation in dishonest majority settings.
In his seminal work, Cleve [ Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986, pp. 364--369] has proved that any r-round coin-flipping protocol can be efficiently biased by Θ(1/r). This lower bound was met for the two-party case by Moran, Naor, and Segev [ J. Cryptology, 29 (2016), pp. 491--513] and the three-party case (up to a polylog factor) by Haitner and Tsfadia [ SIAM J. Comput., 46 (2017), pp. 479--542] and was approached for n-party protocols when n<loglogr by Buchbinder et al. [ Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, 2017, pp. 2580--2600]. For n>loglogr, however, the best bias for n-party coin-flipping protocols remains O(n/r) achieved by the majority protocol of Awerbuch et al. [ How to implement Bracha's O(logn) Byzantine Agreement Algorithm, manuscript, 1985]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant ε>0, an rε-party r-round coin-flipping protocol can be efficiently biased by Ω(1/r). As far as we know, this is the first improvement of Cleve's bound and is only n=rε (multiplicative) far from the aforementioned upper bound of Awerbuch et al. We prove the above bound using two new results that we believe are of independent interest. The first result is that a sequence of (``augmented'') weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes over the result of Cleve and Impagliazzo [ Martingales, Collective Coin Flipping and Discrete Control Processes (Extended Abstract), http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.1797, 1993], who showed that the above holds for strong martingales, and allows in some setting to exploit this gap by efficient algorithms. We prove the above using a novel argument that does not follow the more complicated approach of R. Cleve and R. Impagliazzo. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence.
In the random oracle model, the parties are given oracle access to a random member of a (typically huge) function family, and are assumed to have unbounded computational power (though they can only make a bounded number of oracle queries). This model provides powerful properties that allow proving the security of many protocols, even such that cannot be proved secure in the standard model (under any hardness assumption). The random oracle model is also used to show that a given cryptographic primitive cannot be used in a black-box way to construct another primitive; in their seminal work, Impagliazzo and Rudich [STOC ’89] showed that in the random function model – when the function family is the set of all functions – it is impossible to construct (secure) key-agreement protocols, yielding that key-agreement cannot be black-box reduced to one-way functions. Their work has a long line of followup works (Simon [EC ’98], Gertner et al. [STOC ’00] and Gennaro et al. [SICOMP ’05], to name a few), showing that given oracle access to a certain type of function family (e.g., the family that “implements ” public-key encryption) is not sufficient for building a given cryptographic primitive (e.g., oblivious transfer). Yet, in the more general sense, the following fundamental question remained open: What is the exact power of the random oracle model, and more specifically, of the random function model? We make progress towards answering the above question, showing that any (no private input) semi-honest two-party functionality that can be securely implemented in the random function model, can be securely implemented information theoretically (where parties are assumed to be all powerful, and no oracle is given). We further generalize the above result to function families that provide some natural combinatorial property. To exhibit the power of our result, we use the recent information theoretic impossibility result of McGregor et al. [FOCS ’10], to show the existence of functionalities (e.g., inner product) that cannot be computed both accurately and in a differentially private manner in the random function model; yielding that protocols for computing these functionalities cannot be black-box reduced to the existence of one-way functions.
In his seminal work, Cleve [STOC '86] has proved that any r-round coin-flipping protocol can be efficiently biased by Θ(1/r). This lower bound was met for the two-party case by Moran, Naor, and Segev [Journal of Cryptology '16], and the three-party case (up to a polylog factor) by Haitner and Tsfadi [SICOMP '17], and was approached for n-party protocols when n<loglogr by Buchbinder, Haitner, Levi, and Tsfadia [SODA '17]. For n>loglogr, however, the best bias for n-party coin-flipping protocols remains O(n/r) achieved by the majority protocol of Awerbuch, Blum, Chor, Goldwasser, and Micali [Manuscript '85]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, for every constant ε>0, an rε-party r-round coin-flipping protocol can be efficiently biased by Ω(1/r). As far as we know, this is the first improvement of Cleve's bound, and is only n=rε (multiplicative) far from the aforementioned upper bound of Awerbuch et al.
In his seminal work, Cleve [STOC '86] proved that the bias of any coin-flipping protocol is inversely proportional to the number of rounds. This lower bound was met for the two-party case by Moran et al. [Journal of Cryptology '16], and the three-party case (up to a polylogarithmic factor) by Haitner and Tsfadia [SICOMP '17], and was approached for multi-party protocols by Haitner et al. [SODA '17] when the number of rounds is at least doubly exponential in the number of parties. For the complement case, however, the best bias for multi-party coin-flipping protocols is proportional to the number of parties and inversely proportional to the square root of the number of rounds. The latter bias is achieved by the majority protocol of Awerbuch et al. [Manuscript '85]. Our main result is a tighter lower bound on the bias of coin-flipping protocols, showing that, if the number of rounds is bounded by some polynomial in the number of parties, then the bias is lower-bounded by a quantity that is inversely proportional to the square root of the number of rounds (up to a polylogarithmic factor). As far as we know, this is the first improvement of Cleve's bound, and is far from the aforementioned upper bound of Awerbuch et al. only by a factor of the number of parties. We prove the above bound using two new results that we believe are of independent interest. The first result is that a sequence of ("augmented") weak martingales have large gap: with constant probability there exists two adjacent variables whose gap is at least the ratio between the gap between the first and last variables and the square root of the number of variables. This generalizes over the result of Cleve and Impagliazzo [Manuscript '93], who showed that the above holds for strong martingales, and allows in some setting to exploit this gap by efficient algorithms. We prove the above using a novel argument that does not follow the more complicated approach of Cleve and Impagliazzo. The second result is a new sampling algorithm that uses a differentially private mechanism to minimize the effect of data divergence.