Post-Quantum Multi-Party Computation in Constant Rounds

Amit Agarwal, James Bartusek, Vipul Goyal, Dakshita Khurana, Giulio MalavoltaarXiv 2020 · OpenReview

TL;DR

This paper presents the first constant-round protocols for secure multi-party computation (MPC) that are secure against malicious quantum adversaries, operating in the plain model (no trusted setup). This is achieved by developing novel techniques for quantum zero-knowledge and non-malleable commitments, overcoming the limitations of quantum state cloning.

What Problem Does This Paper Address?

The advent of quantum computers poses a significant threat to existing cryptographic protocols. While research has explored quantum-resistant cryptography, the specific problem of post-quantum multi-party computation (MPC) in the plain model (where parties communicate directly without relying on a common random string or trusted setup) has remained largely open. Existing MPC protocols, even those designed to be quantum-resistant, often require a polynomial number of communication rounds, which is impractical for many applications. Furthermore, classical MPC techniques that rely on "rewinding" simulators to extract information from adversaries are problematic in the quantum setting due to the no-cloning theorem. This paper tackles the challenge of building constant-round MPC protocols that are secure against malicious quantum adversaries in this demanding plain model.

Methods

The core of this work lies in developing new cryptographic primitives and simulation techniques:

  • Constant-Round Post-Quantum MPC: The main result is a constant-round MPC protocol for classical functionalities, secure against malicious quantum adversaries. This is achieved by combining several newly developed primitives.
  • Quantum AFS-Spooky Encryption: The authors construct a novel "spooky encryption" scheme that supports homomorphic operations on relations computable by quantum circuits. This is a significant step towards quantum multi-key fully-homomorphic encryption (FHE) with classical keys.
  • Constant-Round Quantum Zero-Knowledge against Parallel Verifiers: A key technical contribution is a new straight-line non-black-box simulation technique that overcomes the no-cloning theorem. This technique allows for simulating multiple parallel quantum verifiers without cloning the adversary's state, which is crucial for constant-round protocols.
  • Constant-Round Post-Quantum Non-Malleable Commitments: The paper also introduces constant-round non-malleable commitment schemes that are secure against quantum adversaries. This is achieved by building upon existing techniques and adapting them to the quantum setting, relying on the hardness of LWE.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Overcoming the No-Cloning Theorem for Simulation: The most significant insight is the development of a "parallel no-cloning non-black-box simulation technique." This technique is crucial for achieving constant-round security in the quantum setting, as it bypasses the limitations imposed by the no-cloning theorem on traditional rewinding-based simulation.
  • Quantum Multi-Key FHE as a Building Block: The construction of quantum AFS-spooky encryption, which enables quantum multi-key FHE, is a vital primitive. This allows for computations over encrypted data that is encrypted under multiple keys, a necessary component for MPC.
  • Constant Rounds in the Plain Model: Achieving constant-round MPC in the plain model is a major feat. It implies that parties can securely compute functions with minimal communication overhead, even in the presence of powerful quantum adversaries.
  • New Primitives for Quantum Security: The paper introduces and constructs several new cryptographic primitives (spooky encryption, parallel zero-knowledge, non-malleable commitments) that are secure against quantum adversaries and may have independent interest in the field.

Key Results

  • Construction of the first constant-round post-quantum MPC protocol in the plain model, secure against malicious quantum adversaries.
  • Construction of the first quantum multi-key fully-homomorphic encryption scheme with classical keys, based on LWE.
  • Construction of constant-round zero-knowledge arguments secure against multiple parallel quantum verifiers.
  • Construction of constant-round post-quantum non-malleable commitment schemes.
  • The security of these constructions relies on mildly super-polynomial quantum hardness of LWE and an LWE-based circular security assumption.

Limitations and Future Work

  • Composition under Unbounded Parallel Repetition: The paper notes that their developed techniques do not achieve protocols that compose under unbounded parallel repetition. Instead, they build a bounded variant that suffices for their constant-round MPC application. This suggests future work could explore achieving unbounded parallel repetition.
  • Classical vs. Quantum Circuits: While the paper focuses on MPC for classical functionalities, the developed primitives like spooky encryption are for relations computable by quantum circuits. Extending the MPC protocols themselves to handle quantum functionalities would be a natural next step.
  • Efficiency: While constant-round is achieved, the efficiency (in terms of communication and computation complexity) of the constructed protocols is not the primary focus and could be a subject for future optimization.

Summary updated

Abstract

We initiate the study of multi-party computation for classical functionalities (in the plain model) with security against malicious polynomial-time quantum adversaries. We observe that existing techniques readily give a polynomial-round protocol, but our main result is a construction of *constant-round* post-quantum multi-party computation. We assume mildly super-polynomial quantum hardness of learning with errors (LWE), and polynomial quantum hardness of an LWE-based circular security assumption. Along the way, we develop the following cryptographic primitives that may be of independent interest: 1. A spooky encryption scheme for relations computable by quantum circuits, from the quantum hardness of an LWE-based circular security assumption. This yields the first quantum multi-key fully-homomorphic encryption scheme with classical keys. 2. Constant-round zero-knowledge secure against multiple parallel quantum verifiers from spooky encryption for relations computable by quantum circuits. To enable this, we develop a new straight-line non-black-box simulation technique against *parallel* verifiers that does not clone the adversary's state. This forms the heart of our technical contribution and may also be relevant to the classical setting. 3. A constant-round post-quantum non-malleable commitment scheme, from the mildly super-polynomial quantum hardness of LWE.
BibTeX
@misc{agarwal2020post,
  author = {Amit Agarwal and James Bartusek and Vipul Goyal and Dakshita Khurana and Giulio Malavolta},
  title = {{Post-Quantum Multi-Party Computation in Constant Rounds}},
  year = {2020},
  eprint = {2005.12904},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2005.12904},
}
Figure