Asymptotically Optimal Early Termination for Dishonest Majority Broadcast

Deterministic broadcast protocols among n parties tolerating t corruptions require minf + 2, t + 1 rounds, where f ≤ 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 -ε)n. By contrast, the best known algorithm in this regime by Loss and Nielsen (EURO-CRYPT'24) always requires O(minf 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.