{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,15]],"date-time":"2025-02-15T05:14:44Z","timestamp":1739596484755,"version":"3.37.1"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T00:00:00Z","timestamp":1736208000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T00:00:00Z","timestamp":1736208000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100031755","name":"Reichman University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100031755","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Broadcast protocols enable a set of <jats:italic>n<\/jats:italic> parties to agree on the input of a designated sender, even facing attacks by malicious parties. In the honest-majority setting, randomization and cryptography were harnessed to achieve low-communication broadcast with sub-quadratic total communication and balanced sub-linear cost per party. However, comparatively little is known in the dishonest-majority setting. Here, the most communication-efficient constructions are based on Dolev and Strong (SICOMP \u201983), and sub-quadratic broadcast has not been achieved. On the other hand, the only nontrivial <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\omega (n)$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03c9<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> communication lower bounds are restricted to deterministic protocols, or against strong adaptive adversaries that can perform \u201cafter the fact\u201d removal of messages. We provide new communication lower bounds in this space, which hold against arbitrary cryptography and setup assumptions, as well as a simple sub-quadratic broadcast protocol showing near tightness of our first bound.<\/jats:p>","DOI":"10.1007\/s00446-024-00473-5","type":"journal-article","created":{"date-parts":[[2025,1,7]],"date-time":"2025-01-07T16:47:30Z","timestamp":1736268450000},"page":"1-17","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Communication lower bounds for cryptographic broadcast protocols"],"prefix":"10.1007","volume":"38","author":[{"given":"Erica","family":"Blum","sequence":"first","affiliation":[]},{"given":"Elette","family":"Boyle","sequence":"additional","affiliation":[]},{"given":"Ran","family":"Cohen","sequence":"additional","affiliation":[]},{"given":"Chen-Da","family":"Liu-Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,1,7]]},"reference":[{"issue":"2","key":"473_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":"473_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":"473_CR3","doi-asserted-by":"crossref","unstructured":"Boyle, E., Goldwasser, S., Tessaro, S.: Communication locality in secure multi-party computation - how to run sublinear algorithms in a distributed setting. In: Proceedings of the 10th Theory of Cryptography Conference (TCC), pp. 356\u2013376 (2013)","DOI":"10.1007\/978-3-642-36594-2_21"},{"issue":"1","key":"473_CR4","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1145\/2455.214112","volume":"32","author":"D Dolev","year":"1985","unstructured":"Dolev, D., Reischuk, R.: Bounds on information exchange for Byzantine agreement. J. ACM 32(1), 191\u2013204 (1985)","journal-title":"J. ACM"},{"issue":"4","key":"473_CR5","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."},{"key":"473_CR6","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":"1","key":"473_CR7","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/0890-5401(92)90004-Y","volume":"97","author":"BA Coan","year":"1992","unstructured":"Coan, B.A., Welch, J.L.: Modular construction of a Byzantine agreement protocol with optimal message bit complexity. Inf. Comput. 97(1), 61\u201385 (1992)","journal-title":"Inf. Comput."},{"key":"473_CR8","unstructured":"Momose, A., Ren, L.: Optimal communication complexity of authenticated Byzantine agreement. In: Proceedings of the 35th International Symposium on Distributed Computing (DISC), pp. 32\u201313216 (2021)"},{"key":"473_CR9","doi-asserted-by":"crossref","unstructured":"Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. In: Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, pp. 1\u20137 (1983)","DOI":"10.1145\/588058.588060"},{"issue":"1","key":"473_CR10","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/BF01843568","volume":"1","author":"MJ Fischer","year":"1986","unstructured":"Fischer, M.J., Lynch, N.A., Merritt, M.: Easy impossibility proofs for distributed consensus problems. Distrib. Comput. 1(1), 26\u201339 (1986)","journal-title":"Distrib. Comput."},{"issue":"4","key":"473_CR11","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0020-0190(82)90033-3","volume":"14","author":"MJ Fischer","year":"1982","unstructured":"Fischer, M.J., Lynch, N.A.: A lower bound for the time to assure interactive consistency. Inf. Process. Lett. 14(4), 183\u2013186 (1982)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"473_CR12","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0196-6774(82)90004-9","volume":"3","author":"D Dolev","year":"1982","unstructured":"Dolev, D.: The Byzantine generals strike again. J. Algorithms 3(1), 14\u201330 (1982)","journal-title":"J. Algorithms"},{"key":"473_CR13","doi-asserted-by":"crossref","unstructured":"Ben-Or, M.: Another advantage of free choice: Completely asynchronous agreement protocols (extended abstract). In: Proceedings of the 2nd Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 27\u201330 (1983)","DOI":"10.1145\/800221.806707"},{"key":"473_CR14","doi-asserted-by":"crossref","unstructured":"Rabin, M.O.: Randomized Byzantine generals. In: Proceedings of the 24th Annual Symposium on Foundations of Computer Science (FOCS), pp. 403\u2013409 (1983)","DOI":"10.1109\/SFCS.1983.48"},{"key":"473_CR15","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J., Sanwalani, V., Vee, E.: Scalable leader election. In: Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 990\u2013999 (2006)","DOI":"10.1145\/1109557.1109667"},{"key":"473_CR16","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J.: From almost everywhere to everywhere: Byzantine agreement with \u00f5(n3\/2) bits. In: Proceedings of the 23th International Symposium on Distributed Computing (DISC), pp. 464\u2013478 (2009)","DOI":"10.1007\/978-3-642-04355-0_47"},{"key":"473_CR17","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J.: Breaking the O(n2) bit barrier: scalable Byzantine agreement with an adaptive adversary. J. ACM 58(4), 18\u201311824 (2011). A preliminary version appeared at PODC\u201910","DOI":"10.1145\/1989727.1989732"},{"key":"473_CR18","doi-asserted-by":"crossref","unstructured":"Braud-Santoni, N., Guerraoui, R., Huc, F.: Fast Byzantine agreement. In: Proceedings of the 32th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 57\u201364 (2013)","DOI":"10.1145\/2484239.2484243"},{"key":"473_CR19","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. Theoret. Comput. Sci. 777, 155\u2013183 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"473_CR20","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 38th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 317\u2013326 (2019)","DOI":"10.1145\/3293611.3331629"},{"key":"473_CR21","doi-asserted-by":"crossref","unstructured":"Cohen, S., Keidar, I., Spiegelman, A.: Not a COINcidence: Sub-quadratic asynchronous Byzantine agreement WHP. In: Proceedings of the 34th International Symposium on Distributed Computing (DISC), pp. 25\u201312517 (2020)","DOI":"10.1145\/3382734.3405708"},{"key":"473_CR22","doi-asserted-by":"crossref","unstructured":"Blum, E., Katz, J., Liu-Zhang, C., Loss, J.: Asynchronous Byzantine agreement with subquadratic communication. In: Proceedings of the 18th Theory of Cryptography Conference (TCC), Part I, pp. 353\u2013380 (2020)","DOI":"10.1007\/978-3-030-64375-1_13"},{"key":"473_CR23","doi-asserted-by":"crossref","unstructured":"Boyle, E., Cohen, R., Goel, A.: Breaking the O($$\\surd $$n)-bit barrier: Byzantine agreement with polylog bits per party. In: Proceedings of the 40th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 319\u2013330 (2021)","DOI":"10.1145\/3465084.3467897"},{"key":"473_CR24","doi-asserted-by":"crossref","unstructured":"Chan, T.-H., Pass, R., Shi, E.: Sublinear-round Byzantine agreement under corrupt majority. In: Proceedings of the 23rd International Conference on the Theory and Practice of Public-Key Cryptography (PKC), Part II, pp. 246\u2013265 (2020)","DOI":"10.1007\/978-3-030-45388-6_9"},{"key":"473_CR25","doi-asserted-by":"crossref","unstructured":"Tsimos, G., Loss, J., Papamanthou, C.: Gossiping for communication-efficient broadcast. In: 42nd Annual International Cryptology Conference (CRYPTO), Part III, pp. 439\u2013469 (2022)","DOI":"10.1007\/978-3-031-15982-4_15"},{"issue":"2","key":"473_CR26","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":"473_CR27","doi-asserted-by":"crossref","unstructured":"Micali, S., Rabin, M.O., Vadhan, S.P.: Verifiable random functions. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), pp. 120\u2013130 (1999)","DOI":"10.1109\/SFFCS.1999.814584"},{"key":"473_CR28","doi-asserted-by":"crossref","unstructured":"Hirt, M., Zikas, V.: Adaptively secure broadcast. In: 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), pp. 466\u2013485 (2010)","DOI":"10.1007\/978-3-642-13190-5_24"},{"key":"473_CR29","doi-asserted-by":"crossref","unstructured":"Garay, J.A., Katz, J., Kumaresan, R., Zhou, H.: Adaptively secure broadcast, revisited. In: Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 179\u2013186 (2011)","DOI":"10.1145\/1993806.1993832"},{"key":"473_CR30","doi-asserted-by":"crossref","unstructured":"Cohen, R., Garay, J.A., Zikas, V.: Completeness theorems for adaptively secure broadcast. In: 43rd Annual International Cryptology Conference (CRYPTO), Part I, pp. 3\u201338 (2023)","DOI":"10.1007\/978-3-031-38557-5_1"},{"key":"473_CR31","unstructured":"Micali, S.: Very simple and efficient Byzantine agreement. In: Proceedings of the 8th Annual Innovations in Theoretical Computer Science (ITCS) Conference, pp. 6\u2013161 (2017)"},{"key":"473_CR32","doi-asserted-by":"crossref","unstructured":"Fitzi, M., Liu-Zhang, C., Loss, J.: A new way to achieve round-efficient Byzantine agreement. In: Proceedings of the 40th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 355\u2013362 (2021)","DOI":"10.1145\/3465084.3467907"},{"key":"473_CR33","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":"473_CR34","unstructured":"Fernando, R., Gelles, Y., Komargodski, I.: Scalable distributed agreement from LWE: Byzantine agreement, broadcast, and leader election. In: Proceedings of the 15th Annual Innovations in Theoretical Computer Science (ITCS) Conference. LIPIcs, vol. 287, pp. 46\u201314623. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2024)"},{"key":"473_CR35","doi-asserted-by":"crossref","unstructured":"Boyle, E., Cohen, R., Data, D., Hub\u00e1\u010dek, P.: Must the communication graph of MPC protocols be an expander? In: 38th Annual International Cryptology Conference (CRYPTO), Part III, pp. 243\u2013272 (2018)","DOI":"10.1007\/978-3-319-96878-0_9"},{"key":"473_CR36","doi-asserted-by":"crossref","unstructured":"Garay, J.A., Moses, Y.: Fully polynomial Byzantine agreement in t+1 rounds. In: Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC), pp. 31\u201341 (1993)","DOI":"10.1145\/167088.167101"},{"issue":"4","key":"473_CR37","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539790187084","volume":"26","author":"P Feldman","year":"1997","unstructured":"Feldman, P., Micali, S.: An optimal probabilistic protocol for synchronous Byzantine agreement. SIAM J. Comput. 26(4), 873\u2013933 (1997)","journal-title":"SIAM J. Comput."},{"key":"473_CR38","doi-asserted-by":"crossref","unstructured":"Fitzi, M., Garay, J.A.: Efficient player-optimal protocols for strong and differential consensus. In: Proceedings of the 22th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 211\u2013220 (2003)","DOI":"10.1145\/872035.872066"},{"key":"473_CR39","doi-asserted-by":"crossref","unstructured":"Katz, J., Koo, C.: On expected constant-round protocols for Byzantine agreement. In: 25th Annual International Cryptology Conference (CRYPTO), pp. 445\u2013462 (2006)","DOI":"10.1007\/11818175_27"},{"key":"473_CR40","doi-asserted-by":"crossref","unstructured":"Garay, J.A., Katz, J., Koo, C.-Y., Ostrovsky, R.: Round complexity of authenticated broadcast with a dishonest majority. In: Proceedings of the 48th Annual Symposium on Foundations of Computer Science (FOCS), pp. 658\u2013668 (2007)","DOI":"10.1109\/FOCS.2007.44"},{"key":"473_CR41","doi-asserted-by":"crossref","unstructured":"Fitzi, M., Nielsen, J.B.: On the number of synchronous rounds sufficient for authenticated Byzantine agreement. In: Proceedings of the 23th International Symposium on Distributed Computing (DISC), pp. 449\u2013463 (2009)","DOI":"10.1007\/978-3-642-04355-0_46"},{"key":"473_CR42","doi-asserted-by":"crossref","unstructured":"Wan, J., Xiao, H., Shi, E., Devadas, S.: Expected constant round byzantine broadcast under dishonest majority. In: Proceedings of the 18th Theory of Cryptography Conference (TCC), Part I, pp. 381\u2013411 (2020)","DOI":"10.1007\/978-3-030-64375-1_14"},{"key":"473_CR43","doi-asserted-by":"crossref","unstructured":"Wan, J., Xiao, H., Devadas, S., Shi, E.: Round-efficient Byzantine broadcast under strongly adaptive and majority corruptions. In: Proceedings of the 18th Theory of Cryptography Conference (TCC), Part I, pp. 412\u2013456 (2020)","DOI":"10.1007\/978-3-030-64375-1_15"},{"key":"473_CR44","doi-asserted-by":"crossref","unstructured":"Srinivasan, S., Loss, J., Malavolta, G., Nayak, K., Papamanthou, C., Thyagarajan, S.A.K.: Transparent batchable time-lock puzzles and applications to Byzantine consensus. In: Proceedings of the 26th International Conference on the Theory and Practice of Public-Key Cryptography (PKC), Part I, pp. 554\u2013584 (2023)","DOI":"10.1007\/978-3-031-31368-4_20"},{"key":"473_CR45","doi-asserted-by":"crossref","unstructured":"Pfitzmann, B., Waidner, M.: Unconditional Byzantine agreement for any number of faulty processors. In: Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science (STACS), pp. 339\u2013350 (1992)","DOI":"10.1007\/3-540-55210-3_195"},{"key":"473_CR46","doi-asserted-by":"crossref","unstructured":"Beaver, D.: Precomputing oblivious transfer. In: 14th Annual International Cryptology Conference (CRYPTO), pp. 97\u2013109 (1995)","DOI":"10.1007\/3-540-44750-4_8"},{"key":"473_CR47","unstructured":"Feldman, P.: Optimal algorithms for Byzantine agreement. PhD thesis, Stanford University (1988). https:\/\/dspace.mit.edu\/handle\/1721.1\/14368"},{"key":"473_CR48","doi-asserted-by":"crossref","unstructured":"Canetti, R., Feige, U., Goldreich, O., Naor, M.: Adaptively secure multi-party computation. In: Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC), pp. 639\u2013648 (1996)","DOI":"10.1145\/237814.238015"},{"key":"473_CR49","doi-asserted-by":"crossref","unstructured":"Canetti, R.: Universally composable security: A new paradigm for cryptographic protocols. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 136\u2013145 (2001)","DOI":"10.1109\/SFCS.2001.959888"},{"key":"473_CR50","doi-asserted-by":"crossref","unstructured":"Hofheinz, D., Jager, T.: Verifiable random functions from standard assumptions. In: Proceedings of the 13th Theory of Cryptography Conference(TCC 2016-A), Part I, pp. 336\u2013362 (2016)","DOI":"10.1007\/978-3-662-49096-9_14"},{"key":"473_CR51","doi-asserted-by":"crossref","unstructured":"Liu-Zhang, C.-D., Matt, C., Maurer, U., Rito, G., Thomsen, S.E.: Practical provably secure flooding for blockchains. In: 28th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), Part I, pp. 774\u2013805 (2022)","DOI":"10.1007\/978-3-031-22963-3_26"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-024-00473-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-024-00473-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-024-00473-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,14]],"date-time":"2025-02-14T11:39:54Z","timestamp":1739533194000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-024-00473-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,7]]},"references-count":51,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["473"],"URL":"https:\/\/doi.org\/10.1007\/s00446-024-00473-5","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2025,1,7]]},"assertion":[{"value":"19 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}