License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.62
URN: urn:nbn:de:0030-drops-175655
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17565/
Go to the corresponding LIPIcs Volume Portal

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

Asynchronous Multi-Party Quantum Computation

pdf-format:
LIPIcs-ITCS-2023-62.pdf (0.7 MB)

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.

BibTeX - Entry

@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/opus/volltexte/2023/17565},
  URN =		{urn:nbn:de:0030-drops-175655},
  doi =		{10.4230/LIPIcs.ITCS.2023.62},
  annote =	{Keywords: Quantum Cryptography, Multiparty Computation, Asynchronous}
}

Keywords: Quantum Cryptography, Multiparty Computation, Asynchronous
Collection: 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Issue Date: 2023
Date of publication: 01.02.2023

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI