{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:21:03Z","timestamp":1761621663158,"version":"build-2065373602"},"reference-count":61,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T00:00:00Z","timestamp":1759276800000},"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":["J Cryptol"],"published-print":{"date-parts":[[2025,10]]},"DOI":"10.1007\/s00145-025-09556-3","type":"journal-article","created":{"date-parts":[[2025,10,15]],"date-time":"2025-10-15T15:21:34Z","timestamp":1760541694000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Asymptotically Free Broadcast in Constant Expected Time via Packed VSS"],"prefix":"10.1007","volume":"38","author":[{"given":"Ittai","family":"Abraham","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gilad","family":"Asharov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shravani","family":"Patil","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arpita","family":"Patra","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,10,15]]},"reference":[{"key":"9556_CR1","unstructured":"I. Abraham, G. Asharov, A. Chandramouli, Simple is COOL: graded dispersal and its applications for byzantine fault tolerance, in R. Meka, editor, 16th Innovations in Theoretical Computer Science Conference, ITCS 2025, January 7-10, 2025, Columbia University, New York, NY, USA. LIPIcs, vol. 325, (Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2025), pp. 1:1\u20131:20"},{"key":"9556_CR2","doi-asserted-by":"crossref","unstructured":"I. Abraham, G. Asharov, S. Patil, A. Patra, Asymptotically free broadcast in constant expected time via packed vss, in Theory of Cryptography Conference, (Springer, 2022), pp. 384\u2013414","DOI":"10.1007\/978-3-031-22318-1_14"},{"key":"9556_CR3","doi-asserted-by":"crossref","unstructured":"I. Abraham, G. Asharov, A, Yanai, Efficient perfectly secure computation with optimal resilience, in Theory of Cryptography Conference. (2021)","DOI":"10.1007\/978-3-030-90453-1_3"},{"key":"9556_CR4","doi-asserted-by":"crossref","unstructured":"G. Asharov, A. Chandramouli, Perfect (parallel) broadcast in constant expected rounds via statistical VSS. in M. Joye, G. Leander, editors, Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part V. Lecture Notes in Computer Science, vol. 14655. (Springer, 2024), pp. 310\u2013339","DOI":"10.1007\/978-3-031-58740-5_11"},{"key":"9556_CR5","unstructured":"G. Asharov, R. Cohen, O. Shochat, Static vs. adaptive security in perfect MPC: a separation and the adaptive security of BGW, in D. Dachman-Soled, editor,3rd Conference on Information-Theoretic Cryptography, ITC 2022, July 5-7, 2022, Cambridge, MA, USA. LIPIcs, vol. 230. (Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2022), pp. 15:1\u201315:16"},{"key":"9556_CR6","doi-asserted-by":"crossref","unstructured":"I. Abraham, S. Devadas, D. Dolev, K. Nayak, L. Ren, Synchronous byzantine agreement with expected O(1) rounds, expected o(n$$^{2}$$) communication, and optimal resilience, in I. Goldberg, T. Moore, editors, Financial Cryptography and Data Security, 2019, vol. 11598. (Springer, 2019), pp. 320\u2013334","DOI":"10.1007\/978-3-030-32101-7_20"},{"key":"9556_CR7","doi-asserted-by":"crossref","unstructured":"B. Applebaum, E. Kachlon, A. Patra, The round complexity of perfect mpc with active security and optimal resiliency, in Annual Symposium on Foundations of Computer Science (FOCS). (2020)","DOI":"10.1109\/FOCS46700.2020.00121"},{"key":"9556_CR8","unstructured":"G. Asharov, Y. Lindell, A full proof of the bgw protocol for perfectly secure multiparty computation. J. Cryptol. (2017)."},{"key":"9556_CR9","doi-asserted-by":"crossref","unstructured":"G. Asharov, Y. Lindell, T. Rabin, Perfectly-secure multiplication for any $$t < n\/3$$, in P. Rogaway, editor, Advances in Cryptology - CRYPTO 2011. (2011)","DOI":"10.1007\/978-3-642-22792-9_14"},{"key":"9556_CR10","unstructured":"I. Abraham, K. Nayak, Crusader agreement with $$\\le 1\/3$$ error is impossible for $$n \\le 3f$$ if the adversary can simulate. Decentralized Thoughts, Blog Post, 2021. https:\/\/tinyurl.com\/decentralizedthougts. Accessed Sept 2021"},{"key":"9556_CR11","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, R. Canetti, O. Goldreich, Asynchronous secure computation. in Proceedings of ACM symposium on Theory of computing (1993)","DOI":"10.1145\/167088.167109"},{"issue":"4","key":"9556_CR12","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/s00446-002-0083-3","volume":"16","author":"M Ben-Or","year":"2003","unstructured":"M. Ben-Or and R. El-Yaniv. Resilient-optimal interactive consistency in constant time. Distributed Computing, 16(4):249\u2013262, 2003.","journal-title":"Distrib. Comput."},{"key":"9556_CR13","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, Another advantage of free choice: completely asynchronous agreement protocols (extended abstract), in Proceedings of the Annual Symposium on Principles of Distributed Computing (PODC) (1983)","DOI":"10.1145\/800221.806707"},{"key":"9556_CR14","doi-asserted-by":"crossref","unstructured":"P. Berman, J.A. Garay, K.J. Perry, Bit optimal distributed consensus. Computer science. (1992)","DOI":"10.1007\/978-1-4615-3422-8_27"},{"key":"9556_CR15","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, S. Goldwasser, A. Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract), in Proceedings of Annual ACM Symposium on Theory of Computing (1988)","DOI":"10.1145\/62212.62213"},{"key":"9556_CR16","unstructured":"Z. Beerliov\u00e1-Trub\u00edniov\u00e1, M. Hirt, Perfectly-secure mpc with linear communication complexity, in Theory of Cryptography Conference (2008)"},{"key":"9556_CR17","unstructured":"R. Canetti, Asynchronous secure computation, in Technion - Computer Science Department - Technical Report, CS0755 (1993)"},{"key":"9556_CR18","unstructured":"R. Canetti, Studies in secure multiparty computation and applications. PhD thesis, Citeseer, (1996)"},{"issue":"1","key":"9556_CR19","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s001459910006","volume":"13","author":"R Canetti","year":"2000","unstructured":"R. Canetti. Security and composition of multiparty cryptographic protocols. J. Cryptol., 13(1):143\u2013202, 2000.","journal-title":"J. Cryptol."},{"key":"9556_CR20","doi-asserted-by":"crossref","unstructured":"R. Canetti. Universally composable security: a new paradigm for cryptographic protocols, in FOCS (2001)","DOI":"10.1109\/SFCS.2001.959888"},{"key":"9556_CR21","doi-asserted-by":"crossref","unstructured":"D. Chaum, C. Cr\u00e9peau, I. Damg\u00e5rd, Multiparty unconditionally secure protocols (extended abstract), in Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA. (ACM, 1988), pp. 11\u201319","DOI":"10.1145\/62212.62214"},{"issue":"3","key":"9556_CR22","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1007\/s00145-018-9279-y","volume":"32","author":"R Cohen","year":"2019","unstructured":"R. Cohen, S. Coretti, J.A. Garay, V. Zikas, Probabilistic termination and composability of cryptographic protocols. J. Cryptol., 32(3):690\u2013741, 2019.","journal-title":"J. Cryptol."},{"issue":"11s","key":"9556_CR23","doi-asserted-by":"publisher","first-page":"232:1","DOI":"10.1145\/3512344","volume":"54","author":"A Chandramouli","year":"2022","unstructured":"A. Chandramouli, A. Choudhury, A. Patra, A survey on perfectly secure verifiable secret-sharing. ACM Comput. Surv., 54(11):232:1\u2013232:36, 2022.","journal-title":"ACM Comput. Surv."},{"key":"9556_CR24","doi-asserted-by":"crossref","unstructured":"R. Canetti, I. Damg\u00e5rd, S. Dziembowski, Y. Ishai, T. Malkin, On adaptive vs. non-adaptive security of multiparty protocols, in Advances in Cryptology - EUROCRYPT 2001, International Conference on the Theory and Application of Cryptographic Techniques (2001)","DOI":"10.1007\/3-540-44987-6_17"},{"key":"9556_CR25","doi-asserted-by":"crossref","unstructured":"R. Cramer, I. Damg\u00e5rd, U. Maurer, General secure multi-party computation from any linear secret-sharing scheme, in International Conference on the Theory and Applications of Cryptographic Techniques (2000)","DOI":"10.1007\/3-540-45539-6_22"},{"key":"9556_CR26","doi-asserted-by":"crossref","unstructured":"B. Chor, S. Goldwasser, S. Micali, B. Awerbuch, Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract), in 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21-23 October 1985. (IEEE Computer Society, 1985), pp. 383\u2013395","DOI":"10.1109\/SFCS.1985.64"},{"key":"9556_CR27","unstructured":"J. Chen, Optimal error-free multi-valued byzantine agreement, in DISC (2021)"},{"key":"9556_CR28","doi-asserted-by":"crossref","unstructured":"A. Choudhury, M. Hirt, A. Patra, Asynchronous multiparty computation with linear communication complexity, in Y. Afek, editor, Distributed Computing - 27th International Symposium, DISC 2013, Jerusalem, Israel, October 14-18, 2013. Proceedings. Lecture Notes in Computer Science, vol. 8205. (Springer, 2013), pp. 388\u2013402","DOI":"10.1007\/978-3-642-41527-2_27"},{"key":"9556_CR29","doi-asserted-by":"crossref","unstructured":"A. Choudhury, A. Patra, An efficient framework for unconditionally secure multiparty computation. IEEE Transactions on Information Theory, 2016.","DOI":"10.1109\/TIT.2016.2614685"},{"key":"9556_CR30","doi-asserted-by":"crossref","unstructured":"B.A. Coan, J.L. Welch, Modular construction of nearly optimal byzantine agreement protocols, in ACM Symposium on Principles of distributed computing (1989)","DOI":"10.1145\/72981.73002"},{"key":"9556_CR31","doi-asserted-by":"crossref","unstructured":"I. Damg\u00e5rd, B. David, I. Giacomelli, J.B. Nielsen, Compact vss and efficient homomorphic uc commitments, in International Conference on the Theory and Application of Cryptology and Information Security, (Springer, 2014), pp. 213\u2013232","DOI":"10.1007\/978-3-662-45608-8_12"},{"key":"9556_CR32","doi-asserted-by":"crossref","unstructured":"D. Dolev, R. Reischuk, Bounds on information exchange for byzantine agreement, in R.L. Probert, M.J. Fischer, N. Santoro, editor, ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, Ottawa, Canada August 18-20, 1982, (ACM, 1982), pp. 132\u2013140","DOI":"10.1145\/800220.806690"},{"key":"9556_CR33","doi-asserted-by":"crossref","unstructured":"D. Dolev, R. Reischuk, Bounds on information exchange for byzantine agreement. Journal of the ACM (JACM) (1985)","DOI":"10.1145\/2455.214112"},{"key":"9556_CR34","doi-asserted-by":"crossref","unstructured":"S. Das, Z. Xiang, L. Ren, Asynchronous data dissemination and its applications, in ACM CCS Conference on Computer and Communications Security (2021)","DOI":"10.1145\/3460120.3484808"},{"key":"9556_CR35","doi-asserted-by":"crossref","unstructured":"P.N. Feldman, Optimal Algorithms for Byzantine Agreement. PhD thesis, Massachusetts Institute of Technology (1988)","DOI":"10.1145\/62212.62225"},{"key":"9556_CR36","doi-asserted-by":"crossref","unstructured":"M. Fitzi, J.A. Garay, Efficient player-optimal protocols for strong and differential consensus, in PODC (2003)","DOI":"10.1145\/872035.872066"},{"key":"9556_CR37","volume-title":"Fischer and Nancy A","author":"J Michael","year":"1982","unstructured":"M.J. Fischer, N.A. Lynch, A lower bound for the time to assure interactive consistency. Information Processing Letters, (1982)"},{"key":"9556_CR38","doi-asserted-by":"crossref","unstructured":"P. Feldman, S. Micali, Optimal algorithms for byzantine agreement, in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (1988)","DOI":"10.1145\/62212.62225"},{"key":"9556_CR39","doi-asserted-by":"crossref","unstructured":"P. Feldman, S. Micali, An optimal probabilistic protocol for synchronous byzantine agreement. SIAM Journal on Computing (1997)","DOI":"10.1137\/S0097539790187084"},{"key":"9556_CR40","doi-asserted-by":"crossref","unstructured":"M.K. Franklin, M. Yung, Communication complexity of secure computation (extended abstract), in Proceedings of the 24th Annual ACM Symposium on Theory of Computing, ed. S.R. Kosaraju, M. Fellows, A. Wigderson, J.A. Ellis, (ACM, 1992), pp. 699\u2013710","DOI":"10.1145\/129712.129780"},{"key":"9556_CR41","doi-asserted-by":"crossref","unstructured":"R. Gennaro, Y. Ishai, E. Kushilevitz, T. Rabin, The round complexity of verifiable secret sharing and secure multicast, in ACM symposium on Theory of computing (2001)","DOI":"10.1145\/380752.380853"},{"key":"9556_CR42","doi-asserted-by":"crossref","unstructured":"V. Goyal, Y. Liu, Y. Song, Communication-efficient unconditional mpc with guaranteed output delivery, in Annual International Cryptology Conference (2019)","DOI":"10.1007\/978-3-030-26951-7_4"},{"issue":"1","key":"9556_CR43","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/0020-0190(90)90185-Z","volume":"36","author":"O Goldreich","year":"1990","unstructured":"O. Goldreich, E. Petrank, The best of both worlds: Guaranteeing termination in fast randomized byzantine agreement protocols. Inf. Process. Lett., 36(1):45\u201349, 1990.","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9556_CR44","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s00446-020-00384-1","volume":"34","author":"C Ganesh","year":"2021","unstructured":"C. Ganesh, A. Patra, Optimal extension protocols for byzantine broadcast and agreement. Distributed Computing, 34(1):59\u201377, 2021.","journal-title":"Distrib. Comput."},{"key":"9556_CR45","doi-asserted-by":"crossref","unstructured":"R. Gennaro, M.O. Rabin, T. Rabin, Simplified vss and fast-track multiparty computations with applications to threshold cryptography, in ACM symposium on Principles of distributed computing (1998)","DOI":"10.1145\/277697.277716"},{"key":"9556_CR46","doi-asserted-by":"crossref","unstructured":"M. Hirt, U. Maurer, B. Przydatek, Efficient secure multi-party computation, in International conference on the theory and application of cryptology and information security (2000)","DOI":"10.1007\/3-540-44448-3_12"},{"key":"9556_CR47","doi-asserted-by":"crossref","unstructured":"M. Hirt, V. Zikas, Adaptively secure broadcast, in H. Gilbert, editor, Advances in Cryptology - EUROCRYPT 2010. Lecture Notes in Computer Science, vol. 6110 (Springer, 2010) pp. 466\u2013485","DOI":"10.1007\/978-3-642-13190-5_24"},{"key":"9556_CR48","doi-asserted-by":"crossref","unstructured":"J. Katz, C.-Y. Koo, On expected constant-round protocols for byzantine agreement, in Annual International Cryptology Conference (2006)","DOI":"10.1007\/11818175_27"},{"key":"9556_CR49","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_41","volume-title":"Improving the round complexity of vss in point-to-point networks","author":"Jonathan Katz","year":"2008","unstructured":"J. Katz, C.-Y. Koo, R. Kumaresan, Improving the round complexity of vss in point-to-point networks, inInternational Colloquium on Automata, Languages, and Programming (2008)"},{"key":"9556_CR50","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz, Y. Lindell, T. Rabin, Information-theoretically secure protocols and security under composition, in Proceedings of the 38th Annual ACM Symposium on Theory of Computing (2006)","DOI":"10.1145\/1132516.1132532"},{"key":"9556_CR51","unstructured":"Aws latency monitoring. Accessed Feb2022."},{"key":"9556_CR52","doi-asserted-by":"crossref","unstructured":"Y. Lindell, A. Lysyanskaya, T. Rabin, Sequential composition of protocols without simultaneous termination. In A. Ricciardi, editor, Proceedings of the Twenty-First Annual ACM Symposium on Principles of Distributed Computing, PODC 2002, Monterey, California, USA, July 21-24, 2002 (ACM, 2002), pp. 203\u2013212","DOI":"10.1145\/571825.571859"},{"key":"9556_CR53","doi-asserted-by":"crossref","unstructured":"L. Lamport, R. Shostak, M. Pease, The byzantine generals problem. ACM Trans. Program. Lang. Syst. (1982)","DOI":"10.1145\/357172.357176"},{"key":"9556_CR54","unstructured":"K. Nayak, L. Ren, E. Shi, N.H. Vaidya, Z. Xiang, Improved extension protocols for byzantine broadcast and agreement. arXiv preprint arXiv:2002.11321 (2020)"},{"key":"9556_CR55","doi-asserted-by":"crossref","unstructured":"A. Patra, Error-free multi-valued broadcast and byzantine agreement with optimal communication complexity, in International Conference On Principles Of Distributed Systems (2011)","DOI":"10.1007\/978-3-642-25873-2_4"},{"key":"9556_CR56","doi-asserted-by":"crossref","unstructured":"M. Pease, R. Shostak, L. Lamport, Reaching agreement in the presence of faults. Journal of the ACM (JACM) (1980)","DOI":"10.1145\/322186.322188"},{"key":"9556_CR57","doi-asserted-by":"crossref","unstructured":"M.O. Rabin, Randomized byzantine generals, in 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (1983)","DOI":"10.1109\/SFCS.1983.48"},{"key":"9556_CR58","unstructured":"N. Shrestha, A. Bhat, A. Kate, K. Nayak, Synchronous distributed key generation without broadcasts. IACR Cryptol. ePrint Arch., (2021) p. 1635"},{"issue":"2","key":"9556_CR59","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0020-0190(84)90027-9","volume":"18","author":"R Turpin","year":"1984","unstructured":"R. Turpin, B.A. Coan, Extending binary byzantine agreement to multivalued byzantine agreement. Information Processing Letters, 18(2):73\u201376, 1984.","journal-title":"Inf. Process. Lett."},{"key":"9556_CR60","unstructured":"G. Tsimos, J. Loss, C. Papamanthou, Gossiping for communication-efficient broadcast. Cryptology ePrint Archive (2020)"},{"key":"9556_CR61","doi-asserted-by":"crossref","unstructured":"J. Zhu, F. Li, J. Chen, Communication-efficient and error-free gradecast with optimal resilience, in IEEE International Symposium on Information Theory, ISIT 2023, Taipei, Taiwan, June 25-30, 2023, (IEEE, 2023), pp. 108\u2013113","DOI":"10.1109\/ISIT54713.2023.10206579"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-025-09556-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-025-09556-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-025-09556-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:17:28Z","timestamp":1761621448000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-025-09556-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10]]},"references-count":61,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["9556"],"URL":"https:\/\/doi.org\/10.1007\/s00145-025-09556-3","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"type":"print","value":"0933-2790"},{"type":"electronic","value":"1432-1378"}],"subject":[],"published":{"date-parts":[[2025,10]]},"assertion":[{"value":"7 May 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 September 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 September 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"36"}}