Abstract
We consider an asynchronous network of n parties connected to each other via secure channels, up to t of which are byzantine. We study common coin tossing, a task where the parties try to agree on an unpredictable random value, with some chance of failure due to the byzantine parties' influence. Coin tossing is a well known and often studied task due to its use in byzantine agreement. In this work, we present an adaptively secure committee-based method to roughly speaking turn strong but costly common coins into cheaper but lower-quality ones. For all k > 2 and ε > 0, we show how to use a strong (very rarely failing) coin that costs O(n^k) bits of communication to get a cheaper coin that costs O(ε^-2kn^3 - 2/k) bits of communication. This latter coin tolerates ε n fewer byzantine parties than the former, and it fails with an arbitrarily small constant probability. For any ε > 0, our method allows us to get a perfectly secure binary coin that tolerates t ≤ (1/4 - ε)n faults with O(n^2.5(ε⁻⁸ + log n)) messages of size O(log n), as well as a setup-free cryptographically secure binary coin that tolerates t ≤ (1/3 - ε)n faults with O(n^7/3ε⁻⁶κlog n) bits of communication (where κ = Ω(log n) is a cryptographic security paramater). These coins both have O(log n) latency. They are to our knowledge the first setup-free coins that cost o(n³) bits of communication but still succeed with at least constant probability against t = Θ(n) adaptive byzantine faults. As such, they for the first time enable setup-free (and even perfectly secure) asynchronous byzantine agreement with o(n³) communication against Θ(n) adaptive byzantine faults.