Subcubic Coin Tossing in Asynchrony without PKI

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 a committee-based method to transform strong (rarely failing) binary common coins into weaker ones that asymptotically require less communication. For any $k>2$ and $\epsilon >0$, we can transform a strong binary coin that costs $\tilde{O}(n^k)$ bits of communication into a weak binary coin that costs $\tilde{O}({\epsilon }^{-2k}{n}^{3-2/k})$ bits. This latter coin tolerates $\epsilon n$ fewer byzantine parties than the strong coin it is based on, and it fails with an arbitrarily small constant probability. With our method, we obtain a secure-channel-based perfectly secure coin for $t\le (\frac{1}{4}-\epsilon )n$ faults that costs $\tilde{O}(n^{2.5})$ bits, as well as a coin based on cryptographic hashing for $t\le (\frac{1}{3}-\epsilon )n$ faults that costs $\tilde{O}(n^{7/3}\hat{I}º)$ bits. These are to our knowledge the first PKI-free asynchronous common coins that cost $o(n^3)$ bits of communication but still succeed with at least constant probability against $t=\hat{I}˜(n)$ adaptive byzantine faults.

20 pages, full version of a PODC 2026 brief announcement