Scalable distributed agreement from LWE: Byzantine agreement, broadcast, and leader election

Distributed agreement is a general name for the task of ensuring consensus among non-faulty nodes in the presence of faulty or malicious behavior. Well-known instances of agreement tasks are Byzantine Agreement, Broadcast, and Committee or Leader Election. Since agreement tasks lie at the heart of many modern distributed applications, there has been an increased interest in designing scalable protocols for these tasks. Specifically, we want protocols where the per-party communication complexity scales sublinearly with the number of parties. With unconditional security, the state of the art protocols have $\tilde{O}\left(\sqrt{n}\right)$ per-party communication and $\tilde{O}\left(1\right)$ rounds, where n stands for the number of parties, tolerating $1/3-ϵ$ fraction of corruptions for any $ϵ>0$ . There are matching lower bounds showing that these protocols are essentially optimal among a large class of protocols. Recently, Boyle-Cohen-Goel (PODC '21, Journal of Cryptology '24) relaxed the attacker to be computationally bounded and using strong cryptographic assumptions showed a protocol with $\tilde{O}\left(1\right)$ per-party communication and rounds (similarly, tolerating $1/3-ϵ$ fraction of corruptions). The security of their protocol relies on SNARKs for NP with linear-time extraction, a somewhat strong and non-standard assumption. Their protocols further rely on a public-key infrastructure (PKI) and a common-reference-string (CRS). In this work, we present a new synchronous protocol with $\tilde{O}\left(1\right)$ per-party communication and rounds but relying only on the standard Learning With Errors (LWE) assumption. Our protocol also relies on a PKI and a CRS, and tolerates $1/3-ϵ$ fraction of corruptions, similarly to Boyle et al. Technically, we leverage (multi-hop) BARGs for NP directly and in a generic manner that significantly deviates from the framework of Boyle et al.