{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,3]],"date-time":"2026-11-03T22:49:53Z","timestamp":1793746193165,"version":"4.6.1"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030453879","type":"print"},{"value":"9783030453886","type":"electronic"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-45388-6_9","type":"book-chapter","created":{"date-parts":[[2020,4,28]],"date-time":"2020-04-28T23:05:47Z","timestamp":1588115147000},"page":"246-265","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":27,"title":["Sublinear-Round Byzantine Agreement Under Corrupt Majority"],"prefix":"10.1007","author":[{"given":"T.-H. Hubert","family":"Chan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rafael","family":"Pass","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elaine","family":"Shi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2020,4,29]]},"reference":[{"key":"9_CR1","doi-asserted-by":"crossref","unstructured":"Abraham, I., et al.: Communication complexity of Byzantine agreement, revisited. In: PODC (2019)","DOI":"10.1145\/3293611.3331629"},{"key":"9_CR2","doi-asserted-by":"crossref","unstructured":"Abraham, I., Devadas, S., Dolev, D., Nayak, K., Ren, L.: Synchronous Byzantine agreement with optimal resilience, expected $$o(n^2)$$ communication, and expected $$o(1)$$ rounds. In: Financial Cryptography and Data Security (FC) (2019)","DOI":"10.1007\/978-3-030-32101-7_20"},{"key":"9_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"742","DOI":"10.1007\/978-3-662-48000-7_36","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"E Boyle","year":"2015","unstructured":"Boyle, E., Chung, K.-M., Pass, R.: Large-scale secure computation: multi-party computation for (parallel) RAM programs. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 742\u2013762. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48000-7_36"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Braud-Santoni, N., Guerraoui, R., Huc, F.: Fast Byzantine agreement. In: ACM Symposium on Principles of Distributed Computing, PODC 2013, Montreal, QC, Canada, 22\u201324 July 2013, pp. 57\u201364 (2013)","DOI":"10.1145\/2484239.2484243"},{"key":"9_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"720","DOI":"10.1007\/978-3-030-17653-2_24","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2019","author":"T-H Hubert Chan","year":"2019","unstructured":"Hubert Chan, T.-H., Pass, R., Shi, E.: Consensus through herding. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11476, pp. 720\u2013749. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17653-2_24"},{"key":"9_CR6","unstructured":"Hubert Chan, T.-H., Pass, R., Shi, E.: Sublinear-round Byzantine agreement under corrupt majority (2019). Online full version of this paper. https:\/\/eprint.iacr.org\/2019\/886"},{"key":"9_CR7","unstructured":"Chen, J., Micali, S.: ALGORAND: the efficient and democratic ledger (2016). https:\/\/arxiv.org\/abs\/1607.01341"},{"issue":"3","key":"9_CR8","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1145\/65950.65956","volume":"36","author":"B Chor","year":"1989","unstructured":"Chor, B., Merritt, M., Shmoys, D.B.: Simple constant-time consensus protocols in realistic failure models. J. ACM 36(3), 591\u2013614 (1989)","journal-title":"J. ACM"},{"key":"9_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"240","DOI":"10.1007\/978-3-662-53015-3_9","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"R Cohen","year":"2016","unstructured":"Cohen, R., Coretti, S., Garay, J., Zikas, V.: Probabilistic termination and composability of cryptographic protocols. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 240\u2013269. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53015-3_9"},{"key":"9_CR10","unstructured":"Cohen, R., Haitner, I., Makriyannis, N., Orland, M., Samorodnitsky, A.: On the round complexity of randomized Byzantine agreement. In: 33rd International Symposium on Distributed Computing, DISC 2019, Budapest, Hungary, 14\u201318 October 2019, pp. 12:1\u201312:17 (2019)"},{"issue":"4","key":"9_CR11","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. SIAM COMP 12(4), 656\u2013666 (1983)","journal-title":"SIAM J. Comput. SIAM COMP"},{"issue":"4","key":"9_CR12","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":"9_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/978-3-642-04355-0_46","volume-title":"Distributed Computing","author":"M Fitzi","year":"2009","unstructured":"Fitzi, M., Nielsen, J.B.: On the number of synchronous rounds sufficient for authenticated Byzantine agreement. In: Keidar, I. (ed.) DISC 2009. LNCS, vol. 5805, pp. 449\u2013463. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-04355-0_46"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Garay, J., Katz, J., Koo, C.-Y., Ostrovsky, R.: Round complexity of authenticated broadcast with a dishonest majority. In: 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS), November 2007","DOI":"10.1109\/FOCS.2007.44"},{"key":"9_CR15","doi-asserted-by":"crossref","unstructured":"Garay, J.A., Katz, J., Kumaresan, R., Zhou, H.-S.: Adaptively secure broadcast, revisited. In: Proceedings of the 30th Annual ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, PODC 2011, pp. 179\u2013186. ACM, New York (2011)","DOI":"10.1145\/1993806.1993832"},{"key":"9_CR16","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Pavlov, E., Vaikuntanathan, V.: Fault-tolerant distributed computing in full-information networks. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), Berkeley, California, USA, 21\u201324 October 2006, pp. 15\u201326 (2006)","DOI":"10.1109\/FOCS.2006.30"},{"issue":"3","key":"9_CR17","doi-asserted-by":"publisher","first-page":"11:1","DOI":"10.1145\/2220357.2220358","volume":"59","author":"J Groth","year":"2012","unstructured":"Groth, J., Ostrovsky, R., Sahai, A.: New techniques for noninteractive zero-knowledge. J. ACM 59(3), 11:1\u201311:35 (2012)","journal-title":"J. ACM"},{"key":"9_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1007\/978-3-642-13190-5_24","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"M Hirt","year":"2010","unstructured":"Hirt, M., Zikas, V.: Adaptively secure broadcast. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 466\u2013485. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13190-5_24"},{"issue":"4","key":"9_CR19","doi-asserted-by":"publisher","first-page":"68:1","DOI":"10.1145\/1824777.1824788","volume":"6","author":"BM Kapron","year":"2010","unstructured":"Kapron, B.M., Kempe, D., King, V., Saia, J., Sanwalani, V.: Fast asynchronous Byzantine agreement and leader election with full information. ACM Trans. Algorithms 6(4), 68:1\u201368:28 (2010)","journal-title":"ACM Trans. Algorithms"},{"key":"9_CR20","unstructured":"Karlin, A., Yao, A.C.-C.: Probabilistic lower bounds for byzantine agreement. Manuscript (1986)"},{"issue":"2","key":"9_CR21","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1016\/j.jcss.2008.08.001","volume":"75","author":"J Katz","year":"2009","unstructured":"Katz, J., Koo, C.-Y.: On expected constant-round protocols for Byzantine agreement. J. Comput. Syst. Sci. 75(2), 91\u2013112 (2009)","journal-title":"J. Comput. Syst. Sci."},{"key":"9_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"357","DOI":"10.1007\/978-3-319-63688-7_12","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"A Kiayias","year":"2017","unstructured":"Kiayias, A., Russell, A., David, B., Oliynykov, R.: Ouroboros: a provably secure proof-of-stake blockchain protocol. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 357\u2013388. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_12"},{"issue":"4","key":"9_CR23","doi-asserted-by":"publisher","first-page":"18:1","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 58(4), 18:1\u201318:24 (2011)","journal-title":"J. ACM"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"King, V., Saia, J., Sanwalani, V., Vee, E.: Scalable leader election. In: SODA (2006)","DOI":"10.1145\/1109557.1109667"},{"issue":"3","key":"9_CR25","doi-asserted-by":"publisher","first-page":"382","DOI":"10.1145\/357172.357176","volume":"4","author":"L Lamport","year":"1982","unstructured":"Lamport, L., Shostak, R., Pease, M.: The Byzantine generals problem. ACM Trans. Program. Lang. Syst. 4(3), 382\u2013401 (1982)","journal-title":"ACM Trans. Program. Lang. Syst."}],"container-title":["Lecture Notes in Computer Science","Public-Key Cryptography \u2013 PKC 2020"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-45388-6_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,4,29]],"date-time":"2023-04-29T00:05:03Z","timestamp":1682726703000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-45388-6_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030453879","9783030453886"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-45388-6_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"29 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"PKC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"IACR International Conference on Public-Key Cryptography","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Edinburgh","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"United Kingdom","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2020","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 May 2020","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 May 2020","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"pkc2020","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/pkc.iacr.org\/2020\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"IACR Web Review System","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"180","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"44","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3-4","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"15","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}