We present a new technique for simulating fair coin flips using a biased, stationary source of randomness. Sequences of random numbers are of pervasive importance in cryptography and vital to many other computing applications. Many sources of randomness, such as radioactive or quantum-mechanical sources, possess the property of stationarity. In other words, they produce independent outputs over fixed probability distributions. The output of such sources may be viewed as the result of rolling a biased or loaded die. While a biased die may be a good source of entropy, many applications require input in the form of unbiased bits, rather than biased ones. For this reason, von Neumann (1951) presented a now well-known and extensively investigated technique for using a biased coin to simulate a fair coin. We describe a new generalization of von Neumann's algorithm distinguished by its high level of practicality and amenability to analysis. In contrast to previous efforts, we are able to prove our algorithm optimally efficient, in the sense that it simulates the maximum possible number of fair coin flips for a given number of die rolls. In fact, we are able to prove that in an asymptotic sense our algorithm extracts the full entropy of its input. Moreover, we demonstrate experimentally that our algorithm achieves a high level of computational and output efficiency in a practical setting.
We present a new technique for simulating fair coin flips using a biased, stationary source of randomness. Sequences of random numbers are of pervasive importance in cryptography and vital to many other computing applications. Many sources of randomness, such as radioactive or quantum-mechanical sources, possess the property of stationarity. In other words, they produce independent outputs over fixed probability distributions. The output of such sources may be viewed as the result of rolling a biased or loaded die. While a biased die may be a good source of entropy, many applications require input in the form of unbiased bits, rather than biased ones. For this reason, von Neumann (1951) presented a now well-known and extensively investigated technique for using a biased coin to simulate a fair coin. We describe a new generalization of von Neumann's algorithm distinguished by its high level of practicality and amenability to analysis. In contrast to previous efforts, we are able to prove our algorithm optimally efficient, in the sense that it simulates the maximum possible number of fair coin flips for a given number of die rolls. In fact, we are able to prove that in an asymptotic sense our algorithm extracts the full entropy of its input. Moreover, we demonstrate experimentally that our algorithm achieves a high level of computational and output efficiency in a practical setting.
Coin-flipping protocols allow mutually distrustful parties to generate a random bit with uniform distribution. Minimizing bias and keeping fairness are two key requirements in designing such protocols. However, the best previously known fair coin-flipping protocol only guarantees with bias O (1/ r ). In the paper, we introduce a new approach for fair coin-flipping protocol construction by using Garay et al ’s “resource fairness” technique and propose a resource-fair two-party coin-flipping protocol according to the standard real/ideal simulation paradigm. Compared with the other coin-flipping protocols, our protocol enjoys an important advantage that its bias is 0.
Coin flipping is a cryptographic primitive in which two spatially separated players, who do not trust each other, wish to establish a common random bit. If we limit ourselves to classical communication, this task requires either assumptions on the computational power of the players or it requires them to send messages to each other with sufficient simultaneity to force their complete independence. Without such assumptions, all classical protocols are so that one dishonest player has complete control over the outcome. If we use quantum communication, on the other hand, protocols have been introduced that limit the maximal bias that dishonest players can produce. However, those protocols would be very difficult to implement in practice because they are susceptible to realistic losses on the quantum channel between the players or in their quantum memory and measurement apparatus. In this paper, we introduce a quantum protocol and we prove that it is completely impervious to loss. The protocol is fair in the sense that either player has the same probability of success in cheating attempts at biasing the outcome of the coin flip. We also give explicit and optimal cheating strategies for both players.
In this paper we study von Neumann un-biasing normalisation for ideal and real quantum random number generators, operating on finite strings or infinite bit sequences.In the ideal cases one can obtain the desired un-biasing.This relies critically on the independence of the source, a notion we rigorously define for our model.In real cases, affected by imperfections in measurement and hardware, one cannot achieve a true un-biasing, but, if the bias "drifts sufficiently slowly", the result can be arbitrarily close to un-biasing.For infinite sequences, normalisation can both increase or decrease the (algorithmic) randomness of the generated sequences.A successful application of von Neumann normalisation-in fact, any un-biasing transformation-does exactly what it promises, un-biasing, one (among infinitely many) symptoms of randomness; it will not produce "true" randomness.
Abstract In a multi-party fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some adversarial parties try to bias the output. In this work, we focus on the case of an arbitrary number of corrupted parties. Cleve [20] [STOC 1986] has shown that in any such m -round coin-flipping protocol, the corrupted parties can bias the honest parties’ common output bit by Θ(1/m) Θ ( 1 / m ) . For more than two decades, however, the best-known coin-flipping protocol was the one of Awerbuch, Blum, Chor, Goldwasser, and Micali [10] [Manuscript 1985], who presented a t -party, m -round protocol with bias Θ(t/m) Θ ( t / m ) . This was changed by the breakthrough result of Moran, Naor, and Segev [51] [Journal of Cryptology 2016], who constructed an m -round, two -party coin-flipping protocol with optimal bias Θ(1/m) Θ ( 1 / m ) . More recently, Haitner and Tsfadia [37] [SIAM Journal on Computing 2017] constructed an m -round, three -party coin-flipping protocol with bias O(log3m/m) O ( log 3 m / m ) . Still for the case of more than three parties, the best-known protocol remained the Θ(t/m) Θ ( t / m ) -bias protocol of [10]. We make a step toward eliminating the above gap, presenting a t -party, m -round coin-flipping protocol, with bias O(m1/2+1/(2t−1−2)t4⋅2t⋅logm) O t 4 · 2 t · log m m 1 / 2 + 1 / ( 2 t - 1 - 2 ) for any t≤21⋅loglogm t ≤ 1 2 · loglog m . This improves upon the
In a multi-party fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. In this work we focus on the case of dishonest majority, ie at least half of the parties can be corrupted. [19] [STOC 1986] has shown that in any m-round coin-flipping protocol the corrupted parties can bias the honest parties’ common output bit by Θ(1/m). For more than two decades the best known coin-flipping protocols against majority was the protocol of [9] [Manuscript 1985], who presented a t-party, m-round protocol with bias This was changed by the breakthrough result of [42] [TCC 2009], who constructed an m-round, two-party coin-flipping protocol with optimal bias Θ(1/m). Recently, [32] [STOC 14] constructed an m-round, three-party coin-flipping protocol with bias O(log3 m/m). Still for the case of more than three parties, against arbitrary number of corruptions, the best known protocol remained the protocol of [9]. We make a step towards eliminating the above gap, presenting a t-party, m-round coin-flipping protocol, with bias This improves upon the protocol of [9] for any t ≤ 1/2 · log log m, and in particular for t ∊ O(1), this yields an protocol. For the three-party case, this yields an protocol, improving over the the O(log3 m/m)-bias protocol of [32]. Our protocol generalizes that of [32], by presenting an appropriate “defense protocols” for the remaining parties to interact in, in the case that some parties abort or caught cheating ([32] only presented a two-party defense protocol, which limits their final protocol to handle three parties). We analyze our new protocols by presenting a new paradigm for analyzing fairness of coin-flipping protocols. We map the set of adversarial strategies that try to bias the honest parties outcome in the protocol to the set of the feasible solutions of a linear program. The gain each strategy achieves is the value of the corresponding solution. We then bound the the optimal value of the linear program by constructing a feasible solution to its dual.
In a multiparty fair coin-flipping protocol, the parties output a common (close to) unbiased bit, even when some corrupted parties try to bias the output. Cleve [in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1986, pp. 364--369] has shown that in the case of dishonest majority (i.e., at least half of the parties can be corrupted), in any m-round coin-flipping protocol the corrupted parties can bias the honest parties' common output bit by Ω(m1). For more than two decades the best known coin-flipping protocols against dishonest majority had bias Θ(mℓ), where ℓ is the number of corrupted parties. This was changed by a recent breakthrough result of Moran, Naor, and Segev [in Theory of Cryptography, Lecture Notes in Comput. Sci. 5444, Springer, Berlin, 2009, pp. 1--18], who constructed an m-round, two-party coin-flipping protocol with optimal bias Θ(m1). In a subsequent work, Beimel, Omri, and Orlov [in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC), ACM, New York, 1990, pp. 503--513] extended this result to the multiparty case in which less than 32 of the parties can be corrupted. Still, for the case of 32 (or more) corrupted parties, the best known protocol had bias Θ(mℓ). In particular, this was the state of affairs for the natural three-party case. We take a step toward eliminating the above gap, presenting an m-round, three-party coin-flipping protocol, with bias mO(log3m). Our approach (which we also apply to the two-party case) does not follow the “threshold round" paradigm used in the work of Moran, Naor, and Segev and Beimel, Omri, and Orlov but rather is a variation of the majority protocol of Cleve used to obtain the aforementioned Θ(mℓ)-bias protocol.