Paper 2024/1656

Optimal Early Termination for Dishonest Majority Broadcast

Abstract

Deterministic broadcast protocols among $n$ parties tolerating $t$ corruptions require $\min\{f+2, t+1\}$ rounds, where $f \le t$ is the actual number of corruptions in an execution of the protocol. We provide the first protocol which is optimally resilient, adaptively secure, and asymptotically matches this lower bound for any $t<(1-\varepsilon)n$. By contrast, the best known algorithm in this regime by Loss and Nielsen (EUROCRYPT'24) always requires $O(\min\{f^2, t\})$ rounds. Our main technical tool is a generalization of the notion of polarizer introduced by Loss and Nielsen, which allows parties to obtain transferable cryptographic evidence of missing messages with fewer rounds of interaction.