{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,24]],"date-time":"2026-01-24T23:54:29Z","timestamp":1769298869391,"version":"3.49.0"},"reference-count":47,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,7,26]],"date-time":"2020-07-26T00:00:00Z","timestamp":1595721600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,7,26]],"date-time":"2020-07-26T00:00:00Z","timestamp":1595721600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2021,2]]},"DOI":"10.1007\/s00446-020-00384-1","type":"journal-article","created":{"date-parts":[[2020,7,26]],"date-time":"2020-07-26T17:02:15Z","timestamp":1595782935000},"page":"59-77","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Optimal extension protocols for byzantine broadcast and agreement"],"prefix":"10.1007","volume":"34","author":[{"given":"Chaya","family":"Ganesh","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0188-6558","authenticated-orcid":false,"given":"Arpita","family":"Patra","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,7,26]]},"reference":[{"key":"384_CR1","doi-asserted-by":"crossref","unstructured":"Beerliov\u00e1-Trub\u00edniov\u00e1, Z., Hirt, M.: Efficient multi-party computation with dispute control. In: Halevi, S., Rabin, T. (eds.) Theory of Cryptography, pp. 305\u2013328. Springer, Berlin (2006)","DOI":"10.1007\/11681878_16"},{"key":"384_CR2","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Canetti, R., Goldreich, O.: Asynchronous secure computation. In: Proceedings of the 25th Annual ACM Symposium on Theory of computing, pp. 52\u201361. ACM (1993)","DOI":"10.1145\/167088.167109"},{"issue":"4","key":"384_CR3","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s00446-002-0083-3","volume":"16","author":"M Ben-Or","year":"2003","unstructured":"Ben-Or, M., El-Yaniv, R.: Resilient-optimal interactive consistency in constant time. Distrib. Comput. 16(4), 249\u2013262 (2003)","journal-title":"Distrib. Comput."},{"key":"384_CR4","doi-asserted-by":"crossref","unstructured":"Blum, N.: A new approach to maximum matching in general graphs. In: Automata, Languages and Programming, 17th International Colloquium, ICALP90, Warwick University, England, July 16-20, 1990, Proceedings, pp. 586\u2013597 (1990)","DOI":"10.1007\/BFb0032060"},{"key":"384_CR5","doi-asserted-by":"crossref","unstructured":"Braud-Santoni, N., Guerraoui, R., Huc, F.: Fast byzantine agreement. In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, pp. 57\u201364. ACM (2013)","DOI":"10.1145\/2484239.2484243"},{"key":"384_CR6","unstructured":"Canetti, R.: Studies in secure multiparty computation and applications. Ph.D. thesis, The Weizmann Institute of Science (1996)"},{"key":"384_CR7","unstructured":"Chongchitmate, W., Ostrovsky, R.: Information-theoretic broadcast with dishonest majority for long messages. Cryptology ePrint Archive, Report 2018\/829 (2018). https:\/\/eprint.iacr.org\/2018\/829"},{"issue":"1","key":"384_CR8","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. Inform. Comput. 97(1), 61\u201385 (1992)","journal-title":"Inform. Comput."},{"key":"384_CR9","doi-asserted-by":"crossref","unstructured":"Cohen, R., Coretti, S., Garay, J., Zikas, V.: Probabilistic termination and composability of cryptographic protocols. Proceedings. Part III, of the 36th Annual International Cryptology Conference on Advances in Cryptology\u2013CRYPTO 2016-Volume 9816, pp. 240\u2013269. Springer, New York, Inc (2016)","DOI":"10.1007\/978-3-662-53015-3_9"},{"key":"384_CR10","unstructured":"Cohen, R., Coretti, S., Garay, J., Zikas, V.: Round-Preserving Parallel Composition of Probabilistic-Termination Cryptographic Protocols. In: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a080, pp. 37:1\u201337:15 (2017)"},{"key":"384_CR11","first-page":"103","volume-title":"Advances in Cryptology - EUROCRYPT 1997","author":"R Cramer","year":"1997","unstructured":"Cramer, R., Gennaro, R., Schoenmakers, B.: A secure and optimally efficient multi-authority election scheme. In: Fumy, W. (ed.) Advances in Cryptology - EUROCRYPT 1997, pp. 103\u2013118. Springer, Berlin (1997)"},{"issue":"1","key":"384_CR12","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":"384_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":"6","key":"384_CR14","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1145\/3812.3818","volume":"28","author":"S Even","year":"1985","unstructured":"Even, S., Goldreich, O., Lempel, A.: A randomized protocol for signing contracts. Commun. ACM 28(6), 637\u2013647 (1985)","journal-title":"Commun. ACM"},{"issue":"4","key":"384_CR15","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":"384_CR16","doi-asserted-by":"crossref","unstructured":"Fitzi, M., Hirt, M.: Optimally efficient multi-valued byzantine agreement. In: Proceedings of the 25th Annual ACM Symposium on Principles of Distributed Computing, pp. 163\u2013168. ACM (2006)","DOI":"10.1145\/1146381.1146407"},{"key":"384_CR17","doi-asserted-by":"crossref","unstructured":"Ganesh, C., Patra, A.: Broadcast extensions with optimal communication and round complexity. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pp. 371\u2013380. ACM (2016)","DOI":"10.1145\/2933057.2933082"},{"key":"384_CR18","doi-asserted-by":"crossref","unstructured":"Garay, J., Givens, C., Ostrovsky, R., Raykov, P.: Broadcast (and round) efficient verifiable secret sharing. In: International Conference on Information Theoretic Security, pp. 200\u2013219. Springer (2013)","DOI":"10.1007\/978-3-319-04268-8_12"},{"key":"384_CR19","doi-asserted-by":"crossref","unstructured":"Garay, J., Katz, J., Koo, C.Y., Ostrovsky, R.: Round complexity of authenticated broadcast with a dishonest majority. In: Foundations of Computer Science, 2007. FOCS\u201907, pp. 658\u2013668. IEEE (2007)","DOI":"10.1109\/FOCS.2007.4389534"},{"key":"384_CR20","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: a guide to the theory of np-completeness, W. H. Freeman & Co, USA (1990)"},{"key":"384_CR21","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, pp. 218\u2013229. ACM (1987)","DOI":"10.1145\/28395.28420"},{"key":"384_CR22","doi-asserted-by":"crossref","unstructured":"Hirt, M., Maurer, U.M., Przydatek, B.: Efficient secure multi-party computation. In: Okamoto, T. (ed.) Advances in Cryptology - ASIACRYPT 2000, 6th International Conference on the Theory and Application of Cryptology and Information Security, Kyoto, Japan, December 3\u20137, 2000, Proceedings, Lecture Notes in Computer Science, vol. 1976, pp. 143\u2013161. Springer (2000)","DOI":"10.1007\/3-540-44448-3_12"},{"key":"384_CR23","doi-asserted-by":"crossref","unstructured":"Hirt, M., Raykov, P.: Multi-valued byzantine broadcast: The $$t<n$$ case. In: Sarkar, P., Iwata, T. (eds.) Advances in Cryptology\u2013ASIACRYPT 2014, pp. 448\u2013465. Springer (2014)","DOI":"10.1007\/978-3-662-45608-8_24"},{"key":"384_CR24","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kilian, J., Nissim, K., Petrank, E.: Extending oblivious transfers efficiently. In: Boneh, D. (ed.) Advances in Cryptology-CRYPTO 2003, pp. 145\u2013161. Springer (2003)","DOI":"10.1007\/978-3-540-45146-4_9"},{"key":"384_CR25","unstructured":"Karlin, A., Yao, A.C.C.: Probabilistic lower bounds for byzantine agreement. Tech. rep, Manuscript (1986)"},{"key":"384_CR26","first-page":"445","volume":"2006","author":"J Katz","year":"2006","unstructured":"Katz, J., Koo, C.: On expected constant-round protocols for byzantine agreement. Adv. Cryptol - CRYPTO 2006, 445\u2013462 (2006)","journal-title":"Adv. Cryptol - CRYPTO"},{"key":"384_CR27","first-page":"311","volume":"2007","author":"J Katz","year":"2007","unstructured":"Katz, J., Koo, C.Y.: Round-efficient secure computation in point-to-point networks. Adv Cryptolo-EUROCRYPT 2007, 311\u2013328 (2007)","journal-title":"Adv Cryptolo-EUROCRYPT"},{"key":"384_CR28","doi-asserted-by":"crossref","unstructured":"Katz, J., Koo, C.Y., Kumaresan, R.: Improving the round complexity of vss in point-to-point networks. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) International Colloquium on Automata, Languages, and Programming, pp. 499\u2013510. Springer (2008)","DOI":"10.1007\/978-3-540-70583-3_41"},{"key":"384_CR29","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 - 12th International Conference, ICDCN 2011, Bangalore, India, January 2\u20135, 2011. Proceedings, pp. 203\u2013214 (2011)","DOI":"10.1007\/978-3-642-17679-1_18"},{"key":"384_CR30","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J.: From almost everywhere to everywhere: Byzantine agreement with $$\\tilde{O}(n^{3\/2})$$ bits. In: International Symposium on Distributed Computing, pp. 464\u2013478. Springer (2009)","DOI":"10.1007\/978-3-642-04355-0_47"},{"issue":"4","key":"384_CR31","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1145\/1989727.1989732","volume":"58","author":"V King","year":"2011","unstructured":"King, V., Saia, J.: Breaking the $$o(n^2)$$ bit barrier: scalable byzantine agreement with an adaptive adversary. J. ACM (JACM) 58(4), 18 (2011)","journal-title":"J. ACM (JACM)"},{"key":"384_CR32","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 Algorithm, pp. 990\u2013999. Society for Industrial and Applied Mathematics (2006)","DOI":"10.1145\/1109557.1109667"},{"key":"384_CR33","unstructured":"Lamport, L., Fischer, M.: Byzantine generals and transaction commit protocols. Tech. rep., Technical Report 62, SRI International (1982). https:\/\/lamport.azurewebsites.net\/pubs\/trans.pdf"},{"key":"384_CR34","doi-asserted-by":"crossref","unstructured":"Liang, G., Vaidya, N.: Error-free multi-valued consensus with byzantine failures. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, pp. 11\u201320. ACM (2011)","DOI":"10.1145\/1993806.1993809"},{"key":"384_CR35","unstructured":"Lindell, Y., Lysyanskaya, A., Rabin, T.: Sequential composition of protocols without simultaneous termination. In: Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing, PODC 2002, Monterey, California, USA, July 21\u201324, 2002, pp. 203\u2013212 (2002)"},{"issue":"6","key":"384_CR36","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1145\/1217856.1217857","volume":"53","author":"Y Lindell","year":"2006","unstructured":"Lindell, Y., Lysyanskaya, A., Rabin, T.: On the composition of authenticated byzantine agreement. J. ACM (JACM) 53(6), 881\u2013917 (2006)","journal-title":"J. ACM (JACM)"},{"key":"384_CR37","volume-title":"Distributed Algorithms","author":"NA Lynch","year":"1996","unstructured":"Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann, Burlington (1996)"},{"key":"384_CR38","volume-title":"The Theory of Error Correcting Codes","author":"FJ MacWilliams","year":"1978","unstructured":"MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error Correcting Codes. North-Holland Publishing Company, Amsterdam (1978)"},{"key":"384_CR39","unstructured":"Micali, S.: Very simple and efficient byzantine agreement. In: 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9\u201311, 2017, Berkeley, CA, USA, pp. 6:1\u20136:1 (2017)"},{"key":"384_CR40","doi-asserted-by":"crossref","unstructured":"Patra, A.: Error-free multi-valued broadcast and byzantine agreement with optimal communication complexity. In: Proceedings of Principles of Distributed Systems - 15th International Conference, OPODIS 2011, pp. 34\u201349 (2011)","DOI":"10.1007\/978-3-642-25873-2_4"},{"key":"384_CR41","first-page":"162","volume-title":"Progress in Cryptology - LATINCRYPT 2010 LATINCRYPT 2010. Lecture Notes in Computer Science","author":"A Patra","year":"2010","unstructured":"Patra, A., Rangan, C.P.: Communication optimal multi-valued asynchronous broadcast protocol. In: Abdalla, M., Barreto, P.S.L.M. (eds.) Progress in Cryptology - LATINCRYPT 2010 LATINCRYPT 2010. Lecture Notes in Computer Science, vol. 6212, pp. 162\u2013177. Springer, Berlin, Heidelberg (2010)"},{"key":"384_CR42","doi-asserted-by":"crossref","unstructured":"Patra, A., Rangan, C.P.: Communication optimal multi-valued asynchronous byzantine agreement with optimal resilience. In: Proceedings of the 5th International Conference on Information Theoretic Security, pp. 206\u2013226. Springer-Verlag (2011)","DOI":"10.1007\/978-3-642-20728-0_19"},{"issue":"2","key":"384_CR43","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1145\/322186.322188","volume":"27","author":"M Pease","year":"1980","unstructured":"Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. J ACM (JACM) 27(2), 228\u2013234 (1980)","journal-title":"J ACM (JACM)"},{"key":"384_CR44","unstructured":"Pfitzmann, B., Waidner, M.: Information-theoretic pseudosignatures and byzantine agreement for t $$\\ge $$ n\/3. Technical Report RZ 2882 (#90830), IBM Research (1996). https:\/\/www.csa.iisc.ac.in\/~arpita\/BroadcastBAReadingGroup\/PW96.pdf"},{"issue":"2","key":"384_CR45","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/0108018","volume":"8","author":"IS Reed","year":"1960","unstructured":"Reed, I.S., Solomon, G.: Polynomial codes over certain finite fields. J. Soc. Ind. Appl. Math. 8(2), 300\u2013304 (1960)","journal-title":"J. Soc. Ind. Appl. Math."},{"issue":"2","key":"384_CR46","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0020-0190(84)90027-9","volume":"18","author":"R Turpin","year":"1984","unstructured":"Turpin, R., Coan, B.A.: Extending binary byzantine agreement to multivalued byzantine agreement. Inform. Process. Lett. 18(2), 73\u201376 (1984)","journal-title":"Inform. Process. Lett."},{"key":"384_CR47","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Some complexity questions related to distributive computing(preliminary report). In: Proceedings of the 11th Annual ACM Symposium on Theory of Computing, STOC \u201979, pp. 209\u2013213. ACM (1979)","DOI":"10.1145\/800135.804414"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00384-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00446-020-00384-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-020-00384-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,25]],"date-time":"2021-07-25T23:17:00Z","timestamp":1627255020000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00446-020-00384-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,26]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,2]]}},"alternative-id":["384"],"URL":"https:\/\/doi.org\/10.1007\/s00446-020-00384-1","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"value":"0178-2770","type":"print"},{"value":"1432-0452","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,26]]},"assertion":[{"value":"22 October 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 July 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}