⚛️ quantum physics

Verifiable and Collusion-Resistant Multi-Party Quantum Private Set Operations

This paper proposes a verifiable and collusion-resistant multi-party quantum private set intersection protocol that enables explicit cardinality testing without a trusted third party interpreting results, utilizing a rotation-based quantum construction combined with oblivious linear evaluation and garbled circuits to reveal only whether the intersection meets a threshold.

Original authors: Zixian Gong, Kun Tian, Yi Zhang, Fengxia Liu

Published 2026-06-29

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Zixian Gong, Kun Tian, Yi Zhang, Fengxia Liu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends, each holding a secret list of their favorite movies. They want to find out which movies they all like without anyone revealing their full list to the others. In the digital world, this is called Private Set Intersection (PSI).

Now, imagine this group is huge, and they are using a super-smart, powerful computer (let's call it the "Server") to do the math for them. The problem? What if the Server is a bit sneaky? What if the Server tries to peek at the lists, or what if the Server teams up with one of the friends to cheat?

This paper presents a new, high-tech solution called MP-QPSI (Multi-Party Quantum Private Set Intersection). It uses the strange laws of quantum physics to solve these problems. Here is how it works, explained simply:

The Cast of Characters

The Friends (Participants): They have the secret lists. They are "lightweight," meaning they don't have powerful computers; they just need to do a little bit of quantum magic to lock their data.
The Server (Third Party/TP): A powerful quantum computer that does all the heavy lifting. It's trusted to do the math, but the protocol assumes it might try to cheat or peek.
The Referee (Trusted Authority/TA): A neutral party who sets up the game, hands out keys, and checks the final results to make sure no one cheated.

The Core Problem: The "Sneaky Server"

In older versions of this technology, the rules assumed the Server would be honest, or at least wouldn't team up with the friends. If the Server and a friend colluded, they could steal everyone's secrets. This paper fixes that by making it impossible for the Server and a few friends to break the code together.

How It Works: The "Quantum Envelope" and the "Trap"

Think of the process as sending a package through a secure tunnel:

1. Locking the Data (Encryption)
Each friend puts their movie list into a special Quantum Envelope.

The Magic Lock: They use a "Quantum One-Time Pad." Imagine a lock that changes its shape randomly every time you look at it. To the Server, the envelope looks like pure static noise (random fuzz). It's impossible to tell what's inside without the specific key.
The Traps: Inside the envelope, the friends hide "traps"—like little alarm bells. If the Server tries to open the envelope or tamper with it, the alarm goes off.
The Secret Split: The keys to unlock these envelopes aren't held by one person. Instead, the Referee cuts the master key into pieces and gives a piece to each friend. You need a certain number of friends (a "threshold") to put the pieces together and open the final result. This prevents a single friend from teaming up with the Server to steal the keys.

2. Doing the Math (Homomorphic Evaluation)
The Server receives all these locked, fuzzy envelopes.

The Magic Trick: Even though the envelopes are locked, the Server can perform the "AND" operation (finding the common movies) without ever opening them. It's like a chef who can mix ingredients in a sealed, opaque bag and tell you the result without ever seeing the ingredients.
The Log: As the Server does the math, it keeps a detailed "receipt" (a log) of every step it took.

3. Checking the Work (Verification)
Once the Server finishes, it sends the result and the receipt back.

The Friends Check the Receipt: The friends look at the receipt to make sure the Server followed the rules and didn't swap out the math for something else.
The Referee Checks the Traps: The Referee opens the final envelope. First, they check the "alarm bells" (traps). If the Server tried to peek or cheat, the traps would have been triggered, and the Referee would know immediately.
The Final Unlock: If everything checks out, the friends combine their key pieces to unlock the final answer: the list of movies they all share.

Why Is This Special?

No Sneaky Team-Ups: Even if the Server tries to team up with a few friends, they can't steal the secrets because the key is split up. They need too many friends to unlock it.
Catch the Cheater: If the Server tries to do the wrong math or peek at the data, the "trap" system and the receipt check will catch them. The friends will know the result is fake and reject it.
Flexible: The paper shows this system isn't just for finding common movies. By changing a few switches in the "circuit," it can also find the union (all unique movies combined) or just count how many movies they have in common.

The Bottom Line

This paper proposes a way for many people to do private calculations together using a powerful, potentially untrusted computer. It uses quantum locks to hide the data, split keys to prevent collusion, and quantum traps to catch cheaters. It's like a high-stakes game of poker where the dealer (Server) can shuffle the cards but can never see them, and if they try to cheat, the players have a foolproof way to prove it.

Technical Summary: Verifiable and Collusion-Resistant Multi-Party Quantum Private Set Operations

1. Problem Statement

Private Set Operations (PSO), including Private Set Intersection (PSI) and Union (PSU), are fundamental to Secure Multiparty Computation (SMC). While classical cryptographic solutions exist, the advent of quantum algorithms (e.g., Shor's algorithm) threatens current number-theoretic schemes. Consequently, research has shifted toward Quantum PSI (QPSI).

However, existing Quantum PSO (QPSO) protocols face significant limitations:

Threat Models: Most existing QPSI schemes assume a semi-honest Trusted Third Party (TP) or rely on assumptions that the TP cannot collude with any participant.
Collusion Resistance: Prior multi-party QPSI (MP-QPSI) protocols often fail to resist collusion between the TP and a subset of participants, or they only tolerate the corruption of a single participant.
Verifiability: Many schemes lack mechanisms to verify that the TP correctly executed the prescribed quantum circuit, leaving the system vulnerable to malicious deviations.

2. Methodology

The authors propose a Multi-Party Quantum Private Set Intersection (MP-QPSI) protocol that integrates Verifiable Quantum Fully Homomorphic Encryption (vQFHE) with Threshold Fully Homomorphic Encryption (TFHE). The protocol operates in a model involving $n$ data-holding participants, a powerful quantum TP, and a Trusted Authority (TA).

Core Components

Threshold Key Management (TFHE):
- The secret key for decryption is shared among $n$ participants using a $(t, n)$ -threshold secret sharing scheme.
- Decryption requires at least $t$ participants to collaborate. This ensures that neither a subset of corrupted participants nor a collusion between the TP and fewer than $t$ participants can recover the secret key or learn private inputs.
Verifiable Quantum Evaluation (vQFHE):
- The protocol utilizes the TrapTP construction (from [ADS+17]) as the vQFHE layer.
- Encryption: Participants encode their private sets into quantum states using CSS codes, append trap qubits ( $|0\rangle$ and $|+\rangle$ ), apply a random permutation, and mask the result with a Quantum One-Time Pad (QOTP). The QOTP keys are encrypted under TFHE and authenticated with Message Authentication Codes (MAC).
- Evaluation: The TP performs homomorphic evaluation of a multi-party AND circuit ( $C_{\text{AND}}$ ) on the encrypted quantum states. The TP updates the encrypted QOTP keys homomorphically and consumes "gadgets" (magic states) to handle non-Clifford (T) gates, following the garden-hose model.
- Verification: The TP generates a classical transcript (log) of the evaluation. Participants and the TA verify this log against the MACs, the gate array, and the trap code measurements to ensure the TP did not deviate from the target circuit.
Protocol Flow:
- Phase 1 (Preparation): TA generates keys, samples permutations, prepares T-gate gadgets, and distributes secret shares.
- Phase 2 (Encryption): Participants encode their sets into quantum states, apply traps and QOTP, and send encrypted states and keys to the TP.
- Phase 3 (Evaluation): TP executes the $C_{\text{AND}}$ circuit homomorphically, updating keys and recording a transcript.
- Phase 4 (Verification & Decryption): Participants perform classical verification (MAC, gate, and transcript checks) and threshold decryption to recover QOTP keys. The TA performs quantum verification (trap checks) and decrypts the final state to broadcast the intersection result.

3. Key Contributions

Multi-Party Extension: The authors extend vQFHE to a multi-party setting by combining it with TFHE, enabling $n$ parties to compute set intersections without revealing private data.
Collusion Resistance: Unlike prior QPSI schemes, this protocol resists collusion between the TP and up to $t-1$ participants. The threshold mechanism ensures that as long as fewer than $t$ parties are corrupted, the secret key and private inputs remain secure.
Verifiability against Malicious TP: The protocol provides semantic security and verifiability. It can detect if a malicious TP deviates from the prescribed circuit (e.g., by altering the gate array or output) through a combination of classical transcript verification and quantum trap code checks.
Modular Framework: The construction is presented as a modular framework. The authors demonstrate how to:
- Reduce circuit complexity (e.g., using CCCZ gates instead of $C_nX$ to lower T-gate counts).
- Extend functionality to Quantum Private Set Union (QPSU) by replacing the AND circuit with an OR circuit via open-controlled operations.
- Swap underlying vQFHE instantiations for different efficiency/security trade-offs.

4. Results and Analysis

Correctness: The authors validated the logical multi-party AND gate using the IBM Quantum Platform and Qiskit. Simulations confirmed that the output distribution matches the ideal truth table for the logical AND operation.
Security Proofs:
- Privacy: The protocol is proven to be information-theoretically secure against the TP regarding the quantum states (due to QOTP and maximally mixed states) and computationally secure regarding classical data (due to TFHE and MAC).
- Collusion: Theorem 3 proves that any coalition of corrupted participants (size $<t$ ) colluding with the TP gains no information beyond the intersection result.
- Verifiability: Under the semantic security model ( $\kappa$ -SEM-VER), the protocol is shown to be verifiable. A hybrid argument demonstrates that any deviation by the TP is detected with overwhelming probability.
Performance:
- Communication Complexity: The quantum communication cost is $O(n\kappa L)$ , where $n$ is the number of parties, $\kappa$ is the security parameter, and $L$ is the set size.
- Comparison: Compared to existing schemes (e.g., [SMZ+15], [ZLS+20], [HZZ24]), the proposed protocol is the only one supporting multi-party scenarios with both PSI and PSU capabilities while offering resistance to TP-participant collusion and malicious TP behavior.

5. Significance and Claims

The paper claims to offer a significant advancement in the field of quantum secure computation by addressing the "TP-participant collusion" gap that plagues existing QPSI solutions.

Robustness: By integrating TFHE, the protocol achieves a level of collusion resistance previously absent in quantum PSI, ensuring security even if the TP and a subset of participants conspire.
Trust Minimization: The verifiability layer allows the system to function securely even if the TP is malicious, removing the need to trust the TP's honesty, only its computational capability.
Flexibility: The modular design allows the framework to be adapted for different set operations (Union, Cardinality) and optimized for different hardware constraints (e.g., reducing T-gate complexity).

The authors acknowledge that while the protocol offers strong security, it inherits the classical overhead associated with TrapTP-based vQFHE. Future work is suggested to explore gadget-free T-handling and further optimizations to reduce classical communication costs.