{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,11]],"date-time":"2025-09-11T21:04:42Z","timestamp":1757624682631,"version":"3.44.0"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783032018779"},{"type":"electronic","value":"9783032018786"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-032-01878-6_4","type":"book-chapter","created":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T18:08:50Z","timestamp":1755367730000},"page":"101-134","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Nearly Optimal Parallel Broadcast in\u00a0the\u00a0Plain Public Key Model"],"prefix":"10.1007","author":[{"given":"Ran","family":"Gelles","sequence":"first","affiliation":[]},{"given":"Christoph","family":"Lenzen","sequence":"additional","affiliation":[]},{"given":"Julian","family":"Loss","sequence":"additional","affiliation":[]},{"given":"Sravya","family":"Yandamuri","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,17]]},"reference":[{"key":"4_CR1","doi-asserted-by":"publisher","unstructured":"Abraham, I., Asharov, G., Patil, S., Patra, A.: Asymptotically free broadcast in constant expected time via packed VSS. In: Kiltz, E., Vaikuntanathan, V. (eds.) TCC 2022. Part I, volume 13747 of LNCS, pp. 384\u2013414. Springer, Heidelberg (2022). https:\/\/doi.org\/10.1007\/978-3-031-22318-1_14","DOI":"10.1007\/978-3-031-22318-1_14"},{"key":"4_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., et al.: Communication complexity of byzantine agreement. In: Robinson, P., Ellen, F., (eds.) 38th ACM PODC, pp. 317\u2013326. ACM (2019)","DOI":"10.1145\/3293611.3331629"},{"key":"4_CR3","unstructured":"Abraham, I., Nayak, K., Shrestha, N.: Communication and round efficient parallel broadcast protocols. In: IACR Cryptol, pp. 1172 (2023). ePrint Arch."},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Asharov, G., Chandramouli, A.: Perfect (parallel) broadcast in constant expected rounds via statistical VSS. In: EUROCRYPT (to appear), pp. 376 (2024)","DOI":"10.1007\/978-3-031-58740-5_11"},{"key":"4_CR5","doi-asserted-by":"publisher","unstructured":"Berman, P., Garay, J., Perry, K.J.: Bit optimal distributed consensus. In: Computer Science, pp. 313\u2013321. Springer (1992). https:\/\/doi.org\/10.1007\/978-1-4615-3422-8_27","DOI":"10.1007\/978-1-4615-3422-8_27"},{"key":"4_CR6","doi-asserted-by":"publisher","unstructured":"Blum, E., Katz, J., Liu-Zhang, C.-D., Loss, J.: Asynchronous byzantine agreement with subquadratic communication. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. Part I, volume 12550 of LNCS, pp. 353\u2013380. Springer, Heidelberg (2020). https:\/\/doi.org\/10.1007\/978-3-030-64375-1_13","DOI":"10.1007\/978-3-030-64375-1_13"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd FOCS, pp. 136\u2013145. IEEE Computer Society Press (2001)","DOI":"10.1109\/SFCS.2001.959888"},{"key":"4_CR8","unstructured":"Castro, M., Liskov, B.: Practical byzantine fault tolerance. In: Seltzer, M.I., Leach, P.J. (eds.) Proceedings of the Third USENIX Symposium on Operating Systems Design and Implementation (OSDI), New Orleans, Louisiana, USA, February 22\u201325, 1999, pp. 173\u2013186. USENIX Association (1999)"},{"key":"4_CR9","doi-asserted-by":"publisher","unstructured":"Chan, T.-H.H., Pass, R., Shi, E.: Sublinear-round byzantine agreement under corrupt majority. In: Kiayias, A., Kohlweiss, M., Wallden, P., Zikas, V. (eds.) PKC 2020. LNCS, vol. 12111, pp. 246\u2013265. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45388-6_9","DOI":"10.1007\/978-3-030-45388-6_9"},{"key":"4_CR10","doi-asserted-by":"crossref","unstructured":"Civit, P., Dzulfikar, M.A., Gilbert, S., Guerraoui, R., Komatovic, J., Vidigueira, M.: DARE to agree: byzantine agreement with optimal resilience and adaptive communication. In: ACM PODC. ACM (2024)","DOI":"10.1145\/3662158.3662792"},{"issue":"1","key":"4_CR11","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":"4_CR12","unstructured":"Collins, D., Duan, S., Loss, J., Papamanthou, C., Tsimos, G., Wang, H.: Towards optimal parallel broadcast under a dishonest majority. Cryptology ePrint Archive, Report 2024\/974 (2024)"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Dolev, D., Reischuk, R.: Bounds on information exchange for byzantine agreement. In: Probert, R.L., Fischer, M.J., Santoro, N. (eds.) 1st ACM PODC, pp. 132\u2013140. ACM (1982)","DOI":"10.1145\/800220.806690"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Dolev, D., Strong, H.R.: Polynomial algorithms for multiple processor agreement. In: 14th ACM STOC, pp. 401\u2013407. ACM Press (1982)","DOI":"10.1145\/800070.802215"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Dolev, D., Yao, A.C.: On the security of public key protocols (extended abstract). In: 22nd FOCS, pp. 350\u2013357. IEEE Computer Society Press (1981)","DOI":"10.1109\/SFCS.1981.32"},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Feldman, P., Micali, S.: Optimal algorithms for byzantine agreement. In: 20th ACM STOC, pp. 148\u2013161. ACM Press (1988)","DOI":"10.1145\/62212.62225"},{"key":"4_CR17","doi-asserted-by":"publisher","unstructured":"Fitzi, M., Nielsen, J.B.: On the number of synchronous rounds sufficient for authenticated byzantine agreement. In: Keidar, I. (ed.) DISC 2009. LNCS, vol. 5805, pp. 449\u2013463. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-04355-0_46","DOI":"10.1007\/978-3-642-04355-0_46"},{"key":"4_CR18","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: 48th FOCS, pp. 658\u2013668. IEEE Computer Society Press (2007)","DOI":"10.1109\/FOCS.2007.44"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"Garay, J.A., Moses, Y.: Fully polynomial byzantine agreement in t+1 rounds. In: 25th ACM STOC, pp. 31\u201341. ACM Press (1993)","DOI":"10.1145\/167088.167101"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Gelles, R., Lenzen, C., Loss, J., Yandamuri, S.: Nearly optimal parallel broadcast in the plain public key model. Cryptology ePrint Archive, Paper 2025\/1012 (2025)","DOI":"10.1007\/978-3-032-01878-6_4"},{"key":"4_CR21","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, Shanghai, China, October 28\u201331, 2017, pp. 51\u201368. ACM (2017)","DOI":"10.1145\/3132747.3132757"},{"issue":"2","key":"4_CR22","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/0217017","volume":"17","author":"S Goldwasser","year":"1988","unstructured":"Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281\u2013308 (1988)","journal-title":"SIAM J. Comput."},{"key":"4_CR23","doi-asserted-by":"publisher","unstructured":"Katz, J., Koo, C.-Y.: On expected constant-round protocols for byzantine agreement. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 445\u2013462. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11818175_27","DOI":"10.1007\/11818175_27"},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J.: Breaking the $$O(n^2)$$ bit barrier: scalable byzantine agreement with an adaptive adversary. In: Richa, A.W., Guerraoui, R. (eds.) 29th ACM PODC, pp. 420\u2013429. ACM (2010)","DOI":"10.1145\/1835698.1835798"},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J., Sanwalani, V., Vee, E.: Scalable leader election. In: 17th SODA, pp. 990\u2013999. ACM-SIAM (2006)","DOI":"10.1145\/1109557.1109667"},{"key":"4_CR26","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Nisan, N.: Communication Complexity. Cambridge University Press (1996)","DOI":"10.1017\/CBO9780511574948"},{"key":"4_CR27","unstructured":"Micali, S.: Very simple and efficient byzantine agreement. In: Papadimitriou, C.H. (ed.) ITCS 2017, volume 4266, pp. 1\u2013 67. LIPIcs (2017)"},{"key":"4_CR28","unstructured":"Momose, A., Ren, L.: Optimal communication complexity of authenticated byzantine agreement. arXiv preprint arXiv:2007.13175 (2020)"},{"key":"4_CR29","unstructured":"Momose, A., Ren, L.: Optimal communication complexity of authenticated byzantine agreement. In: Gilbert, S. (ed.) 35th International Symposium on Distributed Computing, DISC 2021, October 4\u20138, 2021, Freiburg, Germany (Virtual Conference), volume 209 of LIPIcs, pp. 32:1\u201332:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2021)"},{"issue":"2","key":"4_CR30","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"},{"key":"4_CR31","doi-asserted-by":"publisher","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: Boldyreva, A., Kolesnikov, V. (eds.) PKC 2023. Part I, volume 13940 of LNCS, pp. 554\u2013584. Springer, Heidelberg (2023). https:\/\/doi.org\/10.1007\/978-3-031-31368-4_20","DOI":"10.1007\/978-3-031-31368-4_20"},{"key":"4_CR32","doi-asserted-by":"publisher","unstructured":"Tsimos, G., Loss, J., Papamanthou, C.: Gossiping for communication-efficient broadcast. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. Part III, volume 13509 of LNCS, pp. 439\u2013469. Springer, Heidelberg (2022). https:\/\/doi.org\/10.1007\/978-3-031-15982-4_15","DOI":"10.1007\/978-3-031-15982-4_15"},{"key":"4_CR33","doi-asserted-by":"publisher","unstructured":"Wan, J., Xiao, H., Devadas, S., Shi, E.: Round-efficient byzantine broadcast under strongly adaptive and majority corruptions. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. Part I, volume 12550 of LNCS, pp. 412\u2013456. Springer, Heidelberg (2020). https:\/\/doi.org\/10.1007\/978-3-030-64375-1_15","DOI":"10.1007\/978-3-030-64375-1_15"},{"key":"4_CR34","doi-asserted-by":"publisher","unstructured":"Wan, J., Xiao, H., Shi, E., Devadas, S.: Expected constant round byzantine broadcast under dishonest majority. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. Part I, volume 12550 of LNCS, pp. 381\u2013411. Springer, Heidelberg (2020). https:\/\/doi.org\/10.1007\/978-3-030-64375-1_14","DOI":"10.1007\/978-3-030-64375-1_14"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2025"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-01878-6_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T15:14:18Z","timestamp":1757430858000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-01878-6_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783032018779","9783032018786"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-01878-6_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"17 August 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"45","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}