Document Open Access Logo

Asynchronous Multi-Party Quantum Computation

Authors Vipul Goyal, Chen-Da Liu-Zhang, Justin Raizes, João Ribeiro

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2023.62.pdf
  • Filesize: 0.7 MB
  • 22 pages

Document Identifiers

Author Details

Vipul Goyal
  • Carnegie Mellon University, Pittsburgh, PA, USA
  • NTT Research, Sunnyvale, CA, USA
Chen-Da Liu-Zhang
  • NTT Research, Sunnyvale, CA, USA
Justin Raizes
  • Carnegie Mellon University, Pittsburgh, PA, USA
João Ribeiro
  • Carnegie Mellon University, Pittsburgh, PA, USA

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.
  • Liu-Zhang, Chen-Da: Work partially done while the author was at Carnegie Mellon University.

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.ITCS.2023.62

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. 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.

Subject Classification

ACM Subject Classification
  • Hardware → Quantum communication and cryptography
Keywords
  • Quantum Cryptography
  • Multiparty Computation
  • Asynchronous

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. 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. Google Scholar
  2. 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. Google Scholar
  3. Gorjan Alagic, Tommaso Gagliardoni, and Christian Majenz. Can you sign a quantum state? Quantum, 5:603, 2021. Google Scholar
  4. 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. Google Scholar
  5. 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.
  6. 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. Google Scholar
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. 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.
  19. 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.
  20. 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.
  21. 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.
  22. 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.
  23. 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.
  24. 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.
  25. 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.
  26. 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.
  27. Mark Hillery, Vladimír Bužek, and André Berthiaume. Quantum secret sharing. Physical Review A, 59(3):1829, 1999. Google Scholar
  28. 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.
  29. 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.
  30. 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.
  31. 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.
  32. 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. Google Scholar
  33. 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.
  34. 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. Google Scholar
  35. 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.
  36. 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.
  37. 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. Google Scholar
  38. 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.
  39. 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.
  40. 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. Google Scholar
  41. 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.
  42. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact