⚛️ quantum physics

Quantum Multi-Party Threshold Private Set Intersection with Explicit Cardinality Testing

This paper proposes a quantum multi-party threshold private set intersection protocol featuring explicit cardinality testing, which utilizes a rotation-based single-photon construction and cryptographic primitives to enable a third party to perform measurements without interpreting results while securely revealing only whether the intersection size meets a threshold.

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

Published 2026-06-29

📖 6 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 who each have a secret list of favorite movies. They want to know: "Do we all agree on at least three movies?"

If the answer is yes, they want to see the list of those three movies.
If the answer is no, they want to know nothing—not even how many movies they actually had in common.

This is the problem of Threshold Private Set Intersection (TPSI). The paper proposes a new way to solve this using Quantum Mechanics (specifically, single photons of light) and clever math, ensuring that even the person running the experiment cannot cheat or peek at the secrets.

Here is how the paper's solution works, broken down into simple concepts:

1. The Problem with Old Methods

In previous quantum attempts, the group relied on a "Referee" (called a Third Party or TP) to count the matches.

The Flaw: The Referee would count the matches, compare that number to the threshold (e.g., "Is 3?"), and then decide what to tell the group.
The Risk: This meant the Referee saw the exact number of matches. If the group only had 2 matches, the Referee knew that. But the group only wanted to know if they had enough (3 or more), not the exact count. It's like asking a judge, "Is the defendant guilty?" but the judge first has to write a full biography of the crime before answering.

2. The New Solution: The "Blindfolded Referee"

The authors created a protocol where the Referee performs the measurements but is blindfolded regarding the meaning of the results.

The Setup: The Secret Code

Before the experiment starts, the friends (participants) agree on a secret code among themselves. They also mix their real movie lists with some "decoy" fake lists (anchors) that the Referee doesn't know about.

The Hiding Key: They shuffle the positions of their movies using a secret key. To the Referee, the lists look like random noise.
The Flip: They agree on a secret "flip" (like a secret handshake) that changes the meaning of the results. If a light turns "On," it might actually mean "Off" depending on this secret flip.

The Quantum Dance (The Rotation)

The experiment uses photons (particles of light) as messengers.

The Referee prepares a line of photons and sends them to the first friend.
Friend 1 looks at their secret list. If they have a specific movie at a certain spot, they give the photon a tiny "spin" (a rotation). If they don't have it, they leave it alone. They also add a secret "mask" rotation that only they and the Referee know.
The Chain: The photons travel to Friend 2, then Friend 3, and so on. Each friend adds their own spin based on their secret list.
The Return: The photons return to the Referee.

The Magic of "Hidden Labels"

When the photons return, the Referee removes their own masks and measures the light.

The Result: The Referee sees a pattern of "Same" or "Opposite" light.
The Catch: Because of the secret "flip" agreed upon by the friends, the Referee cannot understand what the pattern means. A "Same" result might mean "Match" or "No Match" depending on a secret bit that only the friends know. The Referee has the data, but it looks like gibberish to them.

3. The Final Check: The "Blind Vote"

Now the friends and the Referee need to decide: "Did we reach the threshold?" without the Referee learning the exact count.

The Math Trick (OLE): They use a cryptographic tool called Oblivious Linear Evaluation. Think of this as a secure calculator where the Referee puts in their "gibberish" numbers, and the friends put in their "secret keys."
The Garbled Circuit: They run a tiny, locked computer program (a garbled circuit). This program adds up the numbers internally.
The Output: The program outputs only one bit: 1 (Yes, we have enough matches) or 0 (No, we don't).
- If the answer is 1, the friends reveal the secret key to decode the Referee's "gibberish" pattern, and they see the matching movies.
- If the answer is 0, they throw everything away. The Referee never learns the exact number of matches, only that it wasn't high enough.

4. Why This is Safe (Security)

The paper proves three main safety points:

No Eavesdroppers: If a spy tries to intercept the photons, the "decoy" lights (which the spy doesn't know about) will change, alerting everyone that the line has been tapped.
The Referee is Honest but Curious: Even if the Referee tries to cheat or use fancy quantum tricks to guess the secrets, the math ensures they can't distinguish the real matches from the noise. They are truly blind to the meaning of the data.
Friends Can't Cheat Each Other: Even if two friends team up to spy on the third, they can't figure out the third friend's list because of the secret masks and the way the photons are rotated.

5. The "Toy Model" Proof

To show this actually works, the authors built a small simulation using IBM's quantum computer simulator (Qiskit).

They simulated 3 friends with small lists.
They added "noise" (simulating real-world imperfections).
The Result: The system correctly identified that the friends had 2 movies in common (which was below their threshold of 3). The system said "No," and the friends learned nothing.
They then showed that if they had 3 matches, the system would correctly say "Yes" and reveal the list.

Summary

This paper introduces a Quantum Multi-Party Threshold PSI protocol.

Goal: Reveal a shared secret only if the group is large enough.
Innovation: It separates the act of measuring (done by a Referee) from the act of interpreting (done by the group).
Mechanism: It uses rotating photons and secret "flips" to create "hidden labels" that the Referee cannot read, ensuring the exact count of matches remains private.
Outcome: The group learns only a simple "Yes/No" about the threshold, and only if "Yes" do they see the actual shared items.

Technical Summary: Quantum Multi-Party Threshold Private Set Intersection with Explicit Cardinality Testing

Problem Statement
Private Set Intersection (PSI) allows parties to compute the intersection of their private sets without revealing non-intersecting elements. Threshold PSI (TPSI) extends this by revealing the intersection only if its cardinality meets or exceeds a public threshold $\tau$ . While classical TPSI protocols exist, existing quantum TPSI protocols (e.g., [MSD+24, LZY+26, WLS+26]) typically rely on a Third Party (TP) to perform final measurements and interpret the results. In these schemes, the TP recovers the exact intersection cardinality and then compares it to $\tau$ . This approach deviates from the ideal TPSI paradigm, as it exposes the exact cardinality statistic to the TP rather than revealing only the one-bit predicate $\mathbb{1}[|\bigcap X_i| \ge \tau]$ . This creates a functionality mismatch and a concentration of authority where the TP acts as both a quantum resource provider and a semantic interpreter of the private data.

Methodology
The authors propose a Multi-Party Quantum TPSI (MP-QTPSI) protocol that decouples the measurement role from the semantic interpretation role. The protocol involves $n$ participants ( $P_1, \dots, P_n$ ) and a semi-honest TP.

Quantum Phase (Hidden-Label Construction):
- Setup: Participants establish a master key via a TP-free Quantum Conference Key Agreement (QCKA) to derive a position-hiding key $k$ , a hidden label-flip vector $\mathbf{b}$ , and rotation shares $\Delta_i$ . TP and each participant establish pairwise keys for rotation masks $T_i$ .
- Encoding: Participants augment their sets with positive anchor sets and apply a position-hiding map $x \mapsto kx \mod M$ . They encode their sets into indicator vectors $Y_i$ .
- Interaction: TP prepares single-photon sequences and applies an initial blinding rotation. The sequences traverse the participants sequentially. Each participant $P_i$ applies a rotation based on their data ($0$ or $\pi/n$ ), their pairwise mask $T_i$ , and their rotation share $\Delta_i$ .
- Measurement: TP removes its known masks and measures the sequences. Due to the correlated aggregate rotations, the measurement outcomes are deterministic only for positions where all participants hold the element (intersection) or none hold it (non-intersection), but the semantic meaning of these outcomes (which label corresponds to "intersection") is blinded by the hidden flip vector $\mathbf{b}$ . TP obtains hidden-label indicator vectors $z_S$ (same) and $z_O$ (opposite) but cannot interpret them without participant-side information.
Classical Phase (Cardinality Testing):
- Masked Consistency Test: The protocol converts the hidden measurements into a masked label-consistency test. Participants hold reference labels $\rho$ and selector masks for real and anchor domains.
- Oblivious Linear Evaluation (OLE): TP and participants use OLE-based Oblivious Inner Product (OIP) to compute additive shares of the consistency counts (inconsistencies $d_{\mathcal{R}}$ and $d_{\mathcal{A}}$ ) without revealing the vectors to each other.
- Threshold Decision: A lightweight garbled circuit evaluates the predicate $\text{flag} = 1 \iff (d_{\mathcal{A}} = 0) \land (d_{\mathcal{R}} \le |\mathcal{R}| - \tau)$ . This outputs only the boolean result, ensuring the exact cardinality is never revealed to the TP.
- Reconstruction: If $\text{flag}=1$ , TP broadcasts the hidden vectors, and participants use their reference labels and inverse key $k^{-1}$ to reconstruct the intersection.

Key Contributions

Explicit Cardinality Testing: The protocol is the first quantum TPSI to strictly adhere to the cardinality-testing paradigm, outputting only the threshold predicate $\mathbb{1}[|\bigcap X_i| \ge \tau]$ without revealing the exact cardinality to the TP.
Hidden-Label Quantum Design: By utilizing participant-side correlated aggregate rotations and a hidden flip vector, the protocol ensures that TP's measurement outcomes are semantically blinded. TP acts solely as a measurement party, unable to map outcomes to specific set elements or cardinality.
Security Against Collusion and TP: The protocol proves security against outside eavesdroppers (via decoy photons), the semi-honest TP (who learns neither sets nor cardinality), and colluding participants (who cannot infer others' sets due to pairwise masks and unknown blinding rotations).
Tamper Detection: The inclusion of hidden anchor sets allows for a consistency check ( $d_{\mathcal{A}}=0$ ) that can detect if the TP modifies the reported measurement vectors.

Results

Correctness: Theoretical proofs demonstrate that the protocol correctly encodes the intersection pattern and that the classical subprotocol correctly evaluates the threshold condition.
Simulation: The authors implemented the quantum phase on the IBM Qiskit platform using a toy model ( $n=3$ , domain size 8). The simulation included depolarizing, phase-damping, and readout errors. The noisy simulation results (Table 3) closely matched theoretical probabilities, successfully passing the anchor check and threshold test to reconstruct the correct intersection $\{1, 3\}$ .
Complexity: The quantum communication cost is $\mathcal{O}(n(\ell M + \delta))$ , and computation cost is similar, where $M$ is the augmented domain size, $\ell$ is the repetition number, and $\delta$ is the number of decoys.

Significance and Claims
The paper claims that its primary significance lies in resolving the "functionality gap" in existing quantum TPSI protocols. By separating the quantum measurement role from the semantic interpretation role, the proposed protocol aligns with the ideal classical TPSI definition where the threshold decision is a direct predicate rather than a post-processing step on revealed statistics. The authors emphasize that their construction relies only on single-photon rotations and a lightweight classical post-processing step (OLE and garbled circuits), avoiding the complexity of Quantum Homomorphic Encryption (QHE) used in other recent works. They assert that this design offers a more privacy-preserving approach for multi-party settings where the TP should not learn the size of the intersection. The paper concludes by noting that the framework is flexible and could potentially be extended to weighted or ratio-based thresholds, though it currently operates under a semi-honest TP model.