Asymptotically Optimal Early Termination for Dishonest Majority Broadcast
摘要
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.