Best-of-Both-Worlds Multiparty Quantum Computation with Publicly Verifiable Identifiable Abort

Kai-Min Chung, Mi-Ying (Miryam) Huang, Er-Cheng Tang, Jiapeng ZhangEUROCRYPT 2024 · DOI

TL;DR

This paper introduces the first multiparty quantum computation (MPQC) protocol that allows anyone to verify if a party cheated, even if they only have classical computing power. This "publicly verifiable identifiable abort" (PVIA) is crucial for real-world disputes and is achieved using a novel primitive called Auditable Quantum Authentication (AQA). The protocol also offers "best-of-both-worlds" security, meaning it's fully secure with an honest majority and secure with abort under a dishonest majority.

What Problem Does This Paper Address?

Secure multiparty computation (MPC) allows multiple parties to compute a function on their private inputs without revealing those inputs. In the quantum realm, this is called multiparty quantum computation (MPQC). While classical MPC has notions like "security with abort" (parties can stop if something goes wrong) and "identifiable abort" (parties can identify who cheated), these have limitations in the quantum setting.

The main challenge is public verifiability. Current MPQC protocols with identifiable abort only allow participants to know who cheated. Imagine a dispute where a client accuses a service provider of not delivering a quantum service. The client and provider might disagree, but an external observer (like a judge) needs a way to verify who is being dishonest. This is especially critical in quantum computing because quantum states are fragile and often exist in only one copy – once ruined, they're gone forever.

The paper addresses this by proposing MPQC with Publicly Verifiable Identifiable Abort (PVIA). This means that even an observer with only classical computational power can definitively identify a malicious party if the protocol aborts. Furthermore, they tackle the problem of achieving Best-of-Both-Worlds (BoBW) security in MPQC, which combines the benefits of honest-majority security (full output delivery) and dishonest-majority security (security with abort).

Methods

The core innovation is the Auditable Quantum Authentication (AQA) primitive. Traditional quantum authentication schemes rely on the receiver to verify a message, which doesn't work for public verifiability because the observer would have to trust the receiver. AQA flips this: it makes the sender accountable through a classical auditor.

Here's how AQA works conceptually:

  1. Setup: Parties prepare quantum states.
  2. Encoding: The sender "authenticates" a quantum message.
  3. Send: The sender generates a classical proof of their action.
  4. Audit: A classical auditor (which can be a classical MPC) verifies the proof. If the proof is valid, the auditor outputs a decoding key.
  5. Receive: The receiver uses the decoding key to get the message.

This separation of the authenticity check from the message decoding allows a classical auditor to verify the sender's actions without needing to interact with the quantum states directly.

The paper then builds MPQC-PVIA protocols using AQA. They leverage a preprocessing model, which involves an initial offline phase to prepare quantum states. This allows for the exchange of classical proofs and facilitates PVIA. They also incorporate quantum error correction codes (QECC) to handle errors and enable distributed computation.

For BoBW security, they combine their MPQC-PVIA protocol with QECC and a specific offline setup that allows for information extraction even under a dishonest majority. This setup ensures that honest parties can still get their outputs if there's an honest majority, but the protocol remains secure with abort if the majority is dishonest.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Sender Accountability is Key: The traditional sender-receiver model for quantum authentication is insufficient for public verifiability. AQA's innovation is making the sender directly accountable through a verifiable proof.
  • Classical Auditors for Quantum Security: The paper demonstrates that classical computation (specifically, a classical MPC acting as an auditor) can play a crucial role in verifying quantum protocols, bridging the gap between quantum computation and classical verification.
  • Bridging Honest and Dishonest Majority Worlds: The BoBW security concept is powerful because it offers the best of both worlds. The paper shows how to achieve this in MPQC by carefully designing the offline setup and leveraging QECC.
  • No-Cloning Theorem is Not a Showstopper for PVIA: While the no-cloning theorem makes direct classical verification of quantum states difficult, AQA and the preprocessing model offer ways to achieve public verifiability indirectly.

Key Results

  • First MPQC-PVIA Protocol: The paper presents the first MPQC protocol that achieves publicly verifiable identifiable abort, even with a trusted setup.
  • First BoBW-MPQC-PVIA Protocol: They then construct a BoBW-MPQC-PVIA protocol, offering both full security under an honest majority and security with abort under a dishonest majority, also with a trusted setup.
  • Instantiable Protocols: Crucially, they show how to instantiate these protocols without a trusted setup, by leveraging existing MPQC-SWIA protocols.
  • Novel Primitive: Auditable Quantum Authentication (AQA): This primitive is central to achieving PVIA and has potential applications beyond MPQC.

Limitations and Future Work

  • Trusted Setup: While they show how to instantiate protocols without a trusted setup, the initial constructions rely on one. Removing the trusted setup for MPQC-PVIA and BoBW-MPQC-PVIA is a significant direction.
  • Constant-Round MPQC-PVIA: The paper suggests that achieving constant-round MPQC-PVIA is possible by combining their techniques with existing garbled circuit methods, but this would likely still require a trusted setup. Finding a constant-round solution without a trusted setup is an open problem.
  • Alternative AQA Forms: Exploring other forms of AQA beyond the Clifford-based one could lead to new constructions or improved efficiency.
  • Public-Key AQA: The current AQA requires a shared secret key. Developing a public-key version could simplify its application in scenarios where parties don't have pre-shared keys.

Summary updated

BibTeX
@inproceedings{chung2024best,
  author = {Kai-Min Chung and Mi-Ying (Miryam) Huang and Er-Cheng Tang and Jiapeng Zhang},
  title = {{Best-of-Both-Worlds Multiparty Quantum Computation with Publicly Verifiable Identifiable Abort}},
  booktitle = {EUROCRYPT},
  year = {2024},
  doi = {10.1007/978-3-031-58751-1\_5},
}

Loading related content...

Figure