Asynchronous Multi-Party Quantum Computation

<!DOCTYPE html> <html lang="en"> <head> <meta charset="utf-8"> <meta http-equiv="X-UA-Compatible" content="IE=edge"> <meta name="google" content="notranslate"> <meta http-equiv="Content-Language" content="en"> <meta name="viewport" content="width=device-width, initial-scale=1"> <meta name="csrf-token" content="8D9iPTGV1BVieQbRBWv1UoU4s5M1YhMODB6czfnh"> <link rel="canonical" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.62"> <meta name="DC.Publisher" content="Schloss Dagstuhl – Leibniz-Zentrum für Informatik" > <meta name="DC.Title" xml:lang="en" content="Asynchronous Multi-Party Quantum Computation" > <meta name="DC.Creator.PersonalName" content="Goyal, Vipul" > <meta name="DC.Creator.PersonalName" content="Liu-Zhang, Chen-Da" > <meta name="DC.Creator.PersonalName" content="Raizes, Justin" > <meta name="DC.Creator.PersonalName" content="Ribeiro, João" > <meta name="DC.Subject" content="Quantum Cryptography" > <meta name="DC.Subject" content="Multiparty Computation" > <meta name="DC.Subject" content="Asynchronous" > <meta name="DC.Date.created" scheme="ISO8601" content="2023-02-01" > <meta name="DC.Date.issued" scheme="ISO8601" content="2023-02-01" > <meta name="DC.Date.modified" scheme="ISO8601" content="2023-02-01" > <meta name="DC.Type" content="InProceedings" > <meta name="DC.Format" scheme="IMT" content="application/pdf" > <meta name="DC.Identifier" scheme="urn:nbn:de" content="urn:nbn:de:0030-drops-175655" > <meta name="DC.Identifier" scheme="DOI" content="10.4230/LIPIcs.ITCS.2023.62" > <meta name="DC.Identifier" scheme="URL" content="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.62" > <meta name="DC.Source" content="14th Innovations in Theoretical Computer Science Conference (ITCS 2023)" > <meta name="DC.Source.URI" content="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-251" > <meta name="DC.Language" scheme="ISO639-1" content="en" > <meta name="DC.Description" xml:lang="en" content="Multi-party quantum computation (MPQC) allows a set of parties to securely compute a quantum circuit over private quantum data. Current MPQC protocols rely on the fact that the network is synchronous, i.e., messages sent are guaranteed to be delivered within a known fixed delay upper bound, and unfortunately completely break down even when only a single message arrives late. Motivated by real-world networks, the seminal work of Ben-Or, Canetti and Goldreich (STOC'93) initiated the study of multi-party computation for classical circuits over asynchronous networks, where the network delay can be arbitrary. In this work, we begin the study of asynchronous multi-party quantum computation (AMPQC) protocols, where the circuit to compute is quantum. Our results completely characterize the optimal achievable corruption threshold: we present an n-party AMPQC protocol secure up to t < n/4 corruptions, and an impossibility result when t ≥ n/4 parties are corrupted. Remarkably, this characterization differs from the analogous classical setting, where the optimal corruption threshold is t < n/3." > <meta name="DC.Rights" scheme="DCTERMS.URI" content="https://creativecommons.org/licenses/by/4.0/legalcode" > <meta name="citation_conference_title" content="14th Innovations in Theoretical Computer Science Conference (ITCS 2023)" > <meta name="citation_doi" content="10.4230/LIPIcs.ITCS.2023.62" > <meta name="citation_firstpage" content="62:1" > <meta name="citation_lastpage" content="62:22" > <meta name="citation_title" content="Asynchronous Multi-Party Quantum Computation" > <meta name="citation_language" content="en" > <meta name="citation_keyword" content="Quantum Cryptography" > <meta name="citation_keyword" content="Multiparty Computation" > <meta name="citation_keyword" content="Asynchronous" > <meta name="citation_author" content="Goyal, Vipul" > <meta name="citation_author_institution" content="Carnegie Mellon University, Pittsburgh, PA, USA; NTT Research, Sunnyvale, CA, USA" > <meta name="citation_author" content="Liu-Zhang, Chen-Da" > <meta name="citation_author_institution" content="NTT Research, Sunnyvale, CA, USA" > <meta name="citation_author" content="Raizes, Justin" > <meta name="citation_author_institution" content="Carnegie Mellon University, Pittsburgh, PA, USA" > <meta name="citation_author" content="Ribeiro, João" > <meta name="citation_author_institution" content="Carnegie Mellon University, Pittsburgh, PA, USA" > <meta name="citation_date" content="2023" > <meta name="citation_keyword" xml:lang="en" content="Quantum Cryptography" > <meta name="citation_keyword" xml:lang="en" content="Multiparty Computation" > <meta name="citation_keyword" xml:lang="en" content="Asynchronous" > <meta name="citation_abstract_html_url" content="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.62" > <meta name="citation_pdf_url" content="https://drops.dagstuhl.de/storage/00lipics/lipics-vol251-itcs2023/LIPIcs.ITCS.2023.62/LIPIcs.ITCS.2023.62.pdf" > <meta name="citation_reference" content="Amit Agarwal, James Bartusek, Vipul Goyal, Dakshita Khurana, and Giulio Malavolta. Post-quantum multi-party computation. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology - EUROCRYPT 2021, pages 435-464. Springer International Publishing, 2021." > <meta name="citation_reference" content="D. Aharonov and M. Ben-Or. Fault-tolerant quantum computation with constant error. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC '97, pages 176-188. Association for Computing Machinery, 1997." > <meta name="citation_reference" content="Gorjan Alagic, Tommaso Gagliardoni, and Christian Majenz. Can you sign a quantum state? Quantum, 5:603, 2021." > <meta name="citation_reference" content="Bar Alon, Hao Chung, Kai-Min Chung, Mi-Ying Huang, Yi Lee, and Yu-Ching Shen. Round efficient secure multiparty quantum computation with identifiable abort. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021, pages 436-466. Springer International Publishing, 2021." > <meta name="citation_reference" content="Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam Smith, and Alain Tapp. Authentication of quantum messages. In 43rd FOCS, pages 449-458. IEEE Computer Society Press, 2002. URL: https://doi.org/10.1109/SFCS.2002.1181969." > <meta name="citation_reference" content="James Bartusek, Andrea Coladangelo, Dakshita Khurana, and Fermi Ma. On the round complexity of secure quantum computation. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021, pages 406-435. Springer International Publishing, 2021." > <meta name="citation_reference" content="Michael Ben-Or, Ran Canetti, and Oded Goldreich. Asynchronous secure computation. In 25th ACM STOC, pages 52-61. ACM Press, 1993. URL: https://doi.org/10.1145/167088.167109." > <meta name="citation_reference" content="Michael Ben-Or, Claude Crépeau, Daniel Gottesman, Avinatan Hassidim, and Adam Smith. Secure multiparty quantum computation with (only) a strict honest majority. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pages 249-260, 2006. Full version at http://crypto.cs.mcgill.ca/~crepeau/PDF/BCGHS06.pdf. URL: https://doi.org/10.1109/FOCS.2006.68." > <meta name="citation_reference" content="Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In 20th ACM STOC, pages 1-10. ACM Press, 1988. URL: https://doi.org/10.1145/62212.62213." > <meta name="citation_reference" content="Michael Ben-Or, Boaz Kelmer, and Tal Rabin. Asynchronous secure computations with optimal resilience (extended abstract). In Jim Anderson and Sam Toueg, editors, 13th ACM PODC, pages 183-192. ACM, 1994. URL: https://doi.org/10.1145/197917.198088." > <meta name="citation_reference" content="Nir Bitansky and Omri Shmueli. Post-quantum zero knowledge in constant rounds. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, 52nd ACM STOC, pages 269-279. ACM Press, 2020. URL: https://doi.org/10.1145/3357713.3384324." > <meta name="citation_reference" content="Erica Blum, Jonathan Katz, Chen-Da Liu-Zhang, and Julian Loss. Asynchronous byzantine agreement with subquadratic communication. In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020, Part I, volume 12550 of LNCS, pages 353-380. Springer, Heidelberg, 2020. URL: https://doi.org/10.1007/978-3-030-64375-1_13." > <meta name="citation_reference" content="Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, and Amit Sahai. Universally composable two-party and multi-party secure computation. In 34th ACM STOC, pages 494-503. ACM Press, 2002. URL: https://doi.org/10.1145/509907.509980." > <meta name="citation_reference" content="David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols (extended abstract). In 20th ACM STOC, pages 11-19. ACM Press, 1988. URL: https://doi.org/10.1145/62212.62214." > <meta name="citation_reference" content="Annick Chopard, Martin Hirt, and Chen-Da Liu-Zhang. On communication-efficient asynchronous MPC with adaptive security. In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part II, volume 13043 of LNCS, pages 35-65. Springer, Heidelberg, 2021. URL: https://doi.org/10.1007/978-3-030-90453-1_2." > <meta name="citation_reference" content="Ashish Choudhury. Optimally-resilient unconditionally-secure asynchronous multi-party computation revisited. Cryptology ePrint Archive, Report 2020/906, 2020. URL: https://eprint.iacr.org/2020/906." > <meta name="citation_reference" content="Ashish Choudhury, Martin Hirt, and Arpita Patra. Asynchronous multiparty computation with linear communication complexity. In Proceedings of the 27th International Symposium on Distributed Computing - Volume 8205, DISC 2013, pages 388-402. Springer-Verlag, 2013. URL: https://doi.org/10.1007/978-3-642-41527-2_27." > <meta name="citation_reference" content="Ashish Choudhury and Arpita Patra. Optimally resilient asynchronous MPC with linear communication complexity. In Proceedings of the 2015 International Conference on Distributed Computing and Networking, ICDCN '15. Association for Computing Machinery, 2015. URL: https://doi.org/10.1145/2684464.2684470." > <meta name="citation_reference" content="Richard Cleve, Daniel Gottesman, and Hoi-Kwong Lo. How to share a quantum secret. Physical Review Letters, 83:648-651, 1999. URL: https://doi.org/10.1103/PhysRevLett.83.648." > <meta name="citation_reference" content="Ran Cohen. Asynchronous secure multiparty computation in constant time. In Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, and Bo-Yin Yang, editors, PKC 2016, Part II, volume 9615 of LNCS, pages 183-207. Springer, Heidelberg, 2016. URL: https://doi.org/10.1007/978-3-662-49387-8_8." > <meta name="citation_reference" content="Claude Crépeau, Daniel Gottesman, and Adam Smith. Secure multi-party quantum computation. In 34th ACM STOC, pages 643-652. ACM Press, 2002. URL: https://doi.org/10.1145/509907.510000." > <meta name="citation_reference" content="Ivan Damgård and Carolin Lunemann. Quantum-secure coin-flipping and applications. In Mitsuru Matsui, editor, ASIACRYPT 2009, volume 5912 of LNCS, pages 52-69. Springer, Heidelberg, 2009. URL: https://doi.org/10.1007/978-3-642-10366-7_4." > <meta name="citation_reference" content="Yfke Dulek, Alex B. Grilo, Stacey Jeffery, Christian Majenz, and Christian Schaffner. Secure multi-party quantum computation with a dishonest majority. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part III, volume 12107 of LNCS, pages 729-758. Springer, Heidelberg, 2020. URL: https://doi.org/10.1007/978-3-030-45727-3_25." > <meta name="citation_reference" content="Frédéric Dupuis, Jesper Buus Nielsen, and Louis Salvail. Actively secure two-party evaluation of any quantum operation. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 794-811. Springer, Heidelberg, 2012. URL: https://doi.org/10.1007/978-3-642-32009-5_46." > <meta name="citation_reference" content="Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In Alfred Aho, editor, 19th ACM STOC, pages 218-229. ACM Press, 1987. URL: https://doi.org/10.1145/28395.28420." > <meta name="citation_reference" content="Sean Hallgren, Adam Smith, and Fang Song. Classical cryptographic protocols in a quantum world. In Phillip Rogaway, editor, CRYPTO 2011, volume 6841 of LNCS, pages 411-428. Springer, Heidelberg, 2011. URL: https://doi.org/10.1007/978-3-642-22792-9_23." > <meta name="citation_reference" content="Mark Hillery, Vladimír Bužek, and André Berthiaume. Quantum secret sharing. Physical Review A, 59(3):1829, 1999." > <meta name="citation_reference" content="Martin Hirt, Jesper Buus Nielsen, and Bartosz Przydatek. Cryptographic asynchronous multi-party computation with optimal resilience (extended abstract). In Ronald Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS, pages 322-340. Springer, Heidelberg, 2005. URL: https://doi.org/10.1007/11426639_19." > <meta name="citation_reference" content="Martin Hirt, Jesper Buus Nielsen, and Bartosz Przydatek. Asynchronous multi-party computation with quadratic communication. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, ICALP 2008, Part II, volume 5126 of LNCS, pages 473-485. Springer, Heidelberg, 2008. URL: https://doi.org/10.1007/978-3-540-70583-3_39." > <meta name="citation_reference" content="Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. Founding cryptography on oblivious transfer - efficiently. In David Wagner, editor, CRYPTO 2008, volume 5157 of LNCS, pages 572-591. Springer, Heidelberg, 2008. URL: https://doi.org/10.1007/978-3-540-85174-5_32." > <meta name="citation_reference" content="Chen-Da Liu-Zhang, Julian Loss, Ueli Maurer, Tal Moran, and Daniel Tschudi. MPC with synchronous security and asynchronous responsiveness. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part III, volume 12493 of LNCS, pages 92-119. Springer, Heidelberg, 2020. URL: https://doi.org/10.1007/978-3-030-64840-4_4." > <meta name="citation_reference" content="Carolin Lunemann and Jesper Buus Nielsen. Fully simulatable quantum-secure coin-flipping and applications. In Abderrahmane Nitaj and David Pointcheval, editors, AFRICACRYPT 11, volume 6737 of LNCS, pages 21-40. Springer, Heidelberg, 2011." > <meta name="citation_reference" content="Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. URL: https://doi.org/10.1017/CBO9780511976667." > <meta name="citation_reference" content="Arpita Patra, Ashish Choudhary, and Chandrasekharan Pandu Rangan. Simple and efficient asynchronous byzantine agreement with optimal resilience. In Proceedings of the 28th ACM symposium on Principles of distributed computing, pages 92-101, 2009." > <meta name="citation_reference" content="Arpita Patra, Ashish Choudhary, and C. Pandu Rangan. Efficient statistical asynchronous verifiable secret sharing with optimal resilience. In Kaoru Kurosawa, editor, ICITS 09, volume 5973 of LNCS, pages 74-92. Springer, Heidelberg, 2010. URL: https://doi.org/10.1007/978-3-642-14496-7_7." > <meta name="citation_reference" content="Arpita Patra, Ashish Choudhury, and C. Pandu Rangan. Efficient asynchronous verifiable secret sharing and multiparty computation. Journal of Cryptology, 28(1):49-109, 2015. URL: https://doi.org/10.1007/s00145-013-9172-7." > <meta name="citation_reference" content="B. Prabhu, K. Srinathan, and C. Pandu Rangan. Asynchronous unconditionally secure computation: An efficiency improvement. In Alfred Menezes and Palash Sarkar, editors, INDOCRYPT 2002, volume 2551 of LNCS, pages 93-107. Springer, Heidelberg, 2002." > <meta name="citation_reference" content="Tal Rabin and Michael Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In 21st ACM STOC, pages 73-85. ACM Press, 1989. URL: https://doi.org/10.1145/73007.73014." > <meta name="citation_reference" content="Peter W. Shor. Fault-tolerant quantum computation. In 37th FOCS, pages 56-65. IEEE Computer Society Press, 1996. URL: https://doi.org/10.1109/SFCS.1996.548464." > <meta name="citation_reference" content="K. Srinathan and C. Pandu Rangan. Efficient asynchronous secure multiparty distributed computation. In Bimal K. Roy and Eiji Okamoto, editors, INDOCRYPT 2000, volume 1977 of LNCS, pages 117-129. Springer, Heidelberg, 2000." > <meta name="citation_reference" content="Dominique Unruh. Universally composable quantum multi-party computation. In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 486-505. Springer, Heidelberg, 2010. URL: https://doi.org/10.1007/978-3-642-13190-5_25." > <meta name="citation_reference" content="Andrew Chi-Chih Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd FOCS, pages 80-91. IEEE Computer Society Press, 1982. URL: https://doi.org/10.1109/SFCS.1982.45." > <script type="application/json+ld"> {"@context":"https:\/\/schema.org\/","@type":"WebPage","mainEntity":{"@type":"ScholarlyArticle","@id":"#document17546","name":"Asynchronous Multi-Party Quantum Computation","abstract":"Multi-party quantum computation (MPQC) allows a set of parties to securely compute a quantum circuit over private quantum data. Current MPQC protocols rely on the fact that the network is synchronous, i.e., messages sent are guaranteed to be delivered within a known fixed delay upper bound, and unfortunately completely break down even when only a single message arrives late. \r\nMotivated by real-world networks, the seminal work of Ben-Or, Canetti and Goldreich (STOC'93) initiated the study of multi-party computation for classical circuits over asynchronous networks, where the network delay can be arbitrary. In this work, we begin the study of asynchronous multi-party quantum computation (AMPQC) protocols, where the circuit to compute is quantum.\r\nOur results completely characterize the optimal achievable corruption threshold: we present an n-party AMPQC protocol secure up to t < n\/4 corruptions, and an impossibility result when t \u2265 n\/4 parties are corrupted. Remarkably, this characterization differs from the analogous classical setting, where the optimal corruption threshold is t < n\/3.","keywords":["Quantum Cryptography","Multiparty Computation","Asynchronous"],"author":[{"@type":"Person","name":"Goyal, Vipul","givenName":"Vipul","familyName":"Goyal","email":"mailto:vipul@cmu.edu","affiliation":"Carnegie Mellon University, Pittsburgh, PA, USA"},{"@type":"Person","name":"Liu-Zhang, Chen-Da","givenName":"Chen-Da","familyName":"Liu-Zhang","email":"mailto:chen-da.liuzhang@ntt-research.com","affiliation":"NTT Research, Sunnyvale, CA, USA","funding":"Work partially done while the author was at Carnegie Mellon University."},{"@type":"Person","name":"Raizes, Justin","givenName":"Justin","familyName":"Raizes","email":"mailto:jraizes@andrew.cmu.edu","affiliation":"Carnegie Mellon University, Pittsburgh, PA, USA"},{"@type":"Person","name":"Ribeiro, Jo\u00e3o","givenName":"Jo\u00e3o","familyName":"Ribeiro","email":"mailto:jlourenc@cs.cmu.edu","affiliation":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"position":62,"dateCreated":"2023-02-01","datePublished":"2023-02-01","isAccessibleForFree":true,"license":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode","copyrightHolder":[{"@type":"Person","name":"Goyal, Vipul","givenName":"Vipul","familyName":"Goyal","email":"mailto:vipul@cmu.edu","affiliation":"Carnegie Mellon University, Pittsburgh, PA, USA"},{"@type":"Person","name":"Liu-Zhang, Chen-Da","givenName":"Chen-Da","familyName":"Liu-Zhang","email":"mailto:chen-da.liuzhang@ntt-research.com","affiliation":"NTT Research, Sunnyvale, CA, USA","funding":"Work partially done while the author was at Carnegie Mellon University."},{"@type":"Person","name":"Raizes, Justin","givenName":"Justin","familyName":"Raizes","email":"mailto:jraizes@andrew.cmu.edu","affiliation":"Carnegie Mellon University, Pittsburgh, PA, USA"},{"@type":"Person","name":"Ribeiro, Jo\u00e3o","givenName":"Jo\u00e3o","familyName":"Ribeiro","email":"mailto:jlourenc@cs.cmu.edu","affiliation":"Carnegie Mellon University, Pittsburgh, PA, USA"}],"copyrightYear":"2023","creativeWorkStatus":"Published","inLanguage":"en-US","identifier":"https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2023.62","funding":"Research supported in part by the NSF award 1916939, DARPA SIEVE program, a gift from Ripple, a DoE NETL award, a JP Morgan Faculty Fellowship, a PNC center for financial services innovation award, and a Cylab seed funding award.","publisher":"Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik","citation":["https:\/\/doi.org\/10.1109\/SFCS.2002.1181969","https:\/\/doi.org\/10.1145\/167088.167109","https:\/\/doi.org\/10.1109\/FOCS.2006.68","https:\/\/doi.org\/10.1145\/62212.62213","https:\/\/doi.org\/10.1145\/197917.198088","https:\/\/doi.org\/10.1145\/3357713.3384324","https:\/\/doi.org\/10.1007\/978-3-030-64375-1_13","https:\/\/doi.org\/10.1145\/509907.509980","https:\/\/doi.org\/10.1145\/62212.62214","https:\/\/doi.org\/10.1007\/978-3-030-90453-1_2","https:\/\/eprint.iacr.org\/2020\/906","https:\/\/doi.org\/10.1007\/978-3-642-41527-2_27","https:\/\/doi.org\/10.1145\/2684464.2684470","https:\/\/doi.org\/10.1103\/PhysRevLett.83.648","https:\/\/doi.org\/10.1007\/978-3-662-49387-8_8","https:\/\/doi.org\/10.1145\/509907.510000","https:\/\/doi.org\/10.1007\/978-3-642-10366-7_4","https:\/\/doi.org\/10.1007\/978-3-030-45727-3_25","https:\/\/doi.org\/10.1007\/978-3-642-32009-5_46","https:\/\/doi.org\/10.1145\/28395.28420","https:\/\/doi.org\/10.1007\/978-3-642-22792-9_23","https:\/\/doi.org\/10.1007\/11426639_19","https:\/\/doi.org\/10.1007\/978-3-540-70583-3_39","https:\/\/doi.org\/10.1007\/978-3-540-85174-5_32","https:\/\/doi.org\/10.1007\/978-3-030-64840-4_4","https:\/\/doi.org\/10.1017\/CBO9780511976667","https:\/\/doi.org\/10.1007\/978-3-642-14496-7_7","https:\/\/doi.org\/10.1007\/s00145-013-9172-7","https:\/\/doi.org\/10.1145\/73007.73014","https:\/\/doi.org\/10.1109\/SFCS.1996.548464","https:\/\/doi.org\/10.1007\/978-3-642-13190-5_25","https:\/\/doi.org\/10.1109\/SFCS.1982.45"],"pageStart":"62:1","pageEnd":"62:22","accessMode":"textual","accessModeSufficient":"textual","isPartOf":{"@type":"PublicationVolume","@id":"#volume6454","volumeNumber":251,"name":"14th Innovations in Theoretical Computer Science Conference (ITCS 2023)","dateCreated":"2023-02-01","datePublished":"2023-02-01","editor":{"@type":"Person","name":"Tauman Kalai, Yael","givenName":"Yael","familyName":"Tauman Kalai","email":"mailto:yaelism@gmail.com","affiliation":"Microsoft Research New England, Cambridge, USA"},"isAccessibleForFree":true,"publisher":"Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik","hasPart":"#document17546","isPartOf":{"@type":"Periodical","@id":"#series116","name":"Leibniz International Proceedings in Informatics","issn":"1868-8969","isAccessibleForFree":true,"publisher":"Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik","hasPart":"#volume6454"}}}} </script> <title>Asynchronous Multi-Party Quantum Computation</title> <link rel="icon" href="https://drops.dagstuhl.de/favicon.ico"> <link rel="stylesheet" href="https://drops.dagstuhl.de/css/app.css?drops-core-2024-12-02.1"> </head> <body> <nav class="navbar main fixed-top navbar-expand-lg navbar-light bg-light"> <div class="container-fluid"> <a class="navbar-brand" href="https://www.dagstuhl.de"> <img class="lzi-logo" src="https://drops.dagstuhl.de/images/LZI-Logo.jpg" width="84" height="62" alt="Schloss Dagstuhl - LZI - Logo"> </a> <button class="navbar-toggler" type="button" data-bs-toggle="collapse" data-bs-target="#navbarSupportedContent" aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation"> <span class="navbar-toggler-icon"></span> </button> <div class="collapse navbar-collapse" id="navbarSupportedContent"> <ul class="navbar-nav me-auto mb-2 mb-lg-0"> <li class="nav-item" style="white-space: nowrap"> <a class="nav-link" href="https://drops.dagstuhl.de"> <i class="bi bi-house large-icon"></i> DROPS </a> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownSeries" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-journals large-icon"></i> Series </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/LIPIcs"> LIPIcs – Leibniz International Proceedings in Informatics </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/OASIcs"> OASIcs – Open Access Series in Informatics </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/DFU"> Dagstuhl Follow-Ups </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/series/DagAnnRep"> Schloss Dagstuhl Jahresbericht </a> </li> <li class="dropdown-divider"></li> <li> <a class="dropdown-item" href="/#discontinued-series">Discontinued Series</a> </li> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownJournals" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-journal large-icon"></i> Journals </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DARTS"> DARTS – Dagstuhl Artifacts Series </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DagRep"> Dagstuhl Reports </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/DagMan"> Dagstuhl Manifestos </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/LITES"> LITES – Leibniz Transactions on Embedded Systems </a> </li> <li><a class="dropdown-item" href="https://drops.dagstuhl.de/entities/journal/TGDK"> TGDK – Transactions on Graph Data and Knowledge </a> </li> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownConferences" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-people large-icon"></i> Conferences </a> <ul class="dropdown-menu conference-dropdown" aria-labelledby="navbarDropdown"> <div class="row"> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AFT"> AFT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AIB"> AIB </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/AofA"> AofA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/APPROX"> APPROX </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ATMOS"> ATMOS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CALCO"> CALCO </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CCC"> CCC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CONCUR"> CONCUR </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/COSIT"> COSIT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CP"> CP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CPM"> CPM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/CSL"> CSL </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DISC"> DISC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DITAM"> DITAM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/DNA"> DNA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ECOOP"> ECOOP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ECRTS"> ECRTS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ESA"> ESA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FAB"> FAB </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FMBC"> FMBC </a> </li> </div> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FORC"> FORC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FSCD"> FSCD </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FSTTCS"> FSTTCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/FUN"> FUN </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/GD"> GD </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/GIScience"> GIScience </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICALP"> ICALP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICDT"> ICDT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ICPEC"> ICPEC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/IPEC"> IPEC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/iPMVM"> iPMVM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ISAAC"> ISAAC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITC"> ITC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITCS"> ITCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/ITP"> ITP </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/LDK"> LDK </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/MFCS"> MFCS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/Microservices"> Microservices </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/NG-RES"> NG-RES </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/OPODIS"> OPODIS </a> </li> </div> <div class="col-sm-4 nav-conference-col"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/PARMA"> PARMA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/RANDOM"> RANDOM </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SAND"> SAND </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SAT"> SAT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SEA"> SEA </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SLATE"> SLATE </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SNAPL"> SNAPL </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SoCG"> SoCG </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/STACS"> STACS </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/SWAT"> SWAT </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TIME"> TIME </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/Tokenomics"> Tokenomics </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TQC"> TQC </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/TYPES"> TYPES </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/WABI"> WABI </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/conference/WCET"> WCET </a> </li> </div> </div> </ul> </li> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" href="#" id="navbarDropdownArtifacts" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-braces-asterisk large-icon"></i> Artifacts </a> <ul class="dropdown-menu" aria-labelledby="navbarDropdown"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/collection/supplementary-materials"> Supplementary Materials (Software, Datasets, ...) </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/collection/dblp"> dblp Artifacts </a> </li> <li class="dropdown-divider"></li> <li> <a class="dropdown-item" href="/entities/journal/DARTS"> DARTS (Evaluated Artifacts) </a> </li> </ul> </li> </ul> <form class="navbar-search d-flex" action="https://drops.dagstuhl.de/search" method="post"> <input type="hidden" name="_token" value="8D9iPTGV1BVieQbRBWv1UoU4s5M1YhMODB6czfnh" autocomplete="off"> <div class="input-group"> <input class="form-control" type="search" placeholder="Search" aria-label="Search" name="term" autocomplete="off" maxlength="600"> <button class="btn btn-outline-success" type="submit"> <i class="bi bi-search" style="color: #000"></i> </button> </div> </form> <ul class="navbar-nav nav-metadata"> <li class="nav-item dropdown"> <a class="nav-link dropdown-toggle" id="navbarDropdownMetadata" role="button" data-bs-toggle="dropdown" aria-expanded="false"> <i class="bi bi-database-down large-icon"></i><span class="nav-text-metadata">Metadata Export</span> </a> <ul class="dropdown-menu dropdown-metadata" aria-labelledby="navbarDropdownMetadata"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/metadata">Metadata Export</a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/oai?verb=Identify" target="_blank">OAI Interface</a> </li> </ul> </li> </ul> </div> </div> </nav> <div id="app" data-release="drops-core-2024-12-02.1" class="container "> <div id="_top-of-page"></div> <div class="fixed-search-button"><i class="bi bi-search"></i></div> <div class="document-details"> <section class="mt-3 mb-5 title"> <div class="entity-type document"> <div class="row"> <div class="col-lg-3 entity-type-name"> <i class="bi bi-file-earmark"></i> Document <img src="https://drops.dagstuhl.de/images/open-access-logo.png" width="80" alt="Open Access Logo" style="transform: translate(1em, -0.2em);"> </div> <div class="col-lg-9"> <input id="doi" type="text" style="position: fixed; top: -50vh" value="https://doi.org/10.4230/LIPIcs.ITCS.2023.62"> <div class="sharing-section"> <span class="permalink"> <span> <code><span class="hide-mobile">https://doi.org/</span>10.4230/LIPIcs.ITCS.2023.62</code> <span class="btn btn-clipboard copy-to-clipboard" title="Copy to clipboard" data-selector="doi"> <i class="bi bi-clipboard" aria-hidden="true"></i> <i class="bi bi-check -hidden" aria-hidden="true"></i> </span> </span> </span> <span class="sharing-buttons"> <a class="btn sharing-btn facebook" href="https://facebook.com/sharer/sharer.php?u=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.ITCS.2023.62" target="_blank" rel="noopener" aria-hidden="true"> <i class="bi bi-facebook"></i> </a> <a class="btn sharing-btn reddit" href="https://www.reddit.com/submit?url=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.ITCS.2023.62&title=Asynchronous+Multi-Party+Quantum+Computation" target="_blank" rel="noopener" aria-hidden="true"> <i class="bi bi-reddit"></i> </a> <a class="btn sharing-btn twitter" href="https://twitter.com/intent/tweet/?text=Asynchronous+Multi-Party+Quantum+Computation&url=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.ITCS.2023.62" target="_blank" rel="noopener" aria-hidden="true"> <svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" fill="currentColor" class="bi bi-twitter-x" viewBox="0 0 16 16"> <path d="M12.6.75h2.454l-5.36 6.142L16 15.25h-4.937l-3.867-5.07-4.425 5.07H.316l5.733-6.57L0 .75h5.063l3.495 4.633L12.601.75Zm-.86 13.028h1.36L4.323 2.145H2.865l8.875 11.633Z"/> </svg> </a> <a class="btn sharing-btn email" href="mailto:?subject=Asynchronous+Multi-Party+Quantum+Computation&body=https%3A%2F%2Fdoi.org%2F10.4230%2FLIPIcs.ITCS.2023.62" target="_self" rel="noopener" aria-hidden="true"> <svg xmlns="http://www.w3.org/2000/svg" width="16" height="16" viewBox="0 0 24 24" fill="currentColor"> <path d="M22 4H2C.9 4 0 4.9 0 6v12c0 1.1.9 2 2 2h20c1.1 0 2-.9 2-2V6c0-1.1-.9-2-2-2zM7.25 14.43l-3.5 2c-.08.05-.17.07-.25.07-.17 0-.34-.1-.43-.25-.14-.24-.06-.55.18-.68l3.5-2c.24-.14.55-.06.68.18.14.24.06.55-.18.68zm4.75.07c-.1 0-.2-.03-.27-.08l-8.5-5.5c-.23-.15-.3-.46-.15-.7.15-.22.46-.3.7-.14L12 13.4l8.23-5.32c.23-.15.54-.08.7.15.14.23.07.54-.16.7l-8.5 5.5c-.08.04-.17.07-.27.07zm8.93 1.75c-.1.16-.26.25-.43.25-.08 0-.17-.02-.25-.07l-3.5-2c-.24-.13-.32-.44-.18-.68s.44-.32.68-.18l3.5 2c.24.13.32.44.18.68z"/> </svg> </a> </span> <span class="sharing-buttons"> <span class="dropdown"> <a class="btn sharing-btn metadata dropdown-toggle" href="#" role="button" data-bs-toggle="dropdown" aria-expanded="false"><i class="bi bi-download"></i></a> <ul class="dropdown-menu dropdown-menu-end"> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.62/metadata/xml"> Export XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.62/metadata/acm-xml"> Export ACM-XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.62/metadata/doaj-xml"> Export DOAJ-XML </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.62/metadata/schema-org"> Export Schema.org </a> </li> <li> <a class="dropdown-item" href="https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.62/metadata/bibtex"> Export BibTeX </a> </li> </ul> </span> </span> </div> </div> </div> </div> <hr> <h1>Asynchronous Multi-Party Quantum Computation</h1> <h3 class="mt-2 authors"> Authors <a href="#author-details" style="font-size: 0.8em; padding-right: 1em"><i class="bi bi-info-circle"></i></a> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Goyal, Vipul" class="name">Vipul Goyal</a>, </span> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Liu-Zhang, Chen-Da" class="name">Chen-Da Liu-Zhang</a>, </span> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Raizes, Justin" class="name">Justin Raizes</a>, </span> <span class="author"> <a href="https://drops.dagstuhl.de/search/documents?author=Ribeiro, João" class="name">João Ribeiro</a> </span> </h3> <hr> <ul class="mt-4"> <li> <span style="margin-right: 10px; ">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-book-half"></i> Volume: </span> <a href="https://drops.dagstuhl.de/entities/volume/LIPIcs-volume-251">14th Innovations in Theoretical Computer Science Conference (ITCS 2023) </a> <br> <span style="margin-right: 10px; visibility: hidden;">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-journals"></i> Series: </span> <a href="https://drops.dagstuhl.de/entities/series/LIPIcs">Leibniz International Proceedings in Informatics (LIPIcs)</a> <br> <span style="margin-right: 10px; visibility: hidden;">Part of:</span> <span style="white-space: nowrap"> <i class="bi bi-people"></i> Conference: </span> <a href="https://drops.dagstuhl.de/entities/conference/ITCS">Innovations in Theoretical Computer Science Conference (ITCS)</a> </li> <li class="mt-2">License:   <a href="https://creativecommons.org/licenses/by/4.0/legalcode"> <img class="license-logo" src="https://drops.dagstuhl.de/images/cc-by.png" alt="CC-BY Logo"> Creative Commons Attribution 4.0 International license </a> </li> <li>Publication Date: 2023-02-01 </li> </ul> <hr> </section> <a class="fixed-pdf-button" href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol251-itcs2023/LIPIcs.ITCS.2023.62/LIPIcs.ITCS.2023.62.pdf"><i class="bi bi-file-earmark-pdf-fill" style="color:red"></i> PDF </a> <div class="row mt-2"> <div class="col-lg-4 mt-2"> <section class="thumbnail"> <a href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol251-itcs2023/LIPIcs.ITCS.2023.62/LIPIcs.ITCS.2023.62.pdf"><img src="https://drops.dagstuhl.de/storage/00lipics/lipics-vol251-itcs2023/thumbnails/LIPIcs.ITCS.2023.62/LIPIcs.ITCS.2023.62.png" alt="Thumbnail PDF"></a> </section> <section class="files mt-5"> <h2>File</h2> <div class="content"> <div> <a href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol251-itcs2023/LIPIcs.ITCS.2023.62/LIPIcs.ITCS.2023.62.pdf"><i class="bi bi-file-earmark-pdf-fill" style="color:red"></i> LIPIcs.ITCS.2023.62.pdf</a> <ul> <li>Filesize: 0.7 MB</li> <li>22 pages</li> </ul> </div> </div> </section> <section class="identifiers mt-3"> <h2>Document Identifiers</h2> <div class="content"> <ul> <li><b>DOI:</b> <a href="https://doi.org/10.4230/LIPIcs.ITCS.2023.62">10.4230/LIPIcs.ITCS.2023.62</a></li> <li><b>URN:</b> <a href="https://nbn-resolving.org/process-urn-form?identifier=urn:nbn:de:0030-drops-175655&verb=FULL">urn:nbn:de:0030-drops-175655</a></li> </ul> </div> </section> <section class="authors mt-3" id="author-details"> <h2>Author Details</h2> <div class="author person-details"> <div> <i class="bi bi-person-fill"></i> <span class="name"><b>Vipul Goyal</b></span> <a href="https://www.cs.cmu.edu/~goyal/"><i class="bi bi-house"></i></a> <a href="mailto:vipul@cmu.edu"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Goyal, Vipul"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Carnegie Mellon University, Pittsburgh, PA, USA </li> <li class="affiliation">NTT Research, Sunnyvale, CA, USA </li> </ul> </div> <div class="author person-details"> <div> <i class="bi bi-person-fill"></i> <span class="name"><b>Chen-Da Liu-Zhang</b></span> <a href="https://sites.google.com/view/chendaliu"><i class="bi bi-house"></i></a> <a href="mailto:chen-da.liuzhang@ntt-research.com"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Liu-Zhang, Chen-Da"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">NTT Research, Sunnyvale, CA, USA </li> </ul> </div> <div class="author person-details"> <div> <i class="bi bi-person-fill"></i> <span class="name"><b>Justin Raizes</b></span> <a href="https://sites.google.com/view/justinraizes"><i class="bi bi-house"></i></a> <a href="mailto:jraizes@andrew.cmu.edu"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Raizes, Justin"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Carnegie Mellon University, Pittsburgh, PA, USA </li> </ul> </div> <div class="author person-details"> <div> <i class="bi bi-person-fill"></i> <span class="name"><b>João Ribeiro</b></span> <a href="https://sites.google.com/site/joaorib94/"><i class="bi bi-house"></i></a> <a href="mailto:jlourenc@cs.cmu.edu"><i class="bi bi-envelope"></i></a> <a href="https://drops.dagstuhl.de/search/documents?author=Ribeiro, João"><small><i class="bi bi-search"></i></small></a> </div> <ul> <li class="affiliation">Carnegie Mellon University, Pittsburgh, PA, USA </li> </ul> </div> </section> <section class="related-version mt-3"> <h2>Funding</h2> <div class="content"> Research supported in part by the NSF award 1916939, DARPA SIEVE program, a gift from Ripple, a DoE NETL award, a JP Morgan Faculty Fellowship, a PNC center for financial services innovation award, and a Cylab seed funding award. <ul> <li><b>Liu-Zhang, Chen-Da</b>: Work partially done while the author was at Carnegie Mellon University.</li> </ul> </div> </section> </div> <div class="col-lg-8 mt-2"> <section class="cite-as mt-3"> <h2>Cite As <span class="btn btn-primary btn-xs" style="float: right" data-bs-toggle="modal" data-bs-target="#bibtex-modal">Get BibTex</span></h2> <div class="content"> Vipul Goyal, Chen-Da Liu-Zhang, Justin Raizes, and João Ribeiro. Asynchronous Multi-Party Quantum Computation. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 62:1-62:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) <a href="https://doi.org/10.4230/LIPIcs.ITCS.2023.62">https://doi.org/10.4230/LIPIcs.ITCS.2023.62</a> </div> <div class="modal fade" id="bibtex-modal" tabindex="-1" aria-labelledby="bibtexModalLabel" aria-hidden="true"> <div class="modal-dialog modal-dialog-centered"> <div class="modal-content"> <div class="modal-header"> <h5 class="modal-title" id="bibtexModalLabel">BibTex</h5> <button type="button" class="btn-close" data-bs-dismiss="modal" aria-label="Close"></button> </div> <div class="modal-body"> <pre class="bibtex">@InProceedings{goyal_et_al:LIPIcs.ITCS.2023.62, author = {Goyal, Vipul and Liu-Zhang, Chen-Da and Raizes, Justin and Ribeiro, Jo\~{a}o}, title = {{Asynchronous Multi-Party Quantum Computation}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {62:1--62:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.62}, URN = {urn:nbn:de:0030-drops-175655}, doi = {10.4230/LIPIcs.ITCS.2023.62}, annote = {Keywords: Quantum Cryptography, Multiparty Computation, Asynchronous} }</pre> <div style="overflow: hidden"> <textarea style="position: absolute; top: -400vh" id="bibtex-input">@InProceedings{goyal_et_al:LIPIcs.ITCS.2023.62, author = {Goyal, Vipul and Liu-Zhang, Chen-Da and Raizes, Justin and Ribeiro, Jo\~{a}o}, title = {{Asynchronous Multi-Party Quantum Computation}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {62:1--62:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.62}, URN = {urn:nbn:de:0030-drops-175655}, doi = {10.4230/LIPIcs.ITCS.2023.62}, annote = {Keywords: Quantum Cryptography, Multiparty Computation, Asynchronous} }</textarea> </div> </div> <div class="modal-footer"> <button type="button" class="btn btn-secondary" data-bs-dismiss="modal">Close</button> <button type="button" class="btn btn-primary copy-to-clipboard" data-selector="bibtex-input"><i class="bi bi-clipboard"></i> Copy BibTex To Clipboard<span class="bi bi-check -hidden" style="padding-left: 1em; font-weight: bold"></span></button> </div> </div> </div> </div> </section> <section class="abstract"> <h2>Abstract</h2> <pre class="content" style="white-space: -moz-pre-wrap; white-space: -o-pre-wrap; word-wrap: break-word; white-space: pre-wrap;">Multi-party quantum computation (MPQC) allows a set of parties to securely compute a quantum circuit over private quantum data. Current MPQC protocols rely on the fact that the network is synchronous, i.e., messages sent are guaranteed to be delivered within a known fixed delay upper bound, and unfortunately completely break down even when only a single message arrives late. Motivated by real-world networks, the seminal work of Ben-Or, Canetti and Goldreich (STOC'93) initiated the study of multi-party computation for classical circuits over asynchronous networks, where the network delay can be arbitrary. In this work, we begin the study of asynchronous multi-party quantum computation (AMPQC) protocols, where the circuit to compute is quantum. Our results completely characterize the optimal achievable corruption threshold: we present an n-party AMPQC protocol secure up to t < n/4 corruptions, and an impossibility result when t ≥ n/4 parties are corrupted. Remarkably, this characterization differs from the analogous classical setting, where the optimal corruption threshold is t < n/3.</pre> </section> <section class="subject-classifications mt-3"> <h2>Subject Classification</h2> <div class="acm-subject-classifications"> <h5>ACM Subject Classification</h5> <div class="content"> <ul> <li>Hardware → Quantum communication and cryptography</li> </ul> </div> </div> <div class="keywords "> <h5>Keywords</h5> <div class="content"> <ul class="list-style-comma"> <li>Quantum Cryptography</li> <li>Multiparty Computation</li> <li>Asynchronous</li> </ul> </div> </div> </section> <section class="metrics mt-3"> <h2>Metrics</h2> <div class="content"> <ul> <li> <a href="#" class="btn-statistics" data-entity="document/10.4230/LIPIcs.ITCS.2023.62" data-title="Asynchronous Multi-Party Quantum Computation"> <i class="bi bi-graph-up"></i> Access Statistics </a> </li> <li> Total Accesses (updated on a weekly basis) <div class="stats-total"> <div class="stats total-downloads"> <div class="circle"> <div class="number" data-number="0">0</div> </div> <div class="label">PDF Downloads</div> </div> <div class="stats total-metadata-views"> <div class="circle"> <div class="number" data-number="0">0</div> </div> <div class="label">Metadata Views</div> </div> </div>  </li> </ul> </div> </section> <div class="offcanvas offcanvas-bottom" tabindex="-1" id="statistics-offcanvas" aria-labelledby="statistics-offcanvas"> <div class="offcanvas-header"> <h5 class="offcanvas-title"></h5> <button type="button" class="btn-close text-reset" data-bs-dismiss="offcanvas" aria-label="Close"></button> </div> <div class="offcanvas-body small" data-context=""> <div style="margin-top: 20vh" class="centered-loader"><div class="loader"></div></div> <iframe class="-hidden"></iframe> </div> </div> <section class="related-version mt-3"> <h2>Related Versions</h2> <div class="content"> <ul> <li> <b>Full Version</b> <a href="https://eprint.iacr.org/2022/1583">https://eprint.iacr.org/2022/1583</a> </li> </ul> </div> </section> <section class="references mt-3"> <h2>References</h2> <div class="content"> <ol> <li> <span> Amit Agarwal, James Bartusek, Vipul Goyal, Dakshita Khurana, and Giulio Malavolta. Post-quantum multi-party computation. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology - EUROCRYPT 2021, pages 435-464. Springer International Publishing, 2021. <a href="https://scholar.google.com/scholar?hl=en&q=Amit Agarwal, James Bartusek, Vipul Goyal, Dakshita Khurana, and Giulio Malavolta. Post-quantum multi-party computation. In Anne Canteaut and François-Xavier Standaert, editors, Advances in Cryptology - EUROCRYPT 2021, pages 435-464. Springer International Publishing, 2021." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> D. Aharonov and M. Ben-Or. Fault-tolerant quantum computation with constant error. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC '97, pages 176-188. Association for Computing Machinery, 1997. <a href="https://scholar.google.com/scholar?hl=en&q=D. Aharonov and M. Ben-Or. Fault-tolerant quantum computation with constant error. In Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC '97, pages 176-188. Association for Computing Machinery, 1997." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Gorjan Alagic, Tommaso Gagliardoni, and Christian Majenz. Can you sign a quantum state? Quantum, 5:603, 2021. <a href="https://scholar.google.com/scholar?hl=en&q=Gorjan Alagic, Tommaso Gagliardoni, and Christian Majenz. Can you sign a quantum state? Quantum, 5:603, 2021." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Bar Alon, Hao Chung, Kai-Min Chung, Mi-Ying Huang, Yi Lee, and Yu-Ching Shen. Round efficient secure multiparty quantum computation with identifiable abort. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021, pages 436-466. Springer International Publishing, 2021. <a href="https://scholar.google.com/scholar?hl=en&q=Bar Alon, Hao Chung, Kai-Min Chung, Mi-Ying Huang, Yi Lee, and Yu-Ching Shen. Round efficient secure multiparty quantum computation with identifiable abort. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021, pages 436-466. Springer International Publishing, 2021." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Howard Barnum, Claude Crépeau, Daniel Gottesman, Adam Smith, and Alain Tapp. Authentication of quantum messages. In 43rd FOCS, pages 449-458. IEEE Computer Society Press, 2002. URL: <a href="https://doi.org/10.1109/SFCS.2002.1181969">https://doi.org/10.1109/SFCS.2002.1181969</a>. </span> </li> <li> <span> James Bartusek, Andrea Coladangelo, Dakshita Khurana, and Fermi Ma. On the round complexity of secure quantum computation. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021, pages 406-435. Springer International Publishing, 2021. <a href="https://scholar.google.com/scholar?hl=en&q=James Bartusek, Andrea Coladangelo, Dakshita Khurana, and Fermi Ma. On the round complexity of secure quantum computation. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021, pages 406-435. Springer International Publishing, 2021." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Michael Ben-Or, Ran Canetti, and Oded Goldreich. Asynchronous secure computation. In 25th ACM STOC, pages 52-61. ACM Press, 1993. URL: <a href="https://doi.org/10.1145/167088.167109">https://doi.org/10.1145/167088.167109</a>. </span> </li> <li> <span> Michael Ben-Or, Claude Crépeau, Daniel Gottesman, Avinatan Hassidim, and Adam Smith. Secure multiparty quantum computation with (only) a strict honest majority. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pages 249-260, 2006. Full version at http://crypto.cs.mcgill.ca/~crepeau/PDF/BCGHS06.pdf. URL: <a href="https://doi.org/10.1109/FOCS.2006.68">https://doi.org/10.1109/FOCS.2006.68</a>. </span> </li> <li> <span> Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In 20th ACM STOC, pages 1-10. ACM Press, 1988. URL: <a href="https://doi.org/10.1145/62212.62213">https://doi.org/10.1145/62212.62213</a>. </span> </li> <li> <span> Michael Ben-Or, Boaz Kelmer, and Tal Rabin. Asynchronous secure computations with optimal resilience (extended abstract). In Jim Anderson and Sam Toueg, editors, 13th ACM PODC, pages 183-192. ACM, 1994. URL: <a href="https://doi.org/10.1145/197917.198088">https://doi.org/10.1145/197917.198088</a>. </span> </li> <li> <span> Nir Bitansky and Omri Shmueli. Post-quantum zero knowledge in constant rounds. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, 52nd ACM STOC, pages 269-279. ACM Press, 2020. URL: <a href="https://doi.org/10.1145/3357713.3384324">https://doi.org/10.1145/3357713.3384324</a>. </span> </li> <li> <span> Erica Blum, Jonathan Katz, Chen-Da Liu-Zhang, and Julian Loss. Asynchronous byzantine agreement with subquadratic communication. In Rafael Pass and Krzysztof Pietrzak, editors, TCC 2020, Part I, volume 12550 of LNCS, pages 353-380. Springer, Heidelberg, 2020. URL: <a href="https://doi.org/10.1007/978-3-030-64375-1_13">https://doi.org/10.1007/978-3-030-64375-1_13</a>. </span> </li> <li> <span> Ran Canetti, Yehuda Lindell, Rafail Ostrovsky, and Amit Sahai. Universally composable two-party and multi-party secure computation. In 34th ACM STOC, pages 494-503. ACM Press, 2002. URL: <a href="https://doi.org/10.1145/509907.509980">https://doi.org/10.1145/509907.509980</a>. </span> </li> <li> <span> David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols (extended abstract). In 20th ACM STOC, pages 11-19. ACM Press, 1988. URL: <a href="https://doi.org/10.1145/62212.62214">https://doi.org/10.1145/62212.62214</a>. </span> </li> <li> <span> Annick Chopard, Martin Hirt, and Chen-Da Liu-Zhang. On communication-efficient asynchronous MPC with adaptive security. In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part II, volume 13043 of LNCS, pages 35-65. Springer, Heidelberg, 2021. URL: <a href="https://doi.org/10.1007/978-3-030-90453-1_2">https://doi.org/10.1007/978-3-030-90453-1_2</a>. </span> </li> <li> <span> Ashish Choudhury. Optimally-resilient unconditionally-secure asynchronous multi-party computation revisited. Cryptology ePrint Archive, Report 2020/906, 2020. URL: <a href="https://eprint.iacr.org/2020/906">https://eprint.iacr.org/2020/906</a>. </span> </li> <li> <span> Ashish Choudhury, Martin Hirt, and Arpita Patra. Asynchronous multiparty computation with linear communication complexity. In Proceedings of the 27th International Symposium on Distributed Computing - Volume 8205, DISC 2013, pages 388-402. Springer-Verlag, 2013. URL: <a href="https://doi.org/10.1007/978-3-642-41527-2_27">https://doi.org/10.1007/978-3-642-41527-2_27</a>. </span> </li> <li> <span> Ashish Choudhury and Arpita Patra. Optimally resilient asynchronous MPC with linear communication complexity. In Proceedings of the 2015 International Conference on Distributed Computing and Networking, ICDCN '15. Association for Computing Machinery, 2015. URL: <a href="https://doi.org/10.1145/2684464.2684470">https://doi.org/10.1145/2684464.2684470</a>. </span> </li> <li> <span> Richard Cleve, Daniel Gottesman, and Hoi-Kwong Lo. How to share a quantum secret. Physical Review Letters, 83:648-651, 1999. URL: <a href="https://doi.org/10.1103/PhysRevLett.83.648">https://doi.org/10.1103/PhysRevLett.83.648</a>. </span> </li> <li> <span> Ran Cohen. Asynchronous secure multiparty computation in constant time. In Chen-Mou Cheng, Kai-Min Chung, Giuseppe Persiano, and Bo-Yin Yang, editors, PKC 2016, Part II, volume 9615 of LNCS, pages 183-207. Springer, Heidelberg, 2016. URL: <a href="https://doi.org/10.1007/978-3-662-49387-8_8">https://doi.org/10.1007/978-3-662-49387-8_8</a>. </span> </li> <li> <span> Claude Crépeau, Daniel Gottesman, and Adam Smith. Secure multi-party quantum computation. In 34th ACM STOC, pages 643-652. ACM Press, 2002. URL: <a href="https://doi.org/10.1145/509907.510000">https://doi.org/10.1145/509907.510000</a>. </span> </li> <li> <span> Ivan Damgård and Carolin Lunemann. Quantum-secure coin-flipping and applications. In Mitsuru Matsui, editor, ASIACRYPT 2009, volume 5912 of LNCS, pages 52-69. Springer, Heidelberg, 2009. URL: <a href="https://doi.org/10.1007/978-3-642-10366-7_4">https://doi.org/10.1007/978-3-642-10366-7_4</a>. </span> </li> <li> <span> Yfke Dulek, Alex B. Grilo, Stacey Jeffery, Christian Majenz, and Christian Schaffner. Secure multi-party quantum computation with a dishonest majority. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part III, volume 12107 of LNCS, pages 729-758. Springer, Heidelberg, 2020. URL: <a href="https://doi.org/10.1007/978-3-030-45727-3_25">https://doi.org/10.1007/978-3-030-45727-3_25</a>. </span> </li> <li> <span> Frédéric Dupuis, Jesper Buus Nielsen, and Louis Salvail. Actively secure two-party evaluation of any quantum operation. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 794-811. Springer, Heidelberg, 2012. URL: <a href="https://doi.org/10.1007/978-3-642-32009-5_46">https://doi.org/10.1007/978-3-642-32009-5_46</a>. </span> </li> <li> <span> Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or A completeness theorem for protocols with honest majority. In Alfred Aho, editor, 19th ACM STOC, pages 218-229. ACM Press, 1987. URL: <a href="https://doi.org/10.1145/28395.28420">https://doi.org/10.1145/28395.28420</a>. </span> </li> <li> <span> Sean Hallgren, Adam Smith, and Fang Song. Classical cryptographic protocols in a quantum world. In Phillip Rogaway, editor, CRYPTO 2011, volume 6841 of LNCS, pages 411-428. Springer, Heidelberg, 2011. URL: <a href="https://doi.org/10.1007/978-3-642-22792-9_23">https://doi.org/10.1007/978-3-642-22792-9_23</a>. </span> </li> <li> <span> Mark Hillery, Vladimír Bužek, and André Berthiaume. Quantum secret sharing. Physical Review A, 59(3):1829, 1999. <a href="https://scholar.google.com/scholar?hl=en&q=Mark Hillery, Vladimír Bužek, and André Berthiaume. Quantum secret sharing. Physical Review A, 59(3):1829, 1999." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Martin Hirt, Jesper Buus Nielsen, and Bartosz Przydatek. Cryptographic asynchronous multi-party computation with optimal resilience (extended abstract). In Ronald Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS, pages 322-340. Springer, Heidelberg, 2005. URL: <a href="https://doi.org/10.1007/11426639_19">https://doi.org/10.1007/11426639_19</a>. </span> </li> <li> <span> Martin Hirt, Jesper Buus Nielsen, and Bartosz Przydatek. Asynchronous multi-party computation with quadratic communication. In Luca Aceto, Ivan Damgård, Leslie Ann Goldberg, Magnús M. Halldórsson, Anna Ingólfsdóttir, and Igor Walukiewicz, editors, ICALP 2008, Part II, volume 5126 of LNCS, pages 473-485. Springer, Heidelberg, 2008. URL: <a href="https://doi.org/10.1007/978-3-540-70583-3_39">https://doi.org/10.1007/978-3-540-70583-3_39</a>. </span> </li> <li> <span> Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. Founding cryptography on oblivious transfer - efficiently. In David Wagner, editor, CRYPTO 2008, volume 5157 of LNCS, pages 572-591. Springer, Heidelberg, 2008. URL: <a href="https://doi.org/10.1007/978-3-540-85174-5_32">https://doi.org/10.1007/978-3-540-85174-5_32</a>. </span> </li> <li> <span> Chen-Da Liu-Zhang, Julian Loss, Ueli Maurer, Tal Moran, and Daniel Tschudi. MPC with synchronous security and asynchronous responsiveness. In Shiho Moriai and Huaxiong Wang, editors, ASIACRYPT 2020, Part III, volume 12493 of LNCS, pages 92-119. Springer, Heidelberg, 2020. URL: <a href="https://doi.org/10.1007/978-3-030-64840-4_4">https://doi.org/10.1007/978-3-030-64840-4_4</a>. </span> </li> <li> <span> Carolin Lunemann and Jesper Buus Nielsen. Fully simulatable quantum-secure coin-flipping and applications. In Abderrahmane Nitaj and David Pointcheval, editors, AFRICACRYPT 11, volume 6737 of LNCS, pages 21-40. Springer, Heidelberg, 2011. <a href="https://scholar.google.com/scholar?hl=en&q=Carolin Lunemann and Jesper Buus Nielsen. Fully simulatable quantum-secure coin-flipping and applications. In Abderrahmane Nitaj and David Pointcheval, editors, AFRICACRYPT 11, volume 6737 of LNCS, pages 21-40. Springer, Heidelberg, 2011." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge University Press, 2010. URL: <a href="https://doi.org/10.1017/CBO9780511976667">https://doi.org/10.1017/CBO9780511976667</a>. </span> </li> <li> <span> Arpita Patra, Ashish Choudhary, and Chandrasekharan Pandu Rangan. Simple and efficient asynchronous byzantine agreement with optimal resilience. In Proceedings of the 28th ACM symposium on Principles of distributed computing, pages 92-101, 2009. <a href="https://scholar.google.com/scholar?hl=en&q=Arpita Patra, Ashish Choudhary, and Chandrasekharan Pandu Rangan. Simple and efficient asynchronous byzantine agreement with optimal resilience. In Proceedings of the 28th ACM symposium on Principles of distributed computing, pages 92-101, 2009." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Arpita Patra, Ashish Choudhary, and C. Pandu Rangan. Efficient statistical asynchronous verifiable secret sharing with optimal resilience. In Kaoru Kurosawa, editor, ICITS 09, volume 5973 of LNCS, pages 74-92. Springer, Heidelberg, 2010. URL: <a href="https://doi.org/10.1007/978-3-642-14496-7_7">https://doi.org/10.1007/978-3-642-14496-7_7</a>. </span> </li> <li> <span> Arpita Patra, Ashish Choudhury, and C. Pandu Rangan. Efficient asynchronous verifiable secret sharing and multiparty computation. Journal of Cryptology, 28(1):49-109, 2015. URL: <a href="https://doi.org/10.1007/s00145-013-9172-7">https://doi.org/10.1007/s00145-013-9172-7</a>. </span> </li> <li> <span> B. Prabhu, K. Srinathan, and C. Pandu Rangan. Asynchronous unconditionally secure computation: An efficiency improvement. In Alfred Menezes and Palash Sarkar, editors, INDOCRYPT 2002, volume 2551 of LNCS, pages 93-107. Springer, Heidelberg, 2002. <a href="https://scholar.google.com/scholar?hl=en&q=B. Prabhu, K. Srinathan, and C. Pandu Rangan. Asynchronous unconditionally secure computation: An efficiency improvement. In Alfred Menezes and Palash Sarkar, editors, INDOCRYPT 2002, volume 2551 of LNCS, pages 93-107. Springer, Heidelberg, 2002." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Tal Rabin and Michael Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In 21st ACM STOC, pages 73-85. ACM Press, 1989. URL: <a href="https://doi.org/10.1145/73007.73014">https://doi.org/10.1145/73007.73014</a>. </span> </li> <li> <span> Peter W. Shor. Fault-tolerant quantum computation. In 37th FOCS, pages 56-65. IEEE Computer Society Press, 1996. URL: <a href="https://doi.org/10.1109/SFCS.1996.548464">https://doi.org/10.1109/SFCS.1996.548464</a>. </span> </li> <li> <span> K. Srinathan and C. Pandu Rangan. Efficient asynchronous secure multiparty distributed computation. In Bimal K. Roy and Eiji Okamoto, editors, INDOCRYPT 2000, volume 1977 of LNCS, pages 117-129. Springer, Heidelberg, 2000. <a href="https://scholar.google.com/scholar?hl=en&q=K. Srinathan and C. Pandu Rangan. Efficient asynchronous secure multiparty distributed computation. In Bimal K. Roy and Eiji Okamoto, editors, INDOCRYPT 2000, volume 1977 of LNCS, pages 117-129. Springer, Heidelberg, 2000." target="_blank" title="Google Scholar"><img style="opacity: 0.5" src="https://drops.dagstuhl.de/images/google-scholar.dark.16x16.png" alt="Google Scholar"></a> </span> </li> <li> <span> Dominique Unruh. Universally composable quantum multi-party computation. In Henri Gilbert, editor, EUROCRYPT 2010, volume 6110 of LNCS, pages 486-505. Springer, Heidelberg, 2010. URL: <a href="https://doi.org/10.1007/978-3-642-13190-5_25">https://doi.org/10.1007/978-3-642-13190-5_25</a>. </span> </li> <li> <span> Andrew Chi-Chih Yao. Theory and applications of trapdoor functions (extended abstract). In 23rd FOCS, pages 80-91. IEEE Computer Society Press, 1982. URL: <a href="https://doi.org/10.1109/SFCS.1982.45">https://doi.org/10.1109/SFCS.1982.45</a>. </span> </li> </ol> </div> </section> </div> </div> </div> </div> <span class="_feedback-button"> <i class="bi bi-question-circle"></i> <span class="text">Questions / Remarks / Feedback</span> </span> <div class="_feedback-form -hidden"> <span class="_feedback-close">X</span> <p>Feedback for Dagstuhl Publishing</p> <div> <textarea class="form-control" name="_feedback"></textarea> <input class="form-control" type="text" name="name" autocomplete="off" placeholder="Name (optional)" maxlength="60"> <input class="form-control" type="email" name="email" autocomplete="off" placeholder="Email (optional)" maxlength="60"> <br> <button class="btn btn-sm btn-default">Send</button> </div> </div> <div class="alert alert-success _feedback-success -hidden"> <span class="glyphicon glyphicon-ok"></span> <h3>Thanks for your feedback!</h3> <div>Feedback submitted</div> <button class="btn btn-white _feedback-done">OK</button> </div> <div class="alert alert-danger _feedback-error -hidden"> <span class="glyphicon glyphicon-remove"></span> <h3>Could not send message</h3> <div>Please try again later or send an <a href="mailto:publishing@dagstuhl.de">E-mail</a></div> <button class="btn btn-white _feedback-done">OK</button> </div> <a class="scroll-up-button -hidden" href="#_top-of-page"> <i class="bi bi-arrow-up-circle"></i> </a> <footer class="page-footer dark"> <div class="container"> <h5>About DROPS</h5> <p>Schloss Dagstuhl - Leibniz Center for Informatics has been operating the Dagstuhl Research Online Publication Server (short: DROPS) since 2004. DROPS enables publication of the latest research findings in a fast, uncomplicated manner, in addition to providing unimpeded, open access to them. All the requisite metadata on each publication is administered in accordance with general guidelines pertaining to online publications (cf. Dublin Core). This enables the online publications to be authorized for citation and made accessible to a wide readership on a permanent basis. Access is free of charge for readers following the open access idea which fosters unimpeded access to scientific publications. </p> <ul style="margin-top: -0.5em"> <li><a href="https://drops.dagstuhl.de/docs/about">More about DROPS</a></li> </ul> </div> <div class="container"> <div class="row"> <div class="col-lg-6"> <h5>Instructions for Authors</h5> <div class="row"> <div class="col-sm-6"> <b>Dagstuhl Series</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/lipics#author">LIPIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/oasics#author">OASIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dfu#author">Dagstuhl Follow-Ups</a></li> </ul> </div> <div class="col-sm-6"> <b>Dagstuhl Journals</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/darts#author">DARTS – Dagstuhl Artifacts Series</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagrep#author">Dagstuhl Reports</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagman#author">Dagstuhl Manifestos</a></li> <li><a href="https://submission.dagstuhl.de/series/details/lites#author">LITES</a></li> <li><a href="https://submission.dagstuhl.de/series/details/tgdk#author">TGDK – Transactions on Graph Data and Knowledge</a></li> </ul> </div> </div> </div> <div class="col-lg-6"> <h5>Instructions for Editors</h5> <div class="row"> <div class="col-sm-6"> <b>Dagstuhl Series</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/lipics#editor">LIPIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/oasics#editor">OASIcs</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dfu#editor">Dagstuhl Follow-Ups</a></li> </ul> </div> <div class="col-sm-6"> <b>Dagstuhl Journals</b><br> <ul> <li><a href="https://submission.dagstuhl.de/series/details/darts#editor">DARTS – Dagstuhl Artifacts Series</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagrep#editor">Dagstuhl Reports</a></li> <li><a href="https://submission.dagstuhl.de/series/details/dagman#editor">Dagstuhl Manifestos</a></li> <li><a href="https://submission.dagstuhl.de/series/details/lites#editor">LITES</a></li> <li><a href="https://submission.dagstuhl.de/series/details/tgdk#editor">TGDK – Transactions on Graph Data and Knowledge</a></li> </ul> </div> </div> </div> </div> </div> </footer> <div class="copyright"> © 2023-2024 <a href="https://www.dagstuhl.de">Schloss Dagstuhl – LZI GmbH</a> <a href="https://drops.dagstuhl.de/docs/about">About DROPS</a> <a href="https://drops.dagstuhl.de/docs/imprint">Imprint</a> <a href="https://drops.dagstuhl.de/docs/privacy">Privacy</a> <a href="https://www.dagstuhl.de/en/publishing/team">Contact</a> </div> <script type="text/javascript" src="https://drops.dagstuhl.de/js/jquery-3.6.0.min.js"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/app.js?drops-core-2024-12-02.1"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/popper.min.js"></script> <script type="text/javascript" src="https://drops.dagstuhl.de/js/circle-progress.js"></script> <script type="text/javascript"> $(document).ready(function() { const view = { statsServer: 'https://drops-stats.dagstuhl.de', animationStarted: false, isScrolledIntoView: function (elem) { const rect = elem.getBoundingClientRect(); const elemTop = rect.top; //const elemBottom = rect.bottom; // const elemHeight = rect.height; return (elemTop >= 0) && (elemTop <= window.innerHeight); }, progressCircle: function ($el) { $el.find('.circle').circleProgress({ value: 1, size: 80, fill: { color: '#555' }, animation: { duration: 1200 } }); }, countUp: function($el) { $el.find('.number').each(function() { const $this = $(this); const number = parseInt($this.attr('data-number')); let suffix = ''; if (number > 90000) { $this.text(Math.ceil(number/1000)+' k'); suffix = ' k'; } else if (number > 90000000) { $this.text(Math.ceil(number/1000000)+' m'); suffix = ' m'; } else { $this.text(Math.ceil(number)) } $({ Counter: 0 }).animate({ Counter: $this.text().replace(suffix, '').replace(',', '') }, { duration: 1000, easing: 'swing', step: function() { $this.text(Math.ceil(this.Counter).toString().replace(/\B(?=(\d{3})+(?!\d))/g, ",") + suffix); } }); }); }, checkVisibility: function() { const $container = $('.stats-total'); if (view.isScrolledIntoView($container[0])) { if (!view.animationStarted) { view.animationStarted = true; view.progressCircle($container); setTimeout(function() { view.countUp($container) }, 200); } } }, initialize: function() { $.ajax({ type: 'get', url: view.statsServer + '/api/external/drops2/document/10.4230/LIPIcs.ITCS.2023.62/-/stats', success: function (result) { $('.total-downloads .number').attr('data-number', result.total.downloads); $('.total-metadata-views .number').attr('data-number', result.total.clicks); window.addEventListener('scroll', view.checkVisibility); view.checkVisibility(); }, error: function () { $('.total-downloads .number').text(0); $('.total-metadata-views .number').text(0); window.addEventListener('scroll', view.checkVisibility); view.checkVisibility(); } }); } }; view.initialize(); }); </script> <script type="text/javascript"> $(document).ready(function() { const statistics = { statsServer: 'https://drops-stats.dagstuhl.de', showStatistics: function(e) { e.preventDefault(); const $offCanvas = $('#statistics-offcanvas'); const $iframe = $offCanvas.find('iframe'); const $loader = $offCanvas.find('.centered-loader'); $iframe.addClass('-hidden'); $loader.removeClass('-hidden'); $iframe[0].onload = function () { $iframe.removeClass('-hidden'); $loader.addClass('-hidden'); }.bind(this); const modeParameter = ''; const $target = $(e.currentTarget); const entityId = $target.attr('data-entity'); const title = $target.attr('data-title'); const embedUrl = statistics.statsServer + '/embed/external/drops2/' + entityId + modeParameter; let context = $offCanvas.find('.offcanvas-body').attr('data-context'); if (context === title) { context = ''; } if (context !== '') { context += '<br>'; } $offCanvas.find('.offcanvas-title').html(context + '<h2 style="font-weight: bold">' + title + '</h2>'); $offCanvas.offcanvas('show'); $offCanvas.find('iframe').attr('src', embedUrl); return false; }, initialize: function() { $('.btn-statistics').on('click', this.showStatistics); } }; statistics.initialize(); }); </script> <script type="text/javascript"> function _enableFeedback() { var $feedbackButton = $('._feedback-button, .fixed-beta-button'); var $feedbackClose = $('._feedback-close'); var $feedbackForm = $('._feedback-form'); var $feedbackSubmit = $('._feedback-form button'); var $textarea = $feedbackForm.find('textarea'); var $feedbackSuccess = $('._feedback-success'); var $feedbackError = $('._feedback-error'); var $feedbackDoneButton = $('._feedback-done'); $feedbackButton.addClass('_show'); $feedbackButton.on('click', function () { $feedbackButton.addClass('-hidden'); $feedbackForm.removeClass('-hidden'); $textarea.focus(); }); $feedbackClose.on('click', function () { $feedbackSuccess.addClass('-hidden'); $feedbackForm.addClass('-hidden'); $feedbackButton.removeClass('-hidden'); }); $feedbackDoneButton.on('click', function () { $feedbackError.addClass('-hidden'); $feedbackSuccess.addClass('-hidden'); $feedbackForm.addClass('-hidden'); $feedbackButton.removeClass('-hidden'); }); $feedbackSubmit.on('click', function () { var message = $textarea.val(); if (message === undefined) { message = ''; } if (message.trim() !== '') { $.ajax({ url: '/api/v1/feedback', type: 'post', data: { content: message, context: window.location.href, name: $('input[name="name"]').val(), email: $('input[name="email"]').val(), }, success: function (result) { if (result === 'success') { $textarea.val(''); $feedbackSuccess.removeClass('-hidden'); } else { $feedbackError.removeClass('-hidden'); } }, error: function () { $feedbackError.removeClass('-hidden'); } }); } }); } var _defer_counter = 0; function _defer(method) { if (window.jQuery) { method(); } else { if (_defer_counter < 20) { setTimeout(function () { _defer(method); console.log(_defer_counter); _defer_counter++; }, 500); } } } setTimeout(function() { _defer(_enableFeedback); }, 1000); </script> <script type="text/javascript"> $(document).ready(function() { const app = { maxScrollPos: window.innerWidth < 500 ? 100 // mobile : 400, // desktop $el : { navbarSearch: $('nav .navbar-search'), fixedSearchButton: $('.fixed-search-button'), copyToClipboard: $('.copy-to-clipboard') }, methods: { hideMenuOnScroll: function(scrollPos) { const $menu = $('nav.navbar.main'); const $stickySearch = $('.search.sticky'); const $banner = $('#_banner'); const $fixedSearchButton = $('.fixed-search-button'); if (scrollPos > app.maxScrollPos) { $menu.addClass('-hide'); $banner.addClass('-hide'); $stickySearch.addClass('-top'); $fixedSearchButton.addClass('-show'); } else { app.methods.showMenu(null, false); } }, showMenu: function(e, focus) { const $menu = $('nav.navbar.main'); const $stickySearch = $('.search.sticky'); const $banner = $('#_banner'); const $fixedSearchButton = $('.fixed-search-button'); $menu.removeClass('-hide'); $banner.removeClass('-hide'); $stickySearch.removeClass('-top'); $fixedSearchButton.removeClass('-show'); if (focus !== false) { $('.navbar-search').find('input[name="term"]').focus(); } }, showUpLinkOnScroll: function(scrollPos) { const $upLink = $('.scroll-up-button'); if (scrollPos > app.maxScrollPos) { $upLink.removeClass('-hidden'); } else { $upLink.addClass('-hidden'); } }, scrollHandler: function() { const scrollPos = $(document).scrollTop(); app.methods.hideMenuOnScroll(scrollPos); app.methods.showUpLinkOnScroll(scrollPos); }, copyToClipboard: function(e) { e.preventDefault(); const $current = $(e.currentTarget); // console.log($current.attr('data-selector')); const element = $('#'+$current.attr('data-selector'))[0]; console.log(element); element.select(); document.execCommand("copy"); const $success = $current.find('.bi-check'); $success.removeClass('-hidden'); setTimeout(function() { $success.addClass('-hidden'); }, 1000); }, initTooltips: function() { const tooltipTriggerList = [].slice.call(document.querySelectorAll('[data-bs-toggle="tooltip"]')) const tooltipList = tooltipTriggerList.map(function (tooltipTriggerEl) { return new bootstrap.Tooltip(tooltipTriggerEl) }); }, expandSearch: function() { app.$el.navbarSearch.addClass('expanded'); }, collapseSearch: function(e) { if (!$(e.currentTarget).is('button.btn-outline-success')) { app.$el.navbarSearch.removeClass('expanded'); } }, initDeepLinksTabs: function() { const innerAnchors = [ 'resource-articles', 'cfp-si-resources', 'cfp-si-autonomous-systems-and-knowledge-graphs' ]; let anchors = []; $('a[role="tab"]').each(function() { anchors.push($(this).attr('aria-controls')); }); innerAnchors.forEach(function(anchor) { if ($('#'+anchor).length > 0) { anchors.push(anchor); } }); if (anchors.length === 0) { return; } let selectedAnchor = window.location.hash.substring(1); if (anchors.indexOf(selectedAnchor) === -1) { $('#publications-tab').tab('show'); window.scrollTo(0,0); return; } if (selectedAnchor !== 'publications') { const innerAnchorIndex = innerAnchors.indexOf(selectedAnchor); // anchor sits inside tab -> open the tab first, then scroll to anchor if (innerAnchorIndex > -1) { const $tab = $('#'+selectedAnchor).closest('.tab-pane'); console.log($tab); try { $('#'+$tab.attr('id')+'-tab').tab('show'); } catch (e) { } setTimeout(function () { $('#' + selectedAnchor)[0].scrollIntoView(); }, 800); } else { try { $('#' + selectedAnchor + '-tab').tab('show'); } catch (e) { } window.scrollTo(0, 0); } } $('[data-tab-link]').on('click', function(e) { const $target = $(e.currentTarget); let href = $target.attr('href'); let scrollLink = null; if (href === '#cfp-si-list') { scrollLink = href; href = '#cfp'; } try { console.log(href); $(href+'-tab').tab('show'); } catch(e) { } console.log(scrollLink); if (scrollLink !== null) { setTimeout(function() { $(scrollLink)[0].scrollIntoView(); }, 200); } else { setTimeout(function() { window.scrollTo(0,0); }, 200); } }); } }, initialize: function() { $(window).on('scroll', app.methods.scrollHandler); $(window).on('scroll-to-top', function() { window.scrollTo(0,0) }); $(document).trigger('scroll'); // set correct status for scroll-related parts (navbar/back-to-top) on page reload app.$el.copyToClipboard.on('click', app.methods.copyToClipboard); app.$el.fixedSearchButton.on('click', app.methods.showMenu); app.$el.navbarSearch.find('input').on('click', app.methods.expandSearch) app.$el.navbarSearch.find('input').on('blur', app.methods.collapseSearch); app.methods.initTooltips(); app.methods.initDeepLinksTabs(); } }; app.initialize(); }); </script> </body> </html>

CINXE.COM

Asynchronous Multi-Party Quantum Computation