Paper 2023/827

On Concurrent Multi-Party Quantum Computation

Vipul Goyal, NTT Research, Carnegie Mellon University
Xiao Liang, NTT Research
Giulio Malavolta, Max Planck Institute for Security and Privacy

Recently, significant progress has been made toward quantumly secure multi-party computation (MPC) in the stand-alone setting. In sharp contrast, the picture of concurrently secure MPC (or even 2PC), for both classical and quantum functionalities, still remains unclear. Quantum information behaves in a fundamentally different way, making the job of adversary harder and easier at the same time. Thus, it is unclear if the positive or negative results from the classical setting still apply. This work initiates a systematic study of concurrent secure computation in the quantum setting. We obtain a mix of positive and negative results. We first show that assuming the existence of post-quantum one-way functions (PQ-OWFs), concurrently secure 2PC (and thus MPC) for quantum functionalities is impossible. Next, we focus on the bounded-concurrent setting, where we obtain simulation-sound zero-knowledge arguments for both NP and QMA, assuming PQ-OWFs. This is obtained by a new design of simulation-sound gadget, relying on the recent post-quantum non-malleable commitments by Liang, Pandey, and Yamakawa [FOCS'23], and the quantum rewinding strategy recently developed by Ananth, Chung, and La Placa [CRYPTO'21] for bounded-concurrent post-quantum ZK. Moreover, we show that our technique is general enough---It also leads to quantum-secure bounded-concurrent coin-flipping protocols, and eventually general-purpose 2PC and MPC, for both classical and quantum functionalities. All these constructions can be based on the quantum hardness of Learning with Errors.

Note: Revise funding acknowledgments.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2023
ConcurrentSecure ComputationQuantum
Contact author(s)
vipul @ cmu edu
xiao crypto @ gmail com
giulio malavolta @ hotmail it
2023-08-17: revised
2023-06-04: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-NoDerivs


      author = {Vipul Goyal and Xiao Liang and Giulio Malavolta},
      title = {On Concurrent Multi-Party Quantum Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2023/827},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.