Balanced and Adaptively Secure Asynchronous Common Coin and Byzantine Agreement With Sub-Quadratic Communication

본문 미리보기

Distributed common randomness generation (i.e., the common coin problem) is a cornerstone of randomized distributed computing. While a long line of research has sought scalable solutions, the asynchronous setting remains a challenge. Specifically, while Blum et al. (TCC'21) achieved sub-quadratic communication complexity, their approach lacks ``balance'': certain nodes must still send $\Omega(n)$ messages, creating a scalability bottleneck. Furthermore, their solution only tolerates a $1/3 - \ep