{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T09:58:11Z","timestamp":1790848691099,"version":"4.1.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T00:00:00Z","timestamp":1790812800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["HR001120C0086"],"award-info":[{"award-number":["HR001120C0086"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N000142212064"],"award-info":[{"award-number":["N000142212064"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["2128519"],"award-info":[{"award-number":["2128519"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2020643"],"award-info":[{"award-number":["2020643"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1774\/20"],"award-info":[{"award-number":["1774\/20"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["101162665"],"award-info":[{"award-number":["101162665"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2026,12]]},"abstract":"Abstract<\/jats:title>\n \n 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\n scalable<\/jats:italic>\n 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\n \n \n $${\\tilde{O}}(\\sqrt{n})$$<\/jats:tex-math>\n \n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n \n n<\/mml:mi>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n per-party communication and\n \n \n $${\\tilde{O}}(1)$$<\/jats:tex-math>\n \n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n rounds, where\n n<\/jats:italic>\n stands for the number of parties, tolerating\n \n \n $$1\/3-\\epsilon $$<\/jats:tex-math>\n \n \n 1<\/mml:mn>\n \/<\/mml:mo>\n 3<\/mml:mn>\n -<\/mml:mo>\n \u03f5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n fraction of corruptions for any\n \n \n $$\\epsilon >0$$<\/jats:tex-math>\n \n \n \u03f5<\/mml:mi>\n ><\/mml:mo>\n 0<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . There are matching lower bounds showing that these protocols are essentially optimal among a large class of protocols. Recently, Boyle-Cohen-Goel (PODC \u201921, Journal of Cryptology \u201924) relaxed the attacker to be computationally bounded and using strong cryptographic assumptions showed a protocol with\n \n \n $${\\tilde{O}}(1)$$<\/jats:tex-math>\n \n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n per-party communication and rounds (similarly, tolerating\n \n \n $$1\/3-\\epsilon $$<\/jats:tex-math>\n \n \n 1<\/mml:mn>\n \/<\/mml:mo>\n 3<\/mml:mn>\n -<\/mml:mo>\n \u03f5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n 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\n \n \n $${\\tilde{O}}(1)$$<\/jats:tex-math>\n \n \n \n O<\/mml:mi>\n ~<\/mml:mo>\n <\/mml:mover>\n \n (<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n 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\n \n \n $$1\/3-\\epsilon $$<\/jats:tex-math>\n \n \n 1<\/mml:mn>\n \/<\/mml:mo>\n 3<\/mml:mn>\n -<\/mml:mo>\n \u03f5<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n 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.\n <\/jats:p>","DOI":"10.1007\/s00446-026-00519-w","type":"journal-article","created":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T09:22:39Z","timestamp":1790846559000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Scalable distributed agreement from LWE: Byzantine agreement, broadcast, and leader election"],"prefix":"10.1007","volume":"39","author":[{"given":"Rex","family":"Fernando","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yuval","family":"Gelles","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ilan","family":"Komargodski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,10,1]]},"reference":[{"issue":"2","key":"519_CR1","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1145\/322186.322188","volume":"27","author":"MC Pease","year":"1980","unstructured":"Pease, M.C., Shostak, R.E., Lamport, L.: Reaching agreement in the presence of faults. J. ACM 27(2), 228\u2013234 (1980)","journal-title":"J. ACM"},{"issue":"3","key":"519_CR2","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L Lamport","year":"1982","unstructured":"Lamport, L., Shostak, R.E., Pease, M.C.: The byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382\u2013401 (1982)","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"519_CR3","doi-asserted-by":"crossref","unstructured":"Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: Scaling byzantine agreements for cryptocurrencies. In: Proceedings of the 26th Symposium on Operating Systems Principles. SOSP, pp. 51\u201368. ACM, Shanghai, China (2017)","DOI":"10.1145\/3132747.3132757"},{"key":"519_CR4","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.tcs.2019.02.001","volume":"777","author":"J Chen","year":"2019","unstructured":"Chen, J., Micali, S.: Algorand: a secure and efficient distributed ledger. Theor. Comput. Sci. 777, 155\u2013183 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"519_CR5","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or A completeness theorem for protocols with honest majority. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, STOC, pp. 218\u2013229. (1987)","DOI":"10.1145\/28395.28420"},{"key":"519_CR6","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC, pp. 1\u201310. (1988)","DOI":"10.1145\/62212.62213"},{"key":"519_CR7","doi-asserted-by":"crossref","unstructured":"Chaum, D., Cr\u00e9peau, C., Damg\u00e5rd, I.: Multiparty unconditionally secure protocols (abstract). In: Advances in Cryptology - CRYPTO, vol. 293, p. 462 (1987)","DOI":"10.1007\/3-540-48184-2_43"},{"key":"519_CR8","doi-asserted-by":"crossref","unstructured":"Rabin, T., Ben-Or, M.: Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, STOC, pp. 73\u201385. (1989)","DOI":"10.1145\/73007.73014"},{"key":"519_CR9","doi-asserted-by":"crossref","unstructured":"Devadas, L., Goyal, R., Kalai, Y., Vaikuntanathan, V.: Rate-1 non-interactive arguments for batch-np and applications. In: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), IEEE, pp. 1057\u20131068. (2022)","DOI":"10.1109\/FOCS54457.2022.00103"},{"key":"519_CR10","doi-asserted-by":"crossref","unstructured":"Paneth, O., Pass, R.: Incrementally verifiable computation via rate-1 batch arguments. In: 63rd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 1045\u20131056. (2022)","DOI":"10.1109\/FOCS54457.2022.00102"},{"key":"519_CR11","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J., Sanwalani, V., Vee, E.: Scalable leader election. In: 17th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 990\u2013999. (2006)","DOI":"10.1145\/1109557.1109667"},{"key":"519_CR12","doi-asserted-by":"crossref","unstructured":"King, V., Lonargan, S., Saia, J., Trehan, A.: Load balanced scalable byzantine agreement through quorum building, with full information. In: Distributed Computing and Networking - ICDCN, pp. 203\u2013214. (2011)","DOI":"10.1007\/978-3-642-17679-1_18"},{"issue":"4","key":"519_CR13","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/0212045","volume":"12","author":"D Dolev","year":"1983","unstructured":"Dolev, D., Strong, H.R.: Authenticated algorithms for byzantine agreement. SIAM J. Comput. 12(4), 656\u2013666 (1983)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"519_CR14","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1145\/42282.42283","volume":"35","author":"C Dwork","year":"1988","unstructured":"Dwork, C., Lynch, N.A., Stockmeyer, L.J.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288\u2013323 (1988)","journal-title":"J. ACM"},{"key":"519_CR15","unstructured":"Castro, M., Liskov, B.: Practical byzantine fault tolerance. In: Proceedings of the Third USENIX Symposium on Operating Systems Design and Implementation, (OSDI), pp. 173\u2013186. (1999)"},{"key":"519_CR16","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J.: From almost everywhere to everywhere: Byzantine agreement with \u00f5($${\\rm n}^{\\text{3\/2}}$$) bits. In: Distributed Computing, 23rd International Symposium, DISC, pp. 464\u2013478. (2009)","DOI":"10.1007\/978-3-642-04355-0_47"},{"key":"519_CR17","doi-asserted-by":"crossref","unstructured":"Braud-Santoni, N., Guerraoui, R., Huc, F.: Fast byzantine agreement. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 57\u201364. (2013)","DOI":"10.1145\/2484239.2484243"},{"key":"519_CR18","doi-asserted-by":"crossref","unstructured":"Abraham, I., Chan, T.-H., Dolev, D., Nayak, K., Pass, R., Ren, L., Shi, E.: Communication complexity of byzantine agreement, revisited. In: Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC, pp. 317\u2013326. (2019)","DOI":"10.1145\/3293611.3331629"},{"key":"519_CR19","doi-asserted-by":"crossref","unstructured":"Gelles, Y., Komargodski, I.: Optimal load-balanced scalable distributed agreement. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC, pp. 411\u2013422. (2024)","DOI":"10.1145\/3618260.3649736"},{"key":"519_CR20","unstructured":"Gelles, Y., Komargodski, I.: Brief announcement: Scalable agreement protocols with optimal optimistic efficiency. In: Distributed Computing, 37th International Symposium, DISC, pp. 42:1\u201342:6 (2023)"},{"issue":"4","key":"519_CR21","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s00446-008-0069-x","volume":"21","author":"D Holtby","year":"2008","unstructured":"Holtby, D., Kapron, B.M., King, V.: Lower bound for scalable byzantine agreement. Distributed Comput. 21(4), 239\u2013248 (2008)","journal-title":"Distributed Comput."},{"key":"519_CR22","doi-asserted-by":"crossref","unstructured":"Boyle, E., Cohen, R., Goel, A.: Breaking the O($$\\sqrt{n}$$)-bit barrier: Byzantine agreement with polylog bits per party. In: ACM Symposium on Principles of Distributed Computing, PODC, pp. 319\u2013330. (2021)","DOI":"10.1145\/3465084.3467897"},{"issue":"1","key":"519_CR23","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1007\/S00145-023-09484-0","volume":"37","author":"E Boyle","year":"2024","unstructured":"Boyle, E., Cohen, R., Goel, A.: Breaking the $${O}(\\sqrt{n})$$-bit barrier: Byzantine agreement with polylog bits per party. J. Cryptol. 37(1), 2 (2024). https:\/\/doi.org\/10.1007\/S00145-023-09484-0","journal-title":"J. Cryptol."},{"key":"519_CR24","doi-asserted-by":"crossref","unstructured":"Naor, M.: On cryptographic assumptions and challenges. In: Advances in Cryptology - CRYPTO, pp. 96\u2013109. (2003)","DOI":"10.1007\/978-3-540-45146-4_6"},{"key":"519_CR25","doi-asserted-by":"crossref","unstructured":"Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC, pp. 99\u2013108. (2011)","DOI":"10.1145\/1993636.1993651"},{"key":"519_CR26","unstructured":"Choudhuri, A.R., Jain, A., Jin, Z.: SNARGs for P from LWE. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 68\u201379. (2021)"},{"key":"519_CR27","doi-asserted-by":"crossref","unstructured":"Choudhuri, A.R., Jain, A., Jin, Z.: Non-interactive batch arguments for NP from standard assumptions. In: Advances in Cryptology - CRYPTO, pp. 394\u2013423. (2021)","DOI":"10.1007\/978-3-030-84259-8_14"},{"key":"519_CR28","doi-asserted-by":"crossref","unstructured":"Jawale, R., Kalai, Y.T., Khurana, D., Zhang, R.Y.: SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE. In: Proceedings of the 53rd Annual ACM Symposium on Theory of Computing, STOC, pp. 708\u2013721. (2021)","DOI":"10.1145\/3406325.3451055"},{"key":"519_CR29","doi-asserted-by":"crossref","unstructured":"Kalai, Y.T., Paneth, O., Yang, L.: Delegation with updatable unambiguous proofs and PPAD-hardness. In: Advances in Cryptology - CRYPTO, pp. 652\u2013673. (2020)","DOI":"10.1007\/978-3-030-56877-1_23"},{"key":"519_CR30","doi-asserted-by":"crossref","unstructured":"Waters, B., Wu, D.J.: Batch arguments for NP and more from standard bilinear group assumptions. In: Advances in Cryptology - CRYPTO, pp. 433\u2013463. (2022)","DOI":"10.1007\/978-3-031-15979-4_15"},{"key":"519_CR31","doi-asserted-by":"crossref","unstructured":"Kalai, Y., Lombardi, A., Vaikuntanathan, V., Wichs, D.: Boosting batch arguments and RAM delegation. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC, pp. 1545\u20131552. (2023)","DOI":"10.1145\/3564246.3585200"},{"key":"519_CR32","doi-asserted-by":"crossref","unstructured":"Hulett, J., Jawale, R., Khurana, D., Srinivasan, A.: SNARGs for P from sub-exponential DDH and QR. In: Advances in Cryptology - EUROCRYPT, pp. 520\u2013549. (2022)","DOI":"10.1007\/978-3-031-07085-3_18"},{"key":"519_CR33","doi-asserted-by":"crossref","unstructured":"Garg, R., Sheridan, K., Waters, B., Wu, D.J.: Fully succinct batch arguments for NP from indistinguishability obfuscation. In: Theory of Cryptography - TCC, pp. 526\u2013555. (2022)","DOI":"10.1007\/978-3-031-22318-1_19"},{"key":"519_CR34","doi-asserted-by":"crossref","unstructured":"Naor, M., Yung, M.: Universal one-way hash functions and their cryptographic applications. In: 21st Annual ACM Symposium on Theory of Computing, STOC, pp. 33\u201343. (1989)","DOI":"10.1145\/73007.73011"},{"key":"519_CR35","doi-asserted-by":"crossref","unstructured":"Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: 22nd Annual ACM Symposium on Theory of Computing, STOC, pp. 387\u2013394. (1990)","DOI":"10.1145\/100216.100269"},{"key":"519_CR36","doi-asserted-by":"crossref","unstructured":"Hub\u00e1cek, P., Wichs, D.: On the communication complexity of secure function evaluation with long output. In: 6th Innovations in Theoretical Computer Science Conference, ITCS, pp. 163\u2013172. (2015)","DOI":"10.1145\/2688073.2688105"},{"key":"519_CR37","doi-asserted-by":"crossref","unstructured":"Berman, P., Garay, J.A., Perry, K.J.: Bit optimal distributed consensus. Computer Science Research, pp. 313\u2013322. (1992)","DOI":"10.1007\/978-1-4615-3422-8_27"},{"issue":"6","key":"519_CR38","doi-asserted-by":"publisher","first-page":"34:1","DOI":"10.1145\/1568318.1568324","volume":"56","author":"O Regev","year":"2009","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56(6), 34:1-34:40 (2009)","journal-title":"J. ACM"},{"key":"519_CR39","doi-asserted-by":"crossref","unstructured":"Bhangale, A., Liu-Zhang, C.-D., Loss, J., Nayak, K., Yandamuri, S.: Leader election with poly-logarithmic communication per party. In: Advances in Cryptology - CRYPTO 2025, pp. 37\u201368 (2025)","DOI":"10.1007\/978-3-032-01878-6_2"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-026-00519-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-026-00519-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-026-00519-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,1]],"date-time":"2026-10-01T09:22:56Z","timestamp":1790846576000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-026-00519-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,10,1]]},"references-count":39,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2026,12]]}},"alternative-id":["519"],"URL":"https:\/\/doi.org\/10.1007\/s00446-026-00519-w","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,10,1]]},"assertion":[{"value":"3 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 September 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 October 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare no competing interests.","order":1,"name":"Ethics","label":"Conflict of interest","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"A preliminary version of this work was published in the proceedings of the 15th Innovations in Theoretical Computer Science (ITCS 2024).","order":2,"name":"Ethics","label":"Consent for publication","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"27"}}