{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,8,10]],"date-time":"2023-08-10T04:15:52Z","timestamp":1691640952889},"reference-count":88,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T00:00:00Z","timestamp":1683676800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,5,10]],"date-time":"2023-05-10T00:00:00Z","timestamp":1683676800000},"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":[[2023,7]]},"DOI":"10.1007\/s00145-023-09460-8","type":"journal-article","created":{"date-parts":[[2023,5,11]],"date-time":"2023-05-11T09:22:50Z","timestamp":1683796970000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Must the Communication Graph of MPC Protocols be an Expander?"],"prefix":"10.1007","volume":"36","author":[{"given":"Elette","family":"Boyle","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ran","family":"Cohen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Deepesh","family":"Data","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pavel","family":"Hub\u00e1\u010dek","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,5,10]]},"reference":[{"key":"9460_CR1","doi-asserted-by":"crossref","unstructured":"S.\u00a0Agarwal, R.\u00a0Cramer, R.\u00a0de\u00a0Haan, Asymptotically optimal two-round perfectly secure message transmission, in Advances in Cryptology\u2014CRYPTO 2006 (2006), pp. 394\u2013408","DOI":"10.1007\/11818175_24"},{"key":"9460_CR2","doi-asserted-by":"crossref","unstructured":"A.\u00a0Akavia, T.\u00a0Moran, Topology-hiding computation beyond logarithmic diameter, in Advances in Cryptology\u2014EUROCRYPT 2017, Part III (2017), pp. 609\u2013637","DOI":"10.1007\/978-3-319-56617-7_21"},{"key":"9460_CR3","doi-asserted-by":"crossref","unstructured":"A.\u00a0Akavia, R.\u00a0LaVigne, T.\u00a0Moran, Topology-hiding computation on all graphs, in Advances in Cryptology\u2014CRYPTO 2017, Part I (2017), pp. 447\u2013467","DOI":"10.1007\/978-3-319-63688-7_15"},{"key":"9460_CR4","doi-asserted-by":"crossref","unstructured":"M.\u00a0Ball, E.\u00a0Boyle, T.\u00a0Malkin, T.\u00a0Moran, Exploring the boundaries of topology-hiding computation, in Advances in Cryptology\u2014EUROCRYPT 2018, Part III (2018), pp. 294\u2013325","DOI":"10.1007\/978-3-319-78372-7_10"},{"key":"9460_CR5","doi-asserted-by":"crossref","unstructured":"M.\u00a0Ball, E.\u00a0Boyle, R.\u00a0Cohen, T.\u00a0Malkin, T.\u00a0Moran, Is information-theoretic topology-hiding computation possible? in Proceedings of the 17th Theory of Cryptography Conference, TCC 2019, Part I (2019), pp. 502\u2013530","DOI":"10.1007\/978-3-030-36030-6_20"},{"key":"9460_CR6","doi-asserted-by":"crossref","unstructured":"D.\u00a0Beaver, Foundations of secure interactive computing, in Advances in Cryptology\u2014CRYPTO \u201991 (1991), pp. 377\u2013391","DOI":"10.1007\/3-540-46766-1_31"},{"key":"9460_CR7","doi-asserted-by":"crossref","unstructured":"D.\u00a0Beaver, S.\u00a0Micali, P.\u00a0Rogaway, The round complexity of secure protocols (extended abstract), in Proceedings of the 22nd Annual ACM Symposium on Theory of Computing (STOC) (1990), pp. 503\u2013513","DOI":"10.1145\/100216.100287"},{"issue":"3","key":"9460_CR8","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1007\/s00446-006-0010-0","volume":"19","author":"A Beimel","year":"2007","unstructured":"A.\u00a0Beimel, On private computation in incomplete networks. Distrib. Comput. 19(3), 237\u2013252 (2007)","journal-title":"Distrib. Comput."},{"issue":"1","key":"9460_CR9","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/S0304-3975(98)00241-2","volume":"220","author":"A Beimel","year":"1999","unstructured":"A.\u00a0Beimel, M.K. Franklin, Reliable communication over partially authenticated networks. Theor. Comput. Sci. 220(1), 185\u2013210 (1999)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"9460_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00446-004-0119-y","volume":"18","author":"A Beimel","year":"2005","unstructured":"A.\u00a0Beimel, L.\u00a0Malka, Efficient reliable communication over partially authenticated networks. Distrib. Comput. 18(1), 1\u201319 (2005)","journal-title":"Distrib. Comput."},{"key":"9460_CR11","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"},{"issue":"2","key":"9460_CR12","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/BF02280836","volume":"7","author":"P Berman","year":"1993","unstructured":"P.\u00a0Berman, J.A. Garay, Fast consensus in networks of bounded degree. Distrib. Comput. 7(2), 67\u201373 (1993)","journal-title":"Distrib. Comput."},{"issue":"3","key":"9460_CR13","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s00145-005-0329-x","volume":"19","author":"M Bl\u00e4ser","year":"2006","unstructured":"M.\u00a0Bl\u00e4ser, A.\u00a0Jakoby, M.\u00a0Li\u015bkiewicz, B.\u00a0Manthey, Private computation: k-connected versus 1-connected networks. J. Cryptol. 19(3), 341\u2013357 (2006)","journal-title":"J. Cryptol."},{"issue":"1","key":"9460_CR14","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/s00224-009-9243-1","volume":"48","author":"M Bl\u00e4ser","year":"2011","unstructured":"M.\u00a0Bl\u00e4ser, A.\u00a0Jakoby, M.\u00a0Li\u015bkiewicz, B.\u00a0Manthey, Privacy in non-private environments. Theory Comput. Syst. 48(1), 211\u2013245 (2011)","journal-title":"Theory Comput. Syst."},{"key":"9460_CR15","doi-asserted-by":"crossref","unstructured":"D.\u00a0Boneh, C.\u00a0Gentry, B.\u00a0Lynn, H.\u00a0Shacham, Aggregate and verifiably encrypted signatures from bilinear maps, in Advances in Cryptology\u2014EUROCRYPT 2003 (2003), pp. 416\u2013432","DOI":"10.1007\/3-540-39200-9_26"},{"key":"9460_CR16","doi-asserted-by":"crossref","unstructured":"E.\u00a0Boyle, S.\u00a0Goldwasser, Y.\u00a0Tauman Kalai, Leakage-resilient coin tossing, in Proceedings of the 25th International Symposium on Distributed Computing (DISC) (2011), pp. 181\u2013196","DOI":"10.1007\/978-3-642-24100-0_16"},{"key":"9460_CR17","doi-asserted-by":"crossref","unstructured":"E.\u00a0Boyle, S.\u00a0Goldwasser, S.\u00a0Tessaro, Communication locality in secure multi-party computation\u2014how to run sublinear algorithms in a distributed setting, in Proceedings of the 10th Theory of Cryptography Conference, TCC 2013 (2013), pp. 356\u2013376","DOI":"10.1007\/978-3-642-36594-2_21"},{"key":"9460_CR18","doi-asserted-by":"crossref","unstructured":"E.\u00a0Boyle, K.\u00a0Chung, R.\u00a0Pass, Large-scale secure computation: Multi-party computation for (parallel) RAM programs, in Advances in Cryptology\u2014CRYPTO 2015, Part II (2015), pp. 742\u2013762","DOI":"10.1007\/978-3-662-48000-7_36"},{"key":"9460_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 Advances in Cryptology\u2014CRYPTO 2018, Part III (2018), pp. 243\u2013272","DOI":"10.1007\/978-3-319-96878-0_9"},{"key":"9460_CR20","unstructured":"E.\u00a0Boyle, R.\u00a0Cohen, A.\u00a0Goel, 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) (2021), pp. 319\u2013330"},{"key":"9460_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":"9460_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":"9460_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":"9460_CR24","doi-asserted-by":"crossref","unstructured":"A.\u00a0Cevallos, S.\u00a0Fehr, R.\u00a0Ostrovsky, Y.\u00a0Rabani, Unconditionally-secure robust secret sharing with compact shares, in Advances in Cryptology\u2014EUROCRYPT 2012 (2012), pp. 195\u2013208","DOI":"10.1007\/978-3-642-29011-4_13"},{"key":"9460_CR25","doi-asserted-by":"crossref","unstructured":"N.\u00a0Chandran, J.\u00a0A. Garay, R.\u00a0Ostrovsky, Improved fault tolerance and secure computation on sparse networks, in Proceedings of the 37th International Colloquium on Automata, Languages, and Programming (ICALP), Part II (2010), pp. 249\u2013260","DOI":"10.1007\/978-3-642-14162-1_21"},{"key":"9460_CR26","doi-asserted-by":"crossref","unstructured":"N.\u00a0Chandran, J.A. Garay, R.\u00a0Ostrovsky, Edge fault tolerance on sparse networks, in Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP), Part II (2012), pp. 452\u2013463","DOI":"10.1007\/978-3-642-31585-5_41"},{"key":"9460_CR27","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 (2015a), pp. 153\u2013162","DOI":"10.1145\/2688073.2688102"},{"issue":"4","key":"9460_CR28","doi-asserted-by":"publisher","first-page":"745","DOI":"10.1007\/s00145-013-9176-3","volume":"28","author":"N Chandran","year":"2015","unstructured":"N.\u00a0Chandran, J.\u00a0A. Garay, R.\u00a0Ostrovsky, Almost-everywhere secure computation with edge corruptions. J. Cryptol. 28(4), 745\u2013768 (2015b)","journal-title":"J. Cryptol."},{"key":"9460_CR29","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"},{"issue":"4","key":"9460_CR30","doi-asserted-by":"publisher","first-page":"1157","DOI":"10.1007\/s00145-016-9245-5","volume":"30","author":"R Cohen","year":"2017","unstructured":"R.\u00a0Cohen, Y.\u00a0Lindell, Fairness versus guaranteed output delivery in secure multiparty computation. J. Cryptol. 30(4), 1157\u20131186 (2017)","journal-title":"J. Cryptol."},{"issue":"2","key":"9460_CR31","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1007\/s00145-017-9264-x","volume":"31","author":"R Cohen","year":"2018","unstructured":"R.\u00a0Cohen, I.\u00a0Haitner, E.\u00a0Omri, L.\u00a0Rotem, Characterization of secure multiparty computation without broadcast. J. Cryptol. 31(2), 587\u2013609 (2018)","journal-title":"J. Cryptol."},{"issue":"3","key":"9460_CR32","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 (2019)","journal-title":"J. Cryptol."},{"issue":"2","key":"9460_CR33","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.A. Garay, V.\u00a0Zikas, Round-preserving parallel composition of probabilistic-termination cryptographic protocols. J. Cryptol. 34(2), 12 (2021)","journal-title":"J. Cryptol."},{"key":"9460_CR34","doi-asserted-by":"crossref","unstructured":"R.\u00a0Cramer, I.\u00a0Damg\u00e5rd, S.\u00a0Dziembowski, M.\u00a0Hirt, T.\u00a0Rabin, Efficient multiparty computations secure against an adaptive adversary, in Advances in Cryptology\u2014EUROCRYPT \u201999 (1999), pp. 311\u2013326","DOI":"10.1007\/3-540-48910-X_22"},{"key":"9460_CR35","doi-asserted-by":"crossref","unstructured":"R.\u00a0Cramer, I.\u00a0Damg\u00e5rd, S.\u00a0Fehr, On the cost of reconstructing a secret, or VSS with optimal reconstruction phase, in Advances in Cryptology\u2014CRYPTO 2001 (2001), pp. 503\u2013523","DOI":"10.1007\/3-540-44647-8_30"},{"key":"9460_CR36","doi-asserted-by":"crossref","unstructured":"I.\u00a0Damg\u00e5rd, Y.\u00a0Ishai, Constant-round multiparty computation using a black-box pseudorandom generator, in Advances in Cryptology\u2014CRYPTO 2005 (2005), pp. 378\u2013394","DOI":"10.1007\/11535218_23"},{"issue":"3","key":"9460_CR37","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."},{"issue":"1","key":"9460_CR38","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":"4","key":"9460_CR39","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1137\/0212045","volume":"12","author":"D Dolev","year":"1983","unstructured":"D.\u00a0Dolev, R.\u00a0Strong, Authenticated algorithms for Byzantine agreement. SIAM J. Comput. 12(4), 656\u2013666 (1983)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9460_CR40","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1145\/138027.138036","volume":"40","author":"D Dolev","year":"1993","unstructured":"D.\u00a0Dolev, C.\u00a0Dwork, O.\u00a0Waarts, M.\u00a0Yung, Perfectly secure message transmission. J. ACM 40(1), 17\u201347 (1993)","journal-title":"J. ACM"},{"issue":"1","key":"9460_CR41","doi-asserted-by":"publisher","first-page":"291","DOI":"10.4086\/toc.2010.v006a012","volume":"6","author":"Z Dvir","year":"2010","unstructured":"Z.\u00a0Dvir, A.\u00a0Wigderson, Monotone expanders: Constructions and applications. Theory Comput. 6(1), 291\u2013308 (2010)","journal-title":"Theory Comput."},{"issue":"5","key":"9460_CR42","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."},{"key":"9460_CR43","unstructured":"U.\u00a0Feige, Noncryptographic selection protocols, in Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS) (1999), pp. 142\u2013153"},{"issue":"4","key":"9460_CR44","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1137\/S0097539790187084","volume":"26","author":"P Feldman","year":"1997","unstructured":"P.\u00a0Feldman, S.\u00a0Micali, An optimal probabilistic protocol for synchronous byzantine agreement. SIAM J. Comput. 26(4), 873\u2013933 (1997)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9460_CR45","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.\u00a0Merritt, Easy impossibility proofs for distributed consensus problems. Distrib. Computi. 1(1), 26\u201339 (1986)","journal-title":"Distrib. Comput."},{"key":"9460_CR46","doi-asserted-by":"crossref","unstructured":"M.\u00a0Fitzi, M.K. Franklin, J.A. Garay, H.V. Simhadri, Towards optimal and efficient perfectly secure message transmission, in Proceedings of the Fourth Theory of Cryptography Conference, TCC 2007 (2007), pp. 311\u2013322","DOI":"10.1007\/978-3-540-70936-7_17"},{"issue":"3","key":"9460_CR47","doi-asserted-by":"publisher","first-page":"437","DOI":"10.1137\/S0895480198335215","volume":"18","author":"MK Franklin","year":"2004","unstructured":"M.K. Franklin, M.\u00a0Yung. Secure hypergraphs: Privacy from partial broadcast. SIAM J. Discrete Math. 18(3), 437\u2013450 (2004)","journal-title":"SIAM J. Discrete Math."},{"key":"9460_CR48","doi-asserted-by":"crossref","unstructured":"J.A. Garay, Y.\u00a0Moses, Fully polynomial byzantine agreement in 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":"9460_CR49","doi-asserted-by":"crossref","unstructured":"J.A. Garay, R.\u00a0Ostrovsky, Almost-everywhere secure computation, in Advances in Cryptology\u2014EUROCRYPT 2008 (2008), pp. 307\u2013323","DOI":"10.1007\/978-3-540-78967-3_18"},{"key":"9460_CR50","doi-asserted-by":"crossref","unstructured":"J.A. Garay, J.\u00a0Katz, R.\u00a0Kumaresan, H.\u00a0Zhou, Adaptively secure broadcast, revisited, in Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing (PODC) (2011), pp. 179\u2013186","DOI":"10.1145\/1993806.1993832"},{"key":"9460_CR51","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, Foundations of Cryptography\u2014VOLUME 2: Basic Applications (Cambridge University Press, 2004)","DOI":"10.1017\/CBO9780511721656"},{"key":"9460_CR52","doi-asserted-by":"crossref","unstructured":"O.\u00a0Goldreich, A sample of samplers: A computational perspective on sampling, in Studies in Complexity and Cryptography (Springer, 2011), pp. 302\u2013332","DOI":"10.1007\/978-3-642-22670-0_24"},{"key":"9460_CR53","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":"9460_CR54","doi-asserted-by":"crossref","unstructured":"S.\u00a0Goldwasser, L.A. Levin, Fair computation of general functions in presence of immoral majority, in Advances in Cryptology\u2014CRYPTO \u201990 (1990), pp. 77\u201393","DOI":"10.1007\/3-540-38424-3_6"},{"key":"9460_CR55","doi-asserted-by":"crossref","unstructured":"R.\u00a0Gradwohl, S.P. Vadhan, D.\u00a0Zuckerman, Random selection with an adversarial majority, in Advances in Cryptology\u2014CRYPTO 2006 (2006), pp. 409\u2013426","DOI":"10.1007\/11818175_25"},{"key":"9460_CR56","doi-asserted-by":"crossref","unstructured":"S.\u00a0Halevi, Y.\u00a0Lindell, B.\u00a0Pinkas, Secure computation on the web: Computing without simultaneous interaction, in Advances in Cryptology\u2014CRYPTO 2011 (2011), pp. 132\u2013150","DOI":"10.1007\/978-3-642-22792-9_8"},{"key":"9460_CR57","doi-asserted-by":"crossref","unstructured":"S.\u00a0Halevi, Y.\u00a0Ishai, A.\u00a0Jain, E.\u00a0Kushilevitz, T.\u00a0Rabin, Secure multiparty computation with general interaction patterns, in Proceedings of the 7th Annual Innovations in Theoretical Computer Science (ITCS) Conference (2016), pp. 157\u2013168","DOI":"10.1145\/2840728.2840760"},{"key":"9460_CR58","doi-asserted-by":"crossref","unstructured":"D.\u00a0Harnik, Y.\u00a0Ishai, E.\u00a0Kushilevitz, How many oblivious transfers are needed for secure multiparty computation? in Advances in Cryptology\u2014CRYPTO 2007 (2007), pp. 284\u2013302","DOI":"10.1007\/978-3-540-74143-5_16"},{"key":"9460_CR59","doi-asserted-by":"crossref","unstructured":"M.\u00a0Hirt, V.\u00a0Zikas, Adaptively secure broadcast, in Advances in Cryptology\u2014EUROCRYPT 2010 (2010), pp. 466\u2013485","DOI":"10.1007\/978-3-642-13190-5_24"},{"key":"9460_CR60","doi-asserted-by":"crossref","unstructured":"M.\u00a0Hirt, U.\u00a0Maurer, D.\u00a0Tschudi, V.\u00a0Zikas, Network-hiding communication and applications to multi-party protocols, in Advances in Cryptology\u2014CRYPTO 2016, Part II (2016), pp. 335\u2013365","DOI":"10.1007\/978-3-662-53008-5_12"},{"issue":"4","key":"9460_CR61","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"S.\u00a0Hoory, N.\u00a0Linial, A.\u00a0Wigderson, Expander graphs and their applications. Bull. Amer. Math. Soc. 43(4), 439\u2013561 (2006)","journal-title":"Bull. Amer. Math. Soc."},{"key":"9460_CR62","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Ishai, R.\u00a0Ostrovsky, V.\u00a0Zikas, Secure multi-party computation with identifiable abort, in Advances in Cryptology\u2014CRYPTO 2014, Part II (2014), pp. 369\u2013386","DOI":"10.1007\/978-3-662-44381-1_21"},{"key":"9460_CR63","unstructured":"B.M. Kapron, D.\u00a0Kempe, V.\u00a0King, J.\u00a0Saia, V.\u00a0Sanwalani, Fast asynchronous byzantine agreement and leader election with full information, in Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (2008), pp. 1038\u20131047"},{"key":"9460_CR64","doi-asserted-by":"crossref","unstructured":"V.\u00a0King, J.\u00a0Saia, From almost everywhere to everywhere: Byzantine agreement with \u00f5(n$${}^{\\text{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":"9460_CR65","unstructured":"V.\u00a0King, J.\u00a0Saia, Breaking the O(n$${}^{\\text{2 }}$$) bit barrier: Scalable byzantine agreement with an adaptive adversary, in Proceedings of the 29th Annual ACM Symposium on Principles of Distributed Computing (PODC) (2010), pp. 420\u2013429"},{"key":"9460_CR66","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":"9460_CR67","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":"9460_CR68","doi-asserted-by":"crossref","unstructured":"M.V.N.A. Kumar, P.R. Goundan, K.\u00a0Srinathan, C.P. Rangan, On perfectly secure communication over arbitrary networks, in Proceedings of the 21th Annual ACM Symposium on Principles of Distributed Computing (PODC) (2002), pp. 193\u2013202","DOI":"10.1145\/571825.571858"},{"key":"9460_CR69","doi-asserted-by":"crossref","unstructured":"R.\u00a0Kumaresan, S.\u00a0Raghuraman, A.\u00a0Sealfon, Network oblivious transfer, in Advances in Cryptology\u2014CRYPTO 2016, Part II (2016), pp. 366\u2013396","DOI":"10.1007\/978-3-662-53008-5_13"},{"issue":"11","key":"9460_CR70","doi-asserted-by":"publisher","first-page":"5223","DOI":"10.1109\/TIT.2009.2030434","volume":"55","author":"K Kurosawa","year":"2009","unstructured":"K.\u00a0Kurosawa, K.\u00a0Suzuki, Truly efficient 2-round perfectly secure message transmission scheme. IEEE Trans. Inf. Theory 55(11), 5223\u20135232 (2009)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"9460_CR71","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 Trans. Program. Lang. Syst. 4(3), 382\u2013401 (1982)","journal-title":"ACM Trans. Program. Lang. Syst."},{"issue":"2","key":"9460_CR72","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":"9460_CR73","doi-asserted-by":"crossref","unstructured":"A.\u00a0Lysyanskaya, S.\u00a0Micali, L.\u00a0Reyzin, H.\u00a0Shacham, Sequential aggregate signatures from trapdoor permutations, in Advances in Cryptology\u2014EUROCRYPT 2004 (2004), pp. 74\u201390","DOI":"10.1007\/978-3-540-24676-3_5"},{"key":"9460_CR74","doi-asserted-by":"crossref","unstructured":"S.\u00a0Micali, P.\u00a0Rogaway, Secure computation (abstract), in Advances in Cryptology\u2014CRYPTO \u201991 (1991), pp. 392\u2013404","DOI":"10.1007\/3-540-46766-1_32"},{"key":"9460_CR75","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) (2001), pp. 245\u2013254","DOI":"10.1145\/501983.502017"},{"key":"9460_CR76","doi-asserted-by":"crossref","unstructured":"T.\u00a0Moran, I.\u00a0Orlov, S.\u00a0Richelson, Topology-hiding computation, in Proceedings of the 12th Theory of Cryptography Conference, TCC 2015, Part I (2015), pp. 159\u2013181","DOI":"10.1007\/978-3-662-46494-6_8"},{"issue":"2","key":"9460_CR77","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":"9460_CR78","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"},{"issue":"1","key":"9460_CR79","first-page":"53","volume":"126","author":"HM Sayeed","year":"1996","unstructured":"H.M. Sayeed, H.\u00a0Abu-Amara, Efficient perfectly secure message transmission in synchronous networks. Inf. Control 126(1), 53\u201361 (1996)","journal-title":"Inf. Control"},{"key":"9460_CR80","doi-asserted-by":"crossref","unstructured":"T.\u00a0Seito, T.\u00a0Aikawa, J.\u00a0Shikata, T.\u00a0Matsumoto, Information-theoretically secure key-insulated multireceiver authentication codes, in Progress in Cryptology\u2014AFRICACRYPT 2010 (2010), pp. 148\u2013165","DOI":"10.1007\/978-3-642-12678-9_10"},{"key":"9460_CR81","doi-asserted-by":"crossref","unstructured":"J.\u00a0Shikata, G.\u00a0Hanaoka, Y.\u00a0Zheng, H.\u00a0Imai, Security notions for unconditionally secure signature schemes, in Advances in Cryptology\u2014EUROCRYPT 2002 (2002), pp. 434\u2013449","DOI":"10.1007\/3-540-46035-7_29"},{"key":"9460_CR82","doi-asserted-by":"crossref","unstructured":"G.\u00a0Spini, G.Z\u00e9mor, Perfectly secure message transmission in two rounds, in Proceedings of the 14th Theory of Cryptography Conference, TCC 2016-B, Part I (2016), pp. 286\u2013304","DOI":"10.1007\/978-3-662-53641-4_12"},{"key":"9460_CR83","doi-asserted-by":"crossref","unstructured":"K.\u00a0Srinathan, A.\u00a0Narayanan, C.P. Rangan, Optimal perfectly secure message transmission, in Advances in Cryptology\u2014CRYPTO 2004 (2004), pp. 545\u2013561","DOI":"10.1007\/978-3-540-28628-8_33"},{"key":"9460_CR84","doi-asserted-by":"crossref","unstructured":"C.\u00a0Swanson, D.R. Stinson, Unconditionally secure signature schemes revisited, in Proceedings of the 5th International Conference on Information Theoretic Security ICITS (2011), pp. 100\u2013116","DOI":"10.1007\/978-3-642-20728-0_10"},{"key":"9460_CR85","doi-asserted-by":"crossref","unstructured":"E.\u00a0Upfal, Tolerating linear number of faults in networks of bounded degree, in Proceedings of the 11th Annual ACM Symposium on Principles of Distributed Computing (PODC) (1992), pp. 83\u201389","DOI":"10.1145\/135419.135437"},{"key":"9460_CR86","doi-asserted-by":"crossref","unstructured":"V.V. Vazirani, M.\u00a0Yannakakis, Suboptimal cuts: Their enumeration, weight and number (extended abstract), in Proceedings of the 19th International Colloquium on Automata, Languages, and Programming (ICALP) (1992), pp. 366\u2013377","DOI":"10.1007\/3-540-55719-9_88"},{"issue":"3","key":"9460_CR87","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s00453-009-9284-5","volume":"56","author":"L Yeh","year":"2010","unstructured":"L.\u00a0Yeh, B.\u00a0Wang, H.\u00a0Su, Efficient algorithms for the problems of enumerating cuts by non-decreasing weights. Algorithmica 56(3), 297\u2013312 (2010)","journal-title":"Algorithmica"},{"issue":"4","key":"9460_CR88","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1002\/(SICI)1098-2418(199712)11:4<345::AID-RSA4>3.0.CO;2-Z","volume":"11","author":"D Zuckerman","year":"1997","unstructured":"D.\u00a0Zuckerman, Randomness-optimal oblivious sampling. Random Struct. Algorithms 11(4), 345\u2013367 (1997)","journal-title":"Random Struct. Algorithms"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09460-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-023-09460-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-023-09460-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T16:09:51Z","timestamp":1691597391000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-023-09460-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,10]]},"references-count":88,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,7]]}},"alternative-id":["9460"],"URL":"https:\/\/doi.org\/10.1007\/s00145-023-09460-8","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,10]]},"assertion":[{"value":"17 August 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 January 2023","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 April 2023","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 May 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"20"}}