{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T03:21:34Z","timestamp":1764645694369,"version":"3.28.0"},"reference-count":97,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,10,27]],"date-time":"2023-10-27T00:00:00Z","timestamp":1698364800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,10,27]],"date-time":"2023-10-27T00:00:00Z","timestamp":1698364800000},"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":[[2024,1]]},"DOI":"10.1007\/s00145-023-09484-0","type":"journal-article","created":{"date-parts":[[2023,10,27]],"date-time":"2023-10-27T23:02:59Z","timestamp":1698447779000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Breaking the $$O(\\sqrt{n})$$-Bit Barrier: Byzantine Agreement with Polylog Bits Per Party"],"prefix":"10.1007","volume":"37","author":[{"given":"Elette","family":"Boyle","sequence":"first","affiliation":[]},{"given":"Ran","family":"Cohen","sequence":"additional","affiliation":[]},{"given":"Aarushi","family":"Goel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,10,27]]},"reference":[{"key":"9484_CR1","doi-asserted-by":"crossref","unstructured":"I.\u00a0Abraham, T.H. Chan, D.\u00a0Dolev, K.\u00a0Nayak, R.\u00a0Pass, L.\u00a0Ren, E.\u00a0Shi, Communication complexity of Byzantine agreement, revisited, in Proceedings of the 38th Annual ACM Symposium on Principles of Distributed Computing (PODC) (2019a), pp. 317\u2013326","DOI":"10.1145\/3293611.3331629"},{"key":"9484_CR2","doi-asserted-by":"crossref","unstructured":"I.\u00a0Abraham, S.\u00a0Devadas, D.\u00a0Dolev, K.\u00a0Nayak, L.\u00a0Ren, Synchronous Byzantine agreement with expected O(1) rounds, expected o(n$${}^{\\text{2)}}$$ communication, and optimal resilience, in Financial Cryptography and Data Security (2019b), pp. 320\u2013334","DOI":"10.1007\/978-3-030-32101-7_20"},{"key":"9484_CR3","doi-asserted-by":"crossref","unstructured":"M.\u00a0Ajtai, C.\u00a0Dwork, A public-key cryptosystem with worst-case\/average-case equivalence, in Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC) (1997), pp. 284\u2013293","DOI":"10.1145\/258533.258604"},{"key":"9484_CR4","doi-asserted-by":"crossref","unstructured":"G.\u00a0Asharov, A.\u00a0Jain, A.\u00a0L\u00f3pez-Alt, E.\u00a0Tromer, V.\u00a0Vaikuntanathan, D.\u00a0Wichs, Multiparty computation with low communication, computation and interaction via threshold FHE, in 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2012), pp. 483\u2013501","DOI":"10.1007\/978-3-642-29011-4_29"},{"issue":"5","key":"9484_CR5","doi-asserted-by":"publisher","first-page":"1661","DOI":"10.1137\/070709244","volume":"38","author":"B Barak","year":"2008","unstructured":"B.\u00a0Barak, O.\u00a0Goldreich. Universal arguments and their applications. SIAM J. Comput., 38(5), 1661\u20131694 (2008)","journal-title":"SIAM J. Comput."},{"key":"9484_CR6","doi-asserted-by":"crossref","unstructured":"M.\u00a0Bellare, G.\u00a0Neven, Multi-signatures in the plain public-key model and a general forking lemma, in Proceedings of the 13th ACM Conference on Computer and Communications Security (CCS) (2006), pp. 390\u2013399","DOI":"10.1145\/1180405.1180453"},{"key":"9484_CR7","doi-asserted-by":"crossref","unstructured":"M.\u00a0Ben-Or, S.\u00a0Goldwasser, A.\u00a0Wigderson, Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract), in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC) (1988), pp. 1\u201310","DOI":"10.1145\/62212.62213"},{"key":"9484_CR8","doi-asserted-by":"crossref","unstructured":"E.\u00a0Ben-Sasson, A.\u00a0Chiesa, E.\u00a0Tromer, M.\u00a0Virza, Scalable zero knowledge via cycles of elliptic curves, in 33rd Annual International Cryptology Conference (CRYPTO), Part II (2014), pp. 276\u2013294","DOI":"10.1007\/978-3-662-44381-1_16"},{"key":"9484_CR9","doi-asserted-by":"crossref","unstructured":"N.\u00a0Bitansky, R.\u00a0Canetti, A.\u00a0Chiesa, E.\u00a0Tromer, Recursive composition and bootstrapping for SNARKs and proof-carrying data, in Proceedings of the 45th Annual ACM Symposium on Theory of Computing (STOC) (2013), pp. 111\u2013120","DOI":"10.1145\/2488608.2488623"},{"issue":"4","key":"9484_CR10","doi-asserted-by":"publisher","first-page":"989","DOI":"10.1007\/s00145-016-9241-9","volume":"30","author":"N Bitansky","year":"2017","unstructured":"N.\u00a0Bitansky, R.\u00a0Canetti, A.\u00a0Chiesa, S.\u00a0Goldwasser, H.\u00a0Lin, A.\u00a0Rubinstein, E.\u00a0Tromer, The hunting of the SNARK. J. Cryptol., 30(4), 989\u20131066 (2017)","journal-title":"J. Cryptol."},{"key":"9484_CR11","doi-asserted-by":"crossref","unstructured":"E.\u00a0Blum, J.\u00a0Katz, C.\u00a0Liu-Zhang, J.\u00a0Loss, Asynchronous Byzantine agreement with subquadratic communication, in Proceedings of the 18th Theory of Cryptography Conference (TCC), Part I (2020), pp. 353\u2013380","DOI":"10.1007\/978-3-030-64375-1_13"},{"key":"9484_CR12","doi-asserted-by":"crossref","unstructured":"A.\u00a0Boldyreva, Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme, in Proceedings of the 6th International Conference on the Theory and Practice of Public-Key Cryptography (PKC) (2003), pp. 31\u201346","DOI":"10.1007\/3-540-36288-6_3"},{"key":"9484_CR13","doi-asserted-by":"crossref","unstructured":"A.\u00a0Boldyreva, C.\u00a0Gentry, A.\u00a0O\u2019Neill, D.H. Yum, Ordered multisignatures and identity-based sequential aggregate signatures, with applications to secure routing, in Proceedings of the 14th ACM Conference on Computer and Communications Security (CCS) (2007), pp. 276\u2013285","DOI":"10.1145\/1315245.1315280"},{"key":"9484_CR14","doi-asserted-by":"crossref","unstructured":"D.\u00a0Boneh, C.\u00a0Gentry, B.\u00a0Lynn, H.\u00a0Shacham, Aggregate and verifiably encrypted signatures from bilinear maps, in 22nd International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2003), pp. 416\u2013432","DOI":"10.1007\/3-540-39200-9_26"},{"key":"9484_CR15","doi-asserted-by":"crossref","unstructured":"D.\u00a0Boneh, M.\u00a0Drijvers, G.\u00a0Neven, Compact multi-signatures for smaller blockchains, in 24th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), part II (2018a), pp. 435\u2013464","DOI":"10.1007\/978-3-030-03329-3_15"},{"key":"9484_CR16","doi-asserted-by":"crossref","unstructured":"D.\u00a0Boneh, Y.\u00a0Ishai, A.\u00a0Sahai, D.J. Wu, Quasi-optimal SNARGs via linear multi-prover interactive proofs, in 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), Part III (2018b), pp. 222\u2013255","DOI":"10.1007\/978-3-319-78372-7_8"},{"key":"9484_CR17","doi-asserted-by":"crossref","unstructured":"E.\u00a0Boyle, S.\u00a0Goldwasser, S.\u00a0Tessaro, 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) (2013), pp. 356\u2013376","DOI":"10.1007\/978-3-642-36594-2_21"},{"key":"9484_CR18","doi-asserted-by":"crossref","unstructured":"E.\u00a0Boyle, K.\u00a0Chung, R.\u00a0Pass. Large-scale secure computation: Multi-party computation for (parallel) RAM programs, in 34th Annual International Cryptology Conference (CRYPTO), Part II (2015), pp. 742\u2013762","DOI":"10.1007\/978-3-662-48000-7_36"},{"key":"9484_CR19","doi-asserted-by":"crossref","unstructured":"E.\u00a0Boyle, R.\u00a0Cohen, D.\u00a0Data, P.\u00a0Hub\u00e1\u010dek, Must the communication graph of MPC protocols be an expander?, in 38th Annual International Cryptology Conference (CRYPTO), part III (2018a), pp. 243\u2013272","DOI":"10.1007\/978-3-319-96878-0_9"},{"key":"9484_CR20","unstructured":"E.\u00a0Boyle, A.\u00a0Jain, M.\u00a0Prabhakaran, C.\u00a0Yu, The bottleneck complexity of secure multiparty computation, in Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP) (2018b), pp. 24:1\u201324:16"},{"key":"9484_CR21","doi-asserted-by":"crossref","unstructured":"N.\u00a0Braud-Santoni, R.\u00a0Guerraoui, F.\u00a0Huc, Fast Byzantine agreement, in Proceedings of the 32th Annual ACM Symposium on Principles of Distributed Computing (PODC), (2013), pp. 57\u201364","DOI":"10.1145\/2484239.2484243"},{"issue":"1","key":"9484_CR22","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s001459910006","volume":"13","author":"R Canetti","year":"2000","unstructured":"R.\u00a0Canetti, Security and composition of multiparty cryptographic protocols. J. Cryptol. 13(1), 143\u2013202 (2000)","journal-title":"J. Cryptol."},{"key":"9484_CR23","doi-asserted-by":"crossref","unstructured":"R.\u00a0Canetti, Universally composable security: A new paradigm for cryptographic protocols, in Proceedings of the 42nd Annual Symposium on Foundations of Computer Science (FOCS) (2001), pp. 136\u2013145","DOI":"10.1109\/SFCS.2001.959888"},{"key":"9484_CR24","unstructured":"R.\u00a0Canetti, Universally composable signature, certification, and authentication, in 17th IEEE Computer Security Foundations Workshop, (CSFW) (2004), p. 219"},{"key":"9484_CR25","doi-asserted-by":"crossref","unstructured":"R.\u00a0Canetti, D.\u00a0Shahaf, M.\u00a0Vald, Universally composable authentication and key-exchange with global PKI, in Proceedings of the 19th International Conference on the Theory and Practice of Public-Key Cryptography (PKC), Part II (2016), pp. 265\u2013296","DOI":"10.1007\/978-3-662-49387-8_11"},{"key":"9484_CR26","doi-asserted-by":"crossref","unstructured":"T.\u00a0H. Chan, R.\u00a0Pass, E.\u00a0Shi, Consensus through herding, in 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), Part I (2019), pp. 720\u2013749","DOI":"10.1007\/978-3-030-17653-2_24"},{"key":"9484_CR27","doi-asserted-by":"crossref","unstructured":"T.H. Chan, R.\u00a0Pass, E.\u00a0Shi, 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 (2020), pp. 246\u2013265","DOI":"10.1007\/978-3-030-45388-6_9"},{"key":"9484_CR28","doi-asserted-by":"crossref","unstructured":"N.\u00a0Chandran, W.\u00a0Chongchitmate, J.A. Garay, S.\u00a0Goldwasser, R.\u00a0Ostrovsky, V.\u00a0Zikas, The hidden graph model: Communication locality and optimal resiliency with adaptive faults, in Proceedings of the 6th Annual Innovations in Theoretical Computer Science (ITCS) Conference (2015), pp. 153\u2013162","DOI":"10.1145\/2688073.2688102"},{"key":"9484_CR29","doi-asserted-by":"crossref","unstructured":"D.\u00a0Chaum, E.\u00a0van Heyst, Group signatures, in 10th Workshop on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (1991), pp. 257\u2013265","DOI":"10.1007\/3-540-46416-6_22"},{"key":"9484_CR30","doi-asserted-by":"crossref","unstructured":"D.\u00a0Chaum, C.\u00a0Cr\u00e9peau, I.\u00a0Damg\u00e5rd, Multiparty unconditionally secure protocols (extended abstract), in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC)(1988), pp. 11\u201319","DOI":"10.1145\/62212.62214"},{"key":"9484_CR31","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/j.tcs.2019.02.001","volume":"777","author":"J Chen","year":"2019","unstructured":"J.\u00a0Chen, S.\u00a0Micali, Algorand: A secure and efficient distributed ledger. Theor. Comput. Sci. 777, 155\u2013183 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"9484_CR32","unstructured":"A.\u00a0Chiesa, E.\u00a0Tromer, Proof-carrying data and hearsay arguments from signature cards, in Innovations in Computer Science\u2014ICS (2010), pp. 310\u2013331"},{"key":"9484_CR33","doi-asserted-by":"crossref","unstructured":"B.\u00a0Chor, S.\u00a0Goldwasser, S.\u00a0Micali, B.\u00a0Awerbuch, Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract), in Proceedings of the 17th Annual ACM Symposium on Theory of Computing (STOC) (1985), pp. 383\u2013395","DOI":"10.1109\/SFCS.1985.64"},{"key":"9484_CR34","doi-asserted-by":"crossref","unstructured":"R.\u00a0Cohen, Asynchronous secure multiparty computation in constant time, in Proceedings of the 19th International Conference on the Theory and Practice of Public-Key Cryptography (PKC), Part II (2016), pp. 183\u2013207","DOI":"10.1007\/978-3-662-49387-8_8"},{"issue":"3","key":"9484_CR35","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1007\/s00145-018-9279-y","volume":"32","author":"R Cohen","year":"2019","unstructured":"R.\u00a0Cohen, S.\u00a0Coretti, J.\u00a0A. Garay, V.\u00a0Zikas. Probabilistic termination and composability of cryptographic protocols. J. Cryptol. 32(3), 690\u2013741 (2019a)","journal-title":"J. Cryptol."},{"key":"9484_CR36","unstructured":"R.\u00a0Cohen, I.\u00a0Haitner, N.\u00a0Makriyannis, M.\u00a0Orland, A.\u00a0Samorodnitsky, On the round complexity of randomized Byzantine agreement, in Proceedings of the 33rd International Symposium on Distributed Computing (DISC) (2019b), pp. 12:1\u201312:17"},{"issue":"2","key":"9484_CR37","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1007\/s00145-021-09377-0","volume":"34","author":"R Cohen","year":"2021","unstructured":"R.\u00a0Cohen, S.\u00a0Coretti, J.\u00a0A. Garay, V.\u00a0Zikas. Round-preserving parallel composition of probabilistic-termination cryptographic protocols. J. Cryptol. 34(2):12 (2021)","journal-title":"J. Cryptol."},{"key":"9484_CR38","doi-asserted-by":"crossref","unstructured":"S.\u00a0Cohen, I.\u00a0Keidar, A.\u00a0Spiegelman, Not a COINcidence: Sub-quadratic asynchronous Byzantine agreement WHP, in Proceedings of the 34th International Symposium on Distributed Computing (DISC) (2020), pp. 25:1\u201325:17","DOI":"10.1145\/3382734.3405708"},{"key":"9484_CR39","doi-asserted-by":"crossref","unstructured":"S.\u00a0Coretti, J.A. Garay, M.\u00a0Hirt, V.\u00a0Zikas, Constant-round asynchronous multi-party computation based on one-way functions, in 22nd International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), Part II, vol. 10032 (2016), pp. 998\u20131021","DOI":"10.1007\/978-3-662-53890-6_33"},{"key":"9484_CR40","doi-asserted-by":"crossref","unstructured":"I.\u00a0Damg\u00e5rd, Y.\u00a0Ishai, Constant-round multiparty computation using a black-box pseudorandom generator, in 24th Annual International Cryptology Conference (CRYPTO) (2005), pp. 378\u2013394","DOI":"10.1007\/11535218_23"},{"key":"9484_CR41","doi-asserted-by":"crossref","unstructured":"I.\u00a0Damg\u00e5rd, Y.\u00a0Ishai, Scalable secure multiparty computation, in 25th Annual International Cryptology Conference (CRYPTO) (2006), pp. 501\u2013520","DOI":"10.1007\/11818175_30"},{"key":"9484_CR42","doi-asserted-by":"crossref","unstructured":"I.\u00a0Damg\u00e5rd, J.B. Nielsen, Scalable and unconditionally secure multiparty computation, in 26th Annual International Cryptology Conference (CRYPTO) (2007), pp. 572\u2013590","DOI":"10.1007\/978-3-540-74143-5_32"},{"key":"9484_CR43","doi-asserted-by":"crossref","unstructured":"I.\u00a0Damg\u00e5rd, Y.\u00a0Ishai, M.\u00a0Kr\u00f8igaard, J.B. Nielsen, A.D. Smith, Scalable multiparty computation with nearly optimal work and resilience, in 27th Annual International Cryptology Conference (CRYPTO) (2008), pp. 241\u2013261","DOI":"10.1007\/978-3-540-85174-5_14"},{"key":"9484_CR44","doi-asserted-by":"crossref","unstructured":"I.\u00a0Damg\u00e5rd, Y.\u00a0Ishai, M.\u00a0Kr\u00f8igaard, Perfectly secure multiparty computation and the computational overhead of cryptography, in 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2010), pp. 445\u2013465","DOI":"10.1007\/978-3-642-13190-5_23"},{"key":"9484_CR45","doi-asserted-by":"crossref","unstructured":"I.\u00a0Damg\u00e5rd, S.\u00a0Faust, C.\u00a0Hazay, Secure two-party computation with low communication, in Proceedings of the 9th Theory of Cryptography Conference (TCC) (2012), pp. 54\u201374","DOI":"10.1007\/978-3-642-28914-9_4"},{"issue":"3","key":"9484_CR46","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/s00446-016-0284-9","volume":"30","author":"V Dani","year":"2017","unstructured":"V.\u00a0Dani, V.\u00a0King, M.\u00a0Movahedi, J.\u00a0Saia, M.\u00a0Zamani, Secure multi-party computation in large networks. Distrib. Comput. 30(3), 193\u2013229 (2017)","journal-title":"Distrib. Comput."},{"key":"9484_CR47","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Desmedt, Y.\u00a0Frankel, Threshold cryptosystems, in 8th Annual International Cryptology Conference (CRYPTO) (1989), pp. 307\u2013315","DOI":"10.1007\/0-387-34805-0_28"},{"issue":"1","key":"9484_CR48","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1016\/0196-6774(82)90004-9","volume":"3","author":"D Dolev","year":"1982","unstructured":"D.\u00a0Dolev, The Byzantine generals strike again. J. Algorithms 3(1), 14\u201330 (1982)","journal-title":"J. Algorithms"},{"issue":"1","key":"9484_CR49","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1145\/2455.214112","volume":"32","author":"D Dolev","year":"1985","unstructured":"D.\u00a0Dolev, R.\u00a0Reischuk. Bounds on information exchange for Byzantine agreement. J. ACM 32(1), 191\u2013204 (1985)","journal-title":"J. ACM"},{"issue":"5","key":"9484_CR50","doi-asserted-by":"publisher","first-page":"975","DOI":"10.1137\/0217061","volume":"17","author":"C Dwork","year":"1988","unstructured":"C.\u00a0Dwork, D.\u00a0Peleg, N.\u00a0Pippenger, E.\u00a0Upfal, Fault tolerance in networks of bounded degree. SIAM J. Comput. 17(5), 975\u2013988 (1988)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9484_CR51","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1007\/BF01843568","volume":"1","author":"MJ Fischer","year":"1986","unstructured":"M.J. Fischer, N.A. Lynch, M. Merritt. Easy impossibility proofs for distributed consensus problems. Distrib. Comput. 1(1), 26\u201339 (1986)","journal-title":"Distrib. Comput."},{"key":"9484_CR52","doi-asserted-by":"crossref","unstructured":"J.A. Garay, Y.\u00a0Moses, Fully polynomial Byzantine agreement in $$\\text{t }+1$$ rounds, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing (STOC) (1993), pp. 31\u201341","DOI":"10.1145\/167088.167101"},{"key":"9484_CR53","unstructured":"M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., New York, NY, USA, 1979). ISBN 0716710447"},{"issue":"1","key":"9484_CR54","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1006\/inco.2000.2881","volume":"164","author":"R Gennaro","year":"2001","unstructured":"R.\u00a0Gennaro, S.\u00a0Jarecki, H.\u00a0Krawczyk, T.\u00a0Rabin. Robust threshold DSS signatures. Inf. Comput. 164(1), 54\u201384 (2001)","journal-title":"Inf. Comput."},{"key":"9484_CR55","doi-asserted-by":"crossref","unstructured":"C.\u00a0Gentry, D.\u00a0Wichs, Separating succinct non-interactive arguments from all falsifiable assumptions, in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC) (2011), pp. 99\u2013108","DOI":"10.1145\/1993636.1993651"},{"key":"9484_CR56","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, Foundations of Cryptography: Volume 2: Basic Applications (Cambridge University Press, 2004)","DOI":"10.1017\/CBO9780511721656"},{"key":"9484_CR57","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, S.\u00a0Micali, A.\u00a0Wigderson, 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) (1987), pp. 218\u2013229","DOI":"10.1145\/28395.28420"},{"key":"9484_CR58","doi-asserted-by":"crossref","unstructured":"D.\u00a0Gupta, A.\u00a0Sahai, On constant-round concurrent zero-knowledge from a knowledge assumption, in INDOCRYPT (2014), pp. 71\u201388","DOI":"10.1007\/978-3-319-13039-2_5"},{"key":"9484_CR59","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Harchol, I.\u00a0Abraham, B.\u00a0Pinkas, Distributed SSH key management with proactive RSA threshold signatures, in Proceedings of the 16th International Conference on Applied Cryptography and Network Security (ACNS) (2018), pp. 22\u201343","DOI":"10.1007\/978-3-319-93387-0_2"},{"key":"9484_CR60","doi-asserted-by":"crossref","unstructured":"S.\u00a0Hohenberger, B.\u00a0Waters, Synchronized aggregate signatures from the RSA assumption, in 37th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), Part II (2018), pp. 197\u2013229","DOI":"10.1007\/978-3-319-78375-8_7"},{"issue":"4","key":"9484_CR61","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s00446-008-0069-x","volume":"21","author":"D Holtby","year":"2008","unstructured":"D.\u00a0Holtby, B.M. Kapron, V.\u00a0King, Lower bound for scalable Byzantine agreement. Distrib. Comput. 21(4), 239\u2013248 (2008)","journal-title":"Distrib. Comput."},{"key":"9484_CR62","doi-asserted-by":"crossref","unstructured":"R.\u00a0Impagliazzo, M.\u00a0Luby. One-way functions are essential for complexity based cryptography (extended abstract), in Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS) (1989), pp. 230\u2013235","DOI":"10.1109\/SFCS.1989.63483"},{"issue":"4","key":"9484_CR63","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/BF00189260","volume":"9","author":"R Impagliazzo","year":"1996","unstructured":"R.\u00a0Impagliazzo, M.\u00a0Naor, Efficient cryptographic schemes provably as secure as subset sum. J. Cryptol. 9(4), 199\u2013216 (1996)","journal-title":"J. Cryptol."},{"key":"9484_CR64","first-page":"1","volume":"71","author":"K Itakura","year":"1983","unstructured":"K.\u00a0Itakura, K.\u00a0Nakamura, A public-key cryptosystem suitable for digital multisignatures. NEC Res. Dev. 71, 1\u20138 (1983)","journal-title":"NEC Res. Dev."},{"key":"9484_CR65","doi-asserted-by":"crossref","unstructured":"R.M. Karp, Reducibility among combinatorial problems, in Proceedings of a Symposium on the Complexity of Computer Computations (1972), pp. 85\u2013103","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"9484_CR66","doi-asserted-by":"crossref","unstructured":"J.\u00a0Katz, C.\u00a0Koo, On expected constant-round protocols for Byzantine agreement, in 25th Annual International Cryptology Conference (CRYPTO) (2006), pp. 445\u2013462","DOI":"10.1007\/11818175_27"},{"issue":"3","key":"9484_CR67","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/s00145-010-9069-7","volume":"24","author":"D Kidron","year":"2011","unstructured":"D.\u00a0Kidron, Y.\u00a0Lindell. Impossibility results for universal composability in public-key models and with fixed inputs. J. Cryptol. 24(3), 517\u2013544 (2011)","journal-title":"J. Cryptol."},{"key":"9484_CR68","doi-asserted-by":"crossref","unstructured":"V.\u00a0King, J.\u00a0Saia, From almost everywhere to everywhere: Byzantine agreement with $$\\tilde{O}(n^{3\/2})$$ bits, in Proceedings of the 23th International Symposium on Distributed Computing (DISC) (2009), pp. 464\u2013478","DOI":"10.1007\/978-3-642-04355-0_47"},{"key":"9484_CR69","doi-asserted-by":"crossref","unstructured":"V.\u00a0King, J.\u00a0Saia, Breaking the $$O(n^2)$$ bit barrier: Scalable Byzantine agreement with an adaptive adversary. J. ACM 58(4), 18:1\u201318:24 (2011)","DOI":"10.1145\/1989727.1989732"},{"key":"9484_CR70","doi-asserted-by":"crossref","unstructured":"V.\u00a0King, J.\u00a0Saia, V.\u00a0Sanwalani, E.\u00a0Vee, Scalable leader election, in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2006), pp. 990\u2013999","DOI":"10.1145\/1109557.1109667"},{"key":"9484_CR71","doi-asserted-by":"crossref","unstructured":"V.\u00a0King, S.\u00a0Lonargan, J.\u00a0Saia, A.\u00a0Trehan, Load balanced scalable Byzantine agreement through quorum building, with full information, in Proceedings of the 12th International Conference on Distributed Computing and Networking (ICDCN) (2011), pp. 203\u2013214","DOI":"10.1007\/978-3-642-17679-1_18"},{"key":"9484_CR72","unstructured":"L.\u00a0Lamport, Constructing Digital Signatures from a One Way Function. Technical Report CSL-98 (SRI International, 1979)"},{"issue":"3","key":"9484_CR73","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L Lamport","year":"1982","unstructured":"L.\u00a0Lamport, R.E. Shostak, M.C. Pease, The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3), 382\u2013401, (1982).","journal-title":"ACM Trans. Program. Lang. Syst."},{"key":"9484_CR74","doi-asserted-by":"crossref","unstructured":"K.\u00a0Lee, D.H. Lee, M.\u00a0Yung. Sequential aggregate signatures made shorter, in Proceedings of the 11th International Conference on Applied Cryptography and Network Security (ACNS) (2013), pp. 202\u2013217","DOI":"10.1007\/978-3-642-38980-1_13"},{"key":"9484_CR75","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.tcs.2016.02.031","volume":"645","author":"B Libert","year":"2016","unstructured":"B.\u00a0Libert, M.\u00a0Joye, M.\u00a0Yung, Born and raised distributively: Fully distributed non-interactive adaptively-secure threshold signatures with short shares. Theor. Comput. Sci. 645, 1\u201324 (2016)","journal-title":"Theor. Comput. Sci."},{"issue":"6","key":"9484_CR76","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1145\/1217856.1217857","volume":"53","author":"Y Lindell","year":"2006","unstructured":"Y.\u00a0Lindell, A.\u00a0Lysyanskaya, T.\u00a0Rabin, On the composition of authenticated Byzantine agreement. J. ACM 53(6), 881\u2013917 (2006)","journal-title":"J. ACM"},{"issue":"2","key":"9484_CR77","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/s00145-012-9126-5","volume":"26","author":"S Lu","year":"2013","unstructured":"S.\u00a0Lu, R.\u00a0Ostrovsky, A.\u00a0Sahai, H.\u00a0Shacham, B.\u00a0Waters, Sequential aggregate signatures, multisignatures, and verifiably encrypted signatures without random oracles. J. Cryptol. 26(2), 340\u2013373 (2013)","journal-title":"J. Cryptol."},{"key":"9484_CR78","doi-asserted-by":"crossref","unstructured":"A.\u00a0Lysyanskaya, S.\u00a0Micali, L.\u00a0Reyzin, H.\u00a0Shacham, Sequential aggregate signatures from trapdoor permutations, in 23rd International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2004), pp. 74\u201390","DOI":"10.1007\/978-3-540-24676-3_5"},{"key":"9484_CR79","doi-asserted-by":"crossref","unstructured":"V.\u00a0Lyubashevsky, A.\u00a0Palacio, G.\u00a0Segev, Public-key cryptographic primitives provably as secure as subset sum, in Proceedings of the 7th Theory of Cryptography Conference (TCC) (2010), pp. 382\u2013400","DOI":"10.1007\/978-3-642-11799-2_23"},{"key":"9484_CR80","doi-asserted-by":"crossref","unstructured":"R.C. Merkle, A certified digital signature, in 8th Annual International Cryptology Conference (CRYPTO) (1989), pp. 218\u2013238","DOI":"10.1007\/0-387-34805-0_21"},{"key":"9484_CR81","doi-asserted-by":"crossref","unstructured":"S.\u00a0Micali. CS proofs (extended abstracts), in Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS) (1994), pp. 436\u2013453","DOI":"10.1109\/SFCS.1994.365746"},{"key":"9484_CR82","unstructured":"S.\u00a0Micali, M.O. Rabin, S.P. Vadhan, Verifiable random functions, in Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS) (1999), pp. 120\u2013130"},{"key":"9484_CR83","doi-asserted-by":"crossref","unstructured":"S.\u00a0Micali, K.\u00a0Ohta, L.\u00a0Reyzin, Accountable-subgroup multisignatures: Extended abstract, in Proceedings of the 8th ACM Conference on Computer and Communications Security (CCS), pp. 245\u2013254 (2001)","DOI":"10.1145\/501983.502017"},{"key":"9484_CR84","doi-asserted-by":"crossref","unstructured":"J.B. Nielsen, A threshold pseudorandom function construction and its applications, in 21st Annual International Cryptology Conference (CRYPTO) (2002), pp. 401\u2013416","DOI":"10.1007\/3-540-45708-9_26"},{"issue":"2","key":"9484_CR85","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1145\/322186.322188","volume":"27","author":"MC Pease","year":"1980","unstructured":"M.C. Pease, R.E. Shostak, L.\u00a0Lamport, Reaching agreement in the presence of faults. J. ACM 27(2), 228\u2013234 (1980)","journal-title":"J. ACM"},{"key":"9484_CR86","doi-asserted-by":"crossref","unstructured":"C.\u00a0Peikert, Public-key cryptosystems from the worst-case shortest vector problem: Extended abstract, in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC) (2009), pp. 333\u2013342","DOI":"10.1145\/1536414.1536461"},{"key":"9484_CR87","doi-asserted-by":"crossref","unstructured":"T.\u00a0Rabin, A simplified approach to threshold and proactive RSA, in 17th Annual International Cryptology Conference (CRYPTO) (1998), pp. 89\u2013104","DOI":"10.1007\/BFb0055722"},{"key":"9484_CR88","doi-asserted-by":"crossref","unstructured":"T.\u00a0Rabin, M.\u00a0Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority (extended abstract), in Proceedings of the 30th Annual Symposium on Foundations of Computer Science (FOCS) (1989), pp. 73\u201385","DOI":"10.1145\/73007.73014"},{"key":"9484_CR89","doi-asserted-by":"crossref","unstructured":"O.\u00a0Regev, New lattice based cryptographic constructions, in Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC) (2003), pp. 407\u2013416","DOI":"10.1145\/780542.780603"},{"key":"9484_CR90","doi-asserted-by":"crossref","unstructured":"O.\u00a0Regev, On lattices, learning with errors, random linear codes, and cryptography, in Proceedings of the 37th Annual ACM Symposium on Theory of Computing (STOC) (2005), pp. 84\u201393","DOI":"10.1145\/1060590.1060603"},{"key":"9484_CR91","doi-asserted-by":"crossref","unstructured":"R.L. Rivest, A.\u00a0Shamir, Y.\u00a0Tauman, How to leak a secret, in 7th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT) (2001), pp. 552\u2013565","DOI":"10.1007\/3-540-45682-1_32"},{"key":"9484_CR92","doi-asserted-by":"crossref","unstructured":"V.\u00a0Shoup, Practical threshold signatures, in 19th International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT) (2000), pp. 207\u2013220","DOI":"10.1007\/3-540-45539-6_15"},{"key":"9484_CR93","doi-asserted-by":"crossref","unstructured":"P.\u00a0Valiant, Incrementally verifiable computation or proofs of knowledge imply time\/space efficiency, in Proceedings of the 5th Theory of Cryptography Conference (TCC) (2008), pp. 1\u201318","DOI":"10.1007\/978-3-540-78524-8_1"},{"key":"9484_CR94","doi-asserted-by":"crossref","unstructured":"J.\u00a0Wan, H.\u00a0Xiao, S.\u00a0Devadas, E.\u00a0Shi, Round-efficient Byzantine broadcast under strongly adaptive and majority corruptions, in Proceedings of the 18th Theory of Cryptography Conference (TCC), Part I (2020a), pp. 412\u2013456","DOI":"10.1007\/978-3-030-64375-1_15"},{"key":"9484_CR95","doi-asserted-by":"crossref","unstructured":"J.\u00a0Wan, H.\u00a0Xiao, E.\u00a0Shi, S.\u00a0Devadas, Expected constant round Byzantine broadcast under dishonest majority, in Proceedings of the 18th Theory of Cryptography Conference (TCC), Part I (2020b), pp. 381\u2013411","DOI":"10.1007\/978-3-030-64375-1_14"},{"key":"9484_CR96","doi-asserted-by":"crossref","unstructured":"A.C. Yao. Protocols for secure computations (extended abstract), in Proceedings of the 23rd Annual Symposium on Foundations of Computer Science (FOCS) (1982), pp. 160\u2013164","DOI":"10.1109\/SFCS.1982.38"},{"key":"9484_CR97","first-page":"149","volume":"2014","author":"M Zamani","year":"2014","unstructured":"M.\u00a0Zamani, M.\u00a0Movahedi, J.\u00a0Saia, Millions of millionaires: Multiparty computation in large networks. IACR Cryptol. ePrint Arch. 2014, 149 (2014)","journal-title":"IACR Cryptol. ePrint Arch."}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09484-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-023-09484-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09484-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,31]],"date-time":"2024-10-31T23:46:29Z","timestamp":1730418389000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-023-09484-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,27]]},"references-count":97,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["9484"],"URL":"https:\/\/doi.org\/10.1007\/s00145-023-09484-0","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"type":"print","value":"0933-2790"},{"type":"electronic","value":"1432-1378"}],"subject":[],"published":{"date-parts":[[2023,10,27]]},"assertion":[{"value":"7 August 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 October 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"2"}}