Quantum Multi-Party Threshold Private Set Intersection with Explicit Cardinality Testing Zixian Gonga,∗ , Kun Tiana , Yi Zhanga and Fengxia Liub a School of Mathematics, Renmin University of China, Beijing, 100872, P. R. China
arXiv:2606.27996v1 [quant-ph] 26 Jun 2026
b Great Bay University, DongGuan, 523808, P. R. China
ARTICLE INFO
ABSTRACT
Keywords: Quantum Private Set Intersection Cardinality Testing Threshold Private Set Intersection Oblivious Linear Evaluation
Threshold private set intersection (TPSI) allows parties to reveal their intersection only when its cardinality reaches a prescribed threshold. Existing quantum TPSI protocols typically rely on a third party (TP) to interpret the final results, which deviates from the cardinality-testing paradigm of TPSI. In this paper, we propose a quantum multiparty TPSI protocol with explicit cardinality testing. Our protocol develops a rotation-based quantum construction in which single-photon sequences are sequentially processed through participant-side data rotations, TP–participant masking rotations, and correlated aggregate rotations. This design produces hidden-label measurement vectors: TP can complete the final measurement, but cannot interpret the semantic meaning of the outcomes. Based on these hidden measurements, we further realize the threshold decision through an oblivious linear evaluation (OLE)-based inner product procedure and a lightweight garbled circuit, revealing only ⋂ 𝟏[| 𝑖 𝑋𝑖 | ≥ 𝜏] before conditional intersection reconstruction. We prove the correctness and security of the proposed protocol, and further validate its feasibility through quantum-circuit simulations implemented on the IBM Qiskit platform.
1. Introduction Private set intersection (PSI) is a fundamental primitive in secure multiparty computation (SMC). It enables a set of parties, each holding a private set 𝑋𝑖 , to compute their com⋂ mon intersection 𝑖 𝑋𝑖 without revealing any information about elements outside the intersection [Mea86, FNP04]. Owing to this privacy-preserving matching capability, PSI has become a key building block for a wide range of applications including contact tracing [ABC+ 20], genomic data analysis [SCW+ 18], and ad conversion tracking [IKN+ 17]. Driven by the diversity of PSI applications, a variety of functional extensions have been developed to satisfy different privacy and utility requirements. Representative examples include PSI cardinality protocols, which reveal only the size of the intersection [DD15]; circuit PSI, which delivers the intersection in secret-shared form for subsequent secure computation [HEK12]; and fuzzy PSI, which supports similarity-based matching [UCK+ 21]. Among these variants, TPSI introduces⋂ a threshold-gated ⋂ disclosure mechanism, namely, reveal 𝑖 𝑋𝑖 only if || 𝑖 𝑋𝑖 || ≥ 𝜏. This functionality is useful in practical applications such as privacypreserving ridesharing [HOS17, MSD+ 24] and matchmaking [ZC18]. Beyond such application-driven formulations, TPSI has also been studied as a distinct cryptographic primitive with dedicated communication-efficiency and multiparty constructions [GS19, BMR+ 21]. The emergence of Shor’s algorithm [Sho97] has shown that many cryptographic schemes relying on number-theoretic hardness assumptions are vulnerable in the presence of quantum computers. While some ongoing researches focuse on post-quantum cryptography (PQC) as an interim measure, ∗ Corresponding author
[email protected] (F. Liu)
ORCID (s): 0009-0005-7059-5040 (Z. Gong)
Zixian Gong et al.: Preprint submitted to Elsevier
Shi et al. [SMZ+ 16] proposed the first two-party quantum PSI protocol. [ZLS+ 20] considered a three-party setting with a third party (TP) and realized quantum PSI-CA and PSU-CA based on GHZ states. [MD23] further extended quantum PSI to multi-party setting (MP-QPSI) using single photons and unitary operations. [HZZ24] achieved MPQPSI via rotation operations. More recently, the threshold functionality has also been introduced into the quantum setting, leading to quantum TPSI based on rotation operations [MSD+ 24, LZY+ 26] and quantum homomorphic encryption (QHE) [WLS+ 26]. Although several quantum TPSI protocols have been proposed [MSD+ 24, LZY+ 26, WLS+ 26], their threshold mechanisms do not entirely fully align with the ideal classical cardinality testing paradigm. In these constructions, a TP is typically introduced to assist the quantum procedure, perform the final measurement or result processing, recover the intersection cardinality, and then compare it with the public threshold 𝜏. Consequently, TP simultaneously acts as a quantum-resource provider, a protocol participant, and an interpreter of the final threshold-related outcome. This creates both a concentration ⋂ of authority and a functionality mismatch: recovering || 𝑛𝑖=1 𝑋𝑖 || and then comparing it with 𝜏 is strictly[more ⋂ revealing]than directly realizing the testing predicate 𝟏 || 𝑛𝑖=1 𝑋𝑖 || ≥ 𝜏 . This gap motivates us to design a quantum TPSI protocol that decouples the measurement or result-processing role from the semantic interpretation role: • Functionality gap and rotation-based hidden-label quantum design. We identify that existing quantum TPSI schemes rely on TP-side cardinality recovery followed by threshold comparison. To restore an explicit cardinality-testing paradigm, we develop a rotation-based quantum construction over single-photon sequences, combining participant-side data rotations, TP–participant Page 1 of 11
QTPSI
masking rotations, and correlated aggregate rotations to produce hidden-label measurement outcomes that TP cannot directly interpret. • Cardinality testing for hidden quantum measurements. We convert the hidden measurement outputs into a masked label-consistency test and realize the threshold decision through oblivious linear evaluation-based innerproduct sharing and a lightweight garbled circuit. The ⋂ protocol outputs only 𝟏[| 𝑖 𝑋𝑖 | ≥ 𝜏] before conditional reconstruction, without revealing the exact cardinality. • Security, simulation, and comparison. We prove correctness and security against outside eavesdroppers, TP, and colluding participants, and discuss anchor-based tamper detection. We also validate the quantum phase via Qiskit simulation and compare our protocol with representative TPSI schemes. Outline. The remainder of this paper is organized as follows. Section 2 discusses the cardinality testing in quantum TPSI. Section 3 presents the realization of cardinality testing for hidden-label measurements. The proposed MP-QTPSI protocol is described in Section 4 along with correctness and security analysis in Section 5. Simulation and comparisons are given in Section 6. Finally, Section 7 concludes the paper.
2. Cardinality Testing for Quantum TPSI Cardinality testing in TPSI. TPSI is intended to realize a conditional disclosure rule: the intersection is revealed only when its cardinality reaches a public threshold. Formally, the protocol should first determine ] [ 𝑛 |⋂ | | | 𝖿 𝗅𝖺𝗀 = 𝟏 | 𝑋𝑖 | ≥ 𝜏 , | | | 𝑖=1 | ⋂ and release 𝑛𝑖=1 𝑋𝑖 only if 𝖿 𝗅𝖺𝗀 = 1 [GS19, BMR+ 21, GS23]. Thus, cardinality testing is a distinct functionality from cardinality disclosure and then comparison: [ 𝑛 ] 𝑛 |⋂ | | 𝐹 𝑢𝑛𝑐𝑡𝑖𝑜𝑛𝑎𝑙𝑖𝑡𝑦 |⋂ | | | | 𝟏 | 𝑋𝑖 | ≥ 𝜏 ≠ | 𝑋𝑖 | ≥ 𝜏. | | | | | 𝑖=1 | | 𝑖=1 | the former reveals only a one-bit threshold predicate, whereas the latter exposes an additional statistic of the private sets. Limitation of TP-centered quantum TPSI. In existing quantum TPSI protocols [MSD+ 24, LZY+ 26, WLS+ 26], TP is typically responsible for quantum-state preparation or result processing, final measurement, and threshold-related interpretation. In particular, TP first derives the intersection cardinality, compares it with 𝜏, and then decides whether to release the intersection related result. Hence, TP’s measurement role and semantic interpretation role are coupled together. This makes the realized functionality closer to PSICA and comparison, rather than direct cardinality testing. To recover the TPSI paradigm without revealing the exact cardinality to TP, the final quantum measurements must first be made semantically uninterpretable to TP. From Quantum Measurements to Hidden-Label Vectors. We address this issue by introducing a participant-side Zixian Gong et al.: Preprint submitted to Elsevier
hidden flip vector. The flip at position 𝑡 is jointly realized through correlated aggregate rotations of all participants, so TP can perform the final measurement but cannot determine which deterministic label corresponds to an intersectionconsistent outcome. The participant side keeps a synchronized reference-label vector, which records the correct postflip interpretation of each position. Since our construction is also based on rotations of angle 𝜋∕𝑛, positions held by only a subset of participants may yield probabilistic same/opposite outcomes, TP measures 𝓁 repeated photon sequences and compresses them into two deterministic-label vectors 𝑧𝖲 and 𝑧𝖮 . In addition, positive and negative anchor sets are mixed with the real domain before the position-hiding map, which further obscures TP’s structural view of deterministic positions and later supports an anchor-consistency check. Consequently, after the quantum phase, TP holds only the hidden-label vectors 𝑧𝖲 and 𝑧𝖮 , while the participant side retains the information needed to interpret them. In this way, the quantum phase no longer outputs a cardinality-interpretable result to TP, but only a semantically blinded measurement interface for the subsequent test. The remaining task is therefore reduced to testing the threshold condition over hidden-label measurements without exposing the labels or the exact cardinality.
3. Realizing Cardinality Testing for Hidden-Label Measurements After the quantum phase discussed above, TP does not obtain an interpretable intersection vector. Instead, TP only holds the hidden-label measurement vectors , whose labels cannot be mapped to intersection and non-intersection positions without the participant-side information. Therefore, the remaining task is to test the threshold condition over these hidden-label vector without revealing the measurement labels, the reference labels, and the exact cardinality. We realize this task by reducing it to a masked label-consistency test and instantiating the required inner products using oblivious linear evaluation (OLE). 𝑝 𝖮𝖫𝖤 : Oblivious Linear Evaluation (OLE)
Parameters: A finite field 𝔽𝑝 . Inputs: Alice inputs 𝑥 ∈ 𝔽𝑝 . Bob inputs 𝑢, 𝑣 ∈ 𝔽𝑝 . Output: Alice learns 𝑧 = 𝑢𝑥 + 𝑣 ∈ 𝔽𝑝 . Bob learns ⊥. 𝑝 𝖵𝖮𝖫𝖤 : Vector Oblivious Linear Evaluation (VOLE)
Parameters: A finite field 𝔽𝑝 , and vector length 𝐿. Inputs: Alice inputs 𝑥 ∈ 𝔽𝑝 . Bob inputs 𝐮, 𝐯 ∈ 𝔽𝑝𝐿 . Output: Alice learns 𝐳 = 𝐮𝑥 + 𝐯 ∈ 𝔽𝑝𝐿 . Bob learns ⊥. Figure 1: Ideal functionalities for OLE and VOLE.
3.1. Oblivious Inner Product (OIP) from OLE OLE and Vector OLE Functionalities. OLE can be viewed as the linear case of Oblivious Polynomial Evaluation (OPE) [NP99] that enables a receiver to compute a linear combination of the sender’s inputs. Vector OLE (VOLE) generalizes this primitive to vectors, as illustrated in Fig. 1. Page 2 of 11
QTPSI Table 1 Summary of notation. Symbol
Description
Symbol
Description
𝑃𝑖 𝑀 𝑋𝑖 𝑌𝑖 𝜏 𝓁 𝐾𝖯 𝑘 𝐛
The 𝑖-th participant, where 𝑖 ∈ [𝑛]. Augmented domain size. Private set held by 𝑃𝑖 . Length-𝑀 indicator vector encoded by 𝑃𝑖 . Threshold for revealing the intersection. Repetition number. Participant-only master key. Participant-side multiplicative hiding key. Hidden label-flip vector.
𝚯 𝚫𝑖 𝑇𝑖 𝜗0 𝜗𝑖,𝑡 𝑧𝖲 , 𝑧𝖮 𝜌 𝑚 , 𝑚 𝑑 , 𝑑
Semantic-flip angle vector with Θ𝑡 = 𝑏𝑡 𝜋. Rotation-share vector of 𝑃𝑖 . Pairwise TP–𝑃𝑖 rotation-mask vector. TP-local initial rotation vector. Data-dependent rotation angle of 𝑃𝑖 at position 𝑡. Indicator vectors obtained by TP. Participant-side reference label vector. Selector masks for real and anchor positions. Inconsistency counts.
VOLE significantly reduces the overhead of batch OLE generation, making it a cornerstone for efficient cryptographic protocols such as zero-knowledge proofs and PSI [BCG+ 18, WYK+ 21, RS21]. They can be instantiated using different cryptographic techniques, such as OT-based extensions, function secret sharing (FSS) with distributed point functions [BCG+ 18]. In particular, for our quantum setting, it can be instantiated from lattice-based assumptions such as RLWE [BEPU+ 22]. Constructing OIP. For our cardinality testing subroutine, the useful interface is not OLE itself, but an oblivious inner product (OIP) functionality. Given two private vectors, OIP outputs additive shares of their inner product as shown in 2, which is exactly the form needed later for Hamming distance shares. Concretely, let Alice hold 𝐚 = (𝑎0 , … , 𝑎𝐿−1 ) ∈ 𝔽𝑝𝐿 and Bob hold 𝐛 = (𝑏0 , … , 𝑏𝐿−1 ) ∈ 𝔽𝑝𝐿 . For each coordinate 𝑡, Alice inputs 𝑎𝑡 to OLE, while Bob inputs (𝑏𝑡 , 𝑟𝑡 ) for a random 𝑟𝑡 ∈ 𝔽𝑝 . Alice obtains 𝑎𝑡 𝑏𝑡 + 𝑟𝑡 , and Bob keeps −𝑟𝑡 as his local share. After summing over all coordinates, Alice and Bob obtain additive shares 𝑠𝐴 = ∑𝐿−1 ∑𝐿−1 𝑡=0 (𝑎𝑡 𝑏𝑡 + 𝑟𝑡 ), 𝑠𝐵 = − 𝑡=0 𝑟𝑡 , which satisfy 𝑠𝐴 + 𝑠𝐵 = ⟨𝐚, 𝐛⟩ (mod 𝑝).
results at position 𝑡 are all-same as initial basis, and 𝑧𝖮 𝑡 = 1 if they are all-opposite compared to initial basis. For mixed outcomes, 𝑧𝖲𝑡 = 𝑧𝖮 𝑡 = 0. The participant side holds a reference label vector 𝜌 ∈ {0, 1}𝑀 , where 𝜌𝑡 = 1 ⊕ 𝑏𝑡 represents the deterministic label expected for an intersection position after the hidden flip 𝑏𝑡 . It also holds two selector vectors 𝑚 , 𝑚 ∈ {0, 1}𝑀 , selecting the hidden real-domain positions and the hidden anchor positions, respectively. For each position 𝑡, define the label-consistency indicator as 𝜒𝑡 = (1 − 𝜌𝑡 )𝑧𝖲𝑡 + 𝜌𝑡 𝑧𝖮 𝑡 . Thus, 𝜒𝑡 = 1 exactly when the deterministic measurement label at position 𝑡 agrees with the participant-side reference label; mixed outcomes contribute 0. For 𝑅 ∈ { , }, define the consistency count ∑ 𝐶𝑅 = 𝑀−1 𝑡=0 𝑚𝑅,𝑡 𝜒𝑡 and the corresponding inconsistency ∑ count 𝑑𝑅 = |𝑅| − 𝐶𝑅 = |𝑅| − 𝑀−1 𝑡=0 𝑚𝑅,𝑡 𝜒𝑡 . Equivalently, ⟨ ⟩ ⟨ ⟩ 𝑑𝑅 = |𝑅| − 𝑧𝖲 , 𝑚𝑅 ⊙ (1 − 𝜌) − 𝑧𝖮 , 𝑚𝑅 ⊙ 𝜌 . Here, 𝑑 counts real-domain positions that are not confirmed as intersection-consistent, while 𝑑 checks whether the anchor positions satisfy their prescribed labels. Participant side
TP side
𝑝 𝖮𝖨𝖯 : Oblivious Inner Product (OIP)
Parameters: A finite field 𝔽𝑝 , and vector length 𝐿. Inputs: Alice inputs 𝐚 ∈ 𝔽𝑝𝐿 . Bob inputs 𝐛 ∈ 𝔽𝑝𝐿 . Output: Alice receives 𝑠𝐴 ∈ 𝔽𝑝 , and Bob receives 𝑠𝐵 ∈ 𝔽𝑝 , such that 𝑠𝐴 + 𝑠𝐵 = ⟨𝐚, 𝐛⟩ (mod 𝑝). Figure 2: Ideal functionality for oblivious inner product (OIP).
Since the consistency statistics are linear combinations of inner products between TP-held label vectors and participant-held masks, OIP provides a natural interface for realizing the classical testing layer.
3.2. Masked Label-Consistency Sharing and Threshold Decision Masked label-consistency counting. We now instantiate the OIP interface for the deterministic measurement outcomes obtained in the quantum phase. Let 𝑧𝖲 , 𝑧𝖮 ∈ {0, 1}𝑀 be TP’s indicator vectors, where 𝑧𝖲𝑡 = 1 if the 𝓁 measurement Zixian Gong et al.: Preprint submitted to Elsevier
$
TP TP TP M aTP U , cU , aA , c A ← F p
{mU , mU ⊙ ρ, mA , mA ⊙ ρ}(1) P P P {aP U , cU , aA , cA }(1)
{mU , mU ⊙ ρ, mA , mA ⊙ ρ}(M ) P P P {aP U , cU , aA , cA }(M )
p FOLE
TP TP TP {z S , z O , aTP U , cU , aA , cA }(1)
.. . p FOLE
TP TP TP {z S , z O , aTP U , cU , aA , cA }(M )
Figure 3: Using OLE for additive shares. Participant side ρ, mU , mA P P P aP U , cU , aA , cA
TP side S
z ,z p FOIP
O
TP TP TP aTP U , cU , aA , cA
Figure 4: OIP Constructed from OLE.
Consistency-share generation. TP and the participant 𝑝 side invoke 𝖮𝖨𝖯 to obtain additive shares of ⟨𝑧𝖲 , 𝑚 ⊙ (1 − 𝖮 𝜌)⟩, ⟨𝑧 , 𝑚 ⊙ 𝜌⟩, ⟨𝑧𝖲 , 𝑚 ⊙ (1 − 𝜌)⟩, and ⟨𝑧𝖮 , 𝑚 ⊙ 𝜌⟩. Page 3 of 11
QTPSI
The OIP interface can be instantiated from coordinate-wise OLE calls, as illustrated in Fig. 3 and 4. ⟨ ⟩ For 𝑅 ∈ { , }, write 𝑎TP +𝑎P𝑅 = 𝑧𝖲 , 𝑚𝑅 ⊙ (1 − 𝜌) , 𝑅 ⟨ ⟩ TP + 𝑐 P = 𝑐𝑅 𝑧𝖮 , 𝑚𝑅 ⊙ 𝜌 (mod 𝑝). Then TP computes 𝑅 TP = −𝑎TP − 𝑐 TP (mod 𝑝), while the participant side 𝛿𝑅 𝑅 𝑅 P = |𝑅| − 𝑎P − 𝑐 P (mod 𝑝). It follows that computes 𝛿𝑅 𝑅 𝑅 TP + 𝛿 P = 𝑑 (mod 𝑝). 𝛿𝑅 𝑅 𝑅 Anchor check and threshold decision. After the sharTP , 𝛿 TP ), while the participant side ing step, TP holds (𝛿 P , 𝛿 P ). The final Boolean predicate is evaluated by holds (𝛿 a lightweight garbled circuit 𝐶CT , following the standard secure-computation approach for privately evaluating lowdepth decision logic [Yao86], which reconstructs 𝑑 = TP + 𝛿 P ) mod 𝑝 and 𝑑 = (𝛿 TP + 𝛿 P ) mod 𝑝, and outputs (𝛿 only 𝖿 𝗅𝖺𝗀 = 1 ⟺ (𝑑 = 0) ∧ (𝑑 ≤ | | − 𝜏). The condition 𝑑 = 0 verifies the anchor positions, while 𝑑 ≤ | | − 𝜏 means that at least 𝜏 real-domain positions are confirmed as intersection-consistent. The complete subprotocol is shown in Fig. 5. By the privacy of garbled-circuit evaluation, the parties learn only the Boolean predicate value, not the explicit inconsistency counts 𝑑 , 𝑑 . Thus, ⋂ the subprotocol realizes cardinality testing as 𝟏[| 𝑖 𝑋𝑖 | ≥ ⋂ 𝜏], rather than exposing | 𝑖 𝑋𝑖 | and then performing a comparison with 𝜏. Protocol Π𝜏CT : Cardinality Testing from OIP and GC. Parameters: Augmented length 𝑀, finite field 𝔽𝑝 with 𝑝 > 2𝑀, original domain size | |, anchor-domain size ||, and threshold 𝜏. Inputs: TP holds 𝑧𝖲 , 𝑧𝖮 ∈ {0, 1}𝑀 . The participant side holds 𝜌, 𝑚 , 𝑚 ∈ {0, 1}𝑀 , where 𝜌 is the reference label vector, 𝑚 selects the hidden real-domain positions, and 𝑚 selects the hidden anchor positions. 𝑝 OIP Share: TP and the participant side invoke 𝖮𝖨𝖯 four times 𝖲 to obtain additive shares of ⟨𝑧 , 𝑚 ⊙ (1 − 𝜌)⟩, ⟨𝑧𝖮 , 𝑚 ⊙ 𝜌⟩, ⟨𝑧𝖲 , 𝑚 ⊙ (1 − 𝜌)⟩, and ⟨𝑧𝖮 , 𝑚 ⊙ 𝜌⟩. All the following share equalities are taken modulo 𝑝: 𝑎TP + 𝑎P = ⟨𝑧𝖲 , 𝑚 ⊙ (1 − 𝜌)⟩, 𝑐TP + 𝑐P = ⟨𝑧𝖮 , 𝑚 ⊙ 𝜌⟩,
𝑎TP + 𝑎P = ⟨𝑧𝖲 , 𝑚 ⊙ (1 − 𝜌)⟩,
TP P 𝑐 + 𝑐 = ⟨𝑧𝖮 , 𝑚 ⊙ 𝜌⟩.
TP Consistency Share: TP locally computes 𝛿 = −𝑎TP −𝑐TP and TP TP TP 𝛿 = −𝑎 − 𝑐 . The participant side locally computes: P 𝛿 = | | − 𝑎P − 𝑐P , P P 𝛿 = || − 𝑎P − 𝑐
(mod 𝑝).
Threshold GC: TP and the participant side evaluate a garbled P P TP TP , 𝛿 ) from circuit 𝐶CT with inputs (𝛿 , 𝛿 ) from TP and (𝛿 TP + the participant side. The circuit reconstructs 𝑑 = (𝛿 P TP P 𝛿 ) mod 𝑝 and 𝑑 = (𝛿 + 𝛿 ) mod 𝑝, and outputs: 𝖿𝗅𝖺𝗀 = 1 ⟺ (𝑑 = 0) ∧ (𝑑 ≤ | | − 𝜏). Output: Both sides learn only 𝖿𝗅𝖺𝗀. Neither side learns 𝑑 , 𝑑 , nor the other side’s private vectors. Figure 5: Masked Hidden-label Cardinality Testing Protocol.
Zixian Gong et al.: Preprint submitted to Elsevier
4. Proposed Quantum TPSI Protocol We now present the proposed MP-QTPSI protocol. The protocol involves 𝑛 participants 𝑃1 , … , 𝑃𝑛 and a semi-honest third party TP. Each participant 𝑃𝑖 holds a private set 𝑋𝑖 = ⋂ 𝓁 {𝑥1𝑖 , … , 𝑥𝑖 𝑖 } ⊆ . The goal is to reveal 𝑛𝑖=1 𝑋𝑖 only when its cardinality is at least the threshold 𝜏, and otherwise reveal no intersection element. The protocol uses two anchor sets + and − in addition to the original universe . After the position-hiding map, these anchors are mixed with the real-domain positions and are later used to define the reference labels and to support the anchor-consistency check. Since TP does not know the hidden anchor locations and labels, this check can detect inconsistent or tampered measurement output with a certain probability. In our protocol, TP is used as a quantum-state preparer and measurement party, but it is not allowed to collude with any participant. Different from existing TP-centered quantum TPSI protocols, TP does not directly obtain interpretable intersection indices or the exact intersection cardinality. Instead, the quantum interaction produces a hiddenlabel measurement vector, and the threshold decision is made through the masked cardinality-testing subprotocol described in Section 3. The overall workflow is illustrated in Fig. 6. ̃ = ∪ + ∪ − be the augmented Setup. Let universe with {0, … , 𝑀 − 1}, where = {0, … , 𝑞 − 1} is the original real domain and the remaining positions are ̃|. The participants occupied by + and − and let 𝑀 = | first execute a TP-free QCKA protocol [FYC+ 15, PHG+ 21] to establish a participant-only master key 𝐾𝖯 . From 𝐾𝖯 , they derive the multiplicative hiding key 𝑘 ∈ ℤ∗𝑀 , the hidden label-flip vector 𝐛 = (𝑏0 , … , 𝑏𝑀−1 ) ∈ {0, 1}𝑀 , the semantic-flip angle vector 𝚯 = (Θ0 , … , Θ𝑀−1 ) with Θ𝑡 = 𝑏𝑡 𝜋, and the rotation-share vectors 𝚫𝑖 = (Δ𝑖,0 , … , Δ𝑖,𝑀−1 ) ∑ satisfying 𝑛𝑖=1 Δ𝑖,𝑡 ≡ Θ𝑡 (mod 2𝜋) for every position 𝑡. In addition, for each participant 𝑃𝑖 , TP and 𝑃𝑖 run a QKD protocol [BB14] to establish a pairwise key, from which they derive the rotation-mask vector 𝑇𝑖 = (𝑇𝑖,0 , … , 𝑇𝑖,𝑀−1 ). Finally, TP locally samples an initial blinding vector 𝜗0 = (𝜗0,0 , … , 𝜗0,𝑀−1 ). ̃𝑖 = Encoding. Each participant augments its input as 𝑋 𝑋𝑖 ∪ + , while − is inserted into none of the participants’ sets. Using the hiding key 𝑘, all positions are permuted by 𝑥 ↦ 𝑘𝑥 mod 𝑀, giving the hidden domains 𝑘 , 𝑘+ , and 𝑘− 𝑚𝑜𝑑 𝑀. The selector vectors 𝑚 , 𝑚 ∈ {0, 1}𝑀 are defined according to this hidden partition where 𝑚 + 𝑚 = 𝟏. Specifically, 𝑚 ,𝑡 = 1 iff 𝑡 ∈ 𝑘 , and 𝑚,𝑡 = 1 iff 𝑡 ∈ 𝑘+ ∪ 𝑘− . Thus 𝑚 marks the positions originating from the real domain, while 𝑚 marks the anchor positions after the 𝑘𝑥 mod 𝑀 permutation. The participants also define the reference label vector 𝜌 ∈ {0, 1}𝑀 . For positions expected to behave as matching positions, namely 𝑡 ∈ 𝑘 ∪ 𝑘+ , they set 𝜌𝑡 = 1 ⊕ 𝑏𝑡 ; for negative-anchor positions 𝑡 ∈ 𝑘− , they set 𝜌𝑡 = Page 4 of 11
QTPSI Phase 3. Interaction TP
Phase 1. Setup
Phase 2. Encoding
• TP-free QCKA -> 𝐾𝐾𝑃𝑃 • QKD -> 𝑇𝑇𝑖𝑖 • TP samples 𝜗𝜗0
• Augment with 𝒜𝒜+ , 𝒜𝒜−
𝑃𝑃1
𝑃𝑃𝑛𝑛
• Photon sequences • Local rotations • Decoy checking
•Apply 𝑘𝑘𝑘𝑘 𝑚𝑚𝑚𝑚𝑚𝑚 𝑀𝑀 • Encode 𝑌𝑌𝑖𝑖
𝑃𝑃2
…
Phase 4. Measurement • Remove TP-side masks • Measure final states • Obtain hidden-label vector: (𝑧𝑧 S , 𝑧𝑧 O )
Phase 5. Cardinality Testing •OIP shares • Tiny GC • Output 𝑓𝑓𝑓𝑓𝑓𝑓𝑓𝑓
Phase 6. Reconstruction • If flag = 0: abort • If flag = 1: reveal(𝑧𝑧 S, 𝑧𝑧 O ) • Reconstruct intersection
Classical Phase
Quantum Phase
Figure 6: Flowchart.
Protocol 1 Quantum Multi-party Threshold PSI with Cardinality Testing Input: Private sets 𝑋𝑖 ⊆ , threshold 𝜏, anchor sets + , − , repetition number 𝓁. ⋂𝑛 Output: Reveal 𝑖=1 𝑋𝑖 iff its cardinality is at least 𝜏. Phase 1: Setup. ̃ = ∪ + ∪ − and 𝑀 = | ̃|. 1: Let 2: Participants run TP-free QCKA to obtain 𝐾𝖯 and derive 𝑘 ∈ ℤ∗𝑀 , 𝐛 = (𝑏0 , … , 𝑏𝑀−1 ) ∈ {0, 1}𝑀 , 𝚯 = (Θ0 , … , Θ𝑀−1 ) with Θ𝑡 = 𝑏𝑡 𝜋, ∑𝑛 and rotation-share vectors 𝚫𝑖 = (Δ𝑖,0 , … , Δ𝑖,𝑀−1 ) satisfying 𝑖=1 Δ𝑖,𝑡 ≡ Θ𝑡 (mod 2𝜋) for all 𝑡. 3: For each 𝑖 ∈ [𝑛], TP and 𝑃𝑖 run QKD to derive 𝑇𝑖 = (𝑇𝑖,0 , … , 𝑇𝑖,𝑀−1 ); TP samples 𝜗0 = (𝜗0,0 , … , 𝜗0,𝑀−1 ). Phase 2: Encoding. 4: Compute the hidden domains 𝑘 , 𝑘+ , and 𝑘− (mod 𝑀). 5: Define 𝑚 = 𝟏𝑘 , 𝑚 = 𝟏𝑘+ ∪𝑘− , and 𝜌𝑡 = 1 ⊕ 𝑏𝑡 for 𝑡 ∈ 𝑘 ∪ 𝑘+ , 𝜌𝑡 = 𝑏𝑡 for 𝑡 ∈ 𝑘− . 6: for 𝑖 = 1 to 𝑛 do ̃𝑖 = 𝑋𝑖 ∪ + and encodes 𝑌𝑖 = 𝟏{𝑘𝑥 mod 𝑀∶𝑥∈𝑋̃ } ∈ {0, 1}𝑀 . 7: 𝑃𝑖 sets 𝑋 𝑖 8: end for Phase 3: Interaction and Measurement. 9: TP prepares 𝓁 length-𝑀 photon sequences, applies 𝑅𝑦 (𝜗0,𝑡 ) to each position 𝑡, inserts decoys, and sends the sequence to 𝑃1 . 10: for 𝑖 = 1 to 𝑛 do 11: 𝑃𝑖 checks decoys and applies 𝑅𝑦 (𝜗𝑖,𝑡 + 𝑇𝑖,𝑡 + Δ𝑖,𝑡 ) at each position 𝑡, where 𝜗𝑖,𝑡 = 𝜋∕𝑛 if 𝑌𝑖,𝑡 = 1 and 𝜗𝑖,𝑡 = 0 otherwise. 12: 𝑃𝑖 inserts fresh decoys and forwards the sequence to 𝑃𝑖+1 . 13: end for ∑𝑛 14: TP checks decoys, applies 𝑅𝑦 (−𝜗0,𝑡 − 𝑖=1 𝑇𝑖,𝑡 ) at each position 𝑡, and measures to obtain 𝑧𝖲 , 𝑧𝖮 ∈ {0, 1}𝑀 . Phase 4: Cardinality Testing. 15: TP and the participants invoke Π𝜏CT on 𝑧𝖲 , 𝑧𝖮 ∈ {0, 1}𝑀 and (𝜌, 𝑚 , 𝑚 , 𝜏). ∑𝑀−1 ). 16: Π𝜏CT outputs 𝖿 𝗅𝖺𝗀 = 1 iff 𝑑 = 0 and 𝑑 ≤ | | − 𝜏, where 𝑑𝑅 = |𝑅| − 𝑡=0 𝑚𝑅,𝑡 ((1 − 𝜌𝑡 )𝑧𝖲𝑡 + 𝜌𝑡 𝑧𝖮 𝑡 Phase 5: Intersection Reconstruction. 17: if 𝖿 𝗅𝖺𝗀 = 1 then { } 18: TP broadcasts 𝑧𝖲 , 𝑧𝖮 ∈ {0, 1}𝑀 , and each participant outputs = 𝑘−1 𝑡 mod 𝑀 ∶ 𝑡 ∈ 𝑘 , (1 − 𝜌𝑡 )𝑧𝖲𝑡 + 𝜌𝑡 𝑧𝖮𝑡 = 1 . 19: else 20: Abort. 21: end if
𝑏𝑡 , where 𝑏𝑡 is the hidden label-flip bit used to blind the semantic meaning of the final measurement label at position 𝑡. Finally, each participant encodes its hidden augmented set as indicator vector 𝑌𝑖 = 𝟏{𝑘𝑥 mod 𝑀∶ 𝑥∈𝑋̃ } ∈ {0, 1}𝑀 , which 𝑖 is used in the rotation phase. Interaction and measurement. To reduce measurement uncertainty, TP prepares 𝓁 length-𝑀 photon sequences, each following an identical state configuration where every qubit is randomly chosen from {|0⟩, |1⟩, |+⟩, |−⟩}. Then, TP applies the initial blinding rotation 𝑅𝑦 (𝜗0 ), inserts decoy photons, and sends the protected sequences to 𝑃1 . For 𝑖 = 1, … , 𝑛, participant 𝑃𝑖 first checks the decoy photons with the previous sender and removes them. Then 𝑃𝑖 applies the position-wise rotation 𝑅𝑦 (𝜗𝑖,𝑡 + 𝑇𝑖,𝑡 + Δ𝑖,𝑡 ) to each photon Zixian Gong et al.: Preprint submitted to Elsevier
at position 𝑡, where 𝜗𝑖,𝑡 = 𝜋∕𝑛 if 𝑌𝑖,𝑡 = 1, and 𝜗𝑖,𝑡 = 0 otherwise. Afterwards, 𝑃𝑖 inserts fresh decoy photons and forwards the protected sequences to 𝑃𝑖+1 until 𝑃𝑛 returns the final sequence to TP. After the final decoy check, TP removes the rotations ∑ known to itself by applying 𝑅𝑦 (−𝜗0,𝑡 − 𝑛𝑖=1 𝑇𝑖,𝑡 ) at each position 𝑡. The remaining effective rotation is therefore ∑𝑛 ∑𝑛 ∑𝑛 ∑𝑛 𝑖=1 𝜗𝑖,𝑡 + 𝑖=1 Δ𝑖,𝑡 = 𝑖=1 𝜗𝑖,𝑡 + Θ𝑡 = 𝑖=1 𝜗𝑖,𝑡 + 𝑏𝑡 𝜋. TP measures the 𝓁 sequences and derives two deterministicoutcome indicator vectors 𝑧𝖲 , 𝑧𝖮 ∈ {0, 1}𝑀 : 𝑧𝖲𝑡 = 1 if the 𝓁 measurement outcomes at position 𝑡 are all-same, 𝑧𝖮 𝑡 = 1 if they are all-opposite, and 𝑧𝖲𝑡 = 𝑧𝖮 = 0 otherwise. 𝑡 Cardinality testing. Participants side and TP invoke the cardinality testing subprotocol Π𝜏CT described in Section 3. Page 5 of 11
QTPSI
The subprotocol first checks the anchor consistency through 𝑑 = 0, which verifies whether the returned measurement vector is consistent with the prescribed anchor positions. It then tests the real-domain threshold condition 𝑑 ≤ | |−𝜏, and outputs only the Boolean value 𝖿 𝗅𝖺𝗀. Intersection Reconstruction. If 𝖿 𝗅𝖺𝗀 = 1, then both the anchor-consistency check and the cardinality testing have passed. TP broadcasts the complete label vectors 𝑧𝖲 and 𝑧𝖮 to all participants. Using the reference labels 𝜌, the hidden real-domain selector 𝑚 , and the inverse 𝑘−1 mod 𝑀, each intersection { −1 participant locally recovers the } as = 𝑘 𝑡 mod 𝑀 ∶ 𝑡 ∈ 𝑘 , (1 − 𝜌𝑡 )𝑧𝖲𝑡 + 𝜌𝑡 𝑧𝖮 = 1 . 𝑡
5. Correctness and Security Analysis 5.1. Correctness Analysis In this subsection, we establish the correctness of the proposed protocol from the following three aspects: (1) TP obtains a hidden-label measurement vector that correctly encodes the intersection pattern; (2) The Π𝜏CT outputs the correct threshold decision; (3) Once the threshold condition is satisfied, the participants can correctly reconstruct the real intersection. Theorem 1 (Correctness of intersection pattern). The vectors 𝑧𝖲 and 𝑧𝖮 measured by TP correctly encode the intersection pattern over the augmented domain under the participant-side label flip vector 𝐛. Proof. For each position 𝑡, after all participants complete their rotations and TP removes the rotations known to itself, the remaining effective rotation is 𝜗0,𝑡 +
𝑛 ∑ 𝑖=1
(𝜗𝑖,𝑡 + 𝑇𝑖,𝑡 + Δ𝑖,𝑡 ) − 𝜗0,𝑡 −
𝑛 ∑
𝑇𝑖,𝑡 =
𝑖=1
∑𝑛
𝑛 ∑
Theorem 2 (Correctness of cardinality testing). The subprotocol Π𝜏CT outputs the correct value of 𝖿 𝗅𝖺𝗀. Proof. By the construction in Section 3.2 and the steps of 𝑝 Π𝜏CT , TP and the participant side invoke 𝖮𝖨𝖯 to obtain additive shares of the inner products required for the consistency counts over the real-domain and anchor positions. They then locally derive additive shares of 𝑑 and 𝑑 , satisfying 𝑑𝑅 = TP + 𝛿 P (mod 𝑝) for 𝑅 ∈ { , }. 𝛿𝑅 𝑅 The tiny garbled circuit 𝐶CT reconstructs these values only inside the circuit and evaluates 𝖿 𝗅𝖺𝗀 = 1 ⟺ (𝑑 = 0) ∧ (𝑑 ≤ | | − 𝜏). Hence, 𝑑 = 0 correctly performs the anchor check, while 𝑑 ≤ | | − 𝜏 correctly judge the threshold decision. Therefore, Π𝜏CT outputs the correct value of 𝖿 𝗅𝖺𝗀. Theorem 3 (Correctness of reconstruction). If 𝖿 𝗅𝖺𝗀 = 1, ⋂ then the participants can recover the 𝑛𝑖=1 𝑋𝑖 exactly. Proof. If 𝖿 𝗅𝖺𝗀 = 1, TP broadcasts 𝑧𝖲 and 𝑧𝖮 to all participants. By the correctness in Theorem 1, for each hidden realdomain position 𝑡 ∈ 𝑘 𝜒𝑡 = (1 − 𝜌𝑡 )𝑧𝖲𝑡 + 𝜌𝑡 𝑧𝖮 𝑡 = 1 holds exactly when position 𝑡 corresponds to an element contained in every(⋂ participant’s encoded set. Hence, { 𝑡 ∈ 𝑘 ∶ 𝜒𝑡 = ) 1 } = 𝑘 𝑛𝑖=1 𝑋𝑖 . Since 𝑘 ∈ ℤ∗𝑀 , the map 𝑥 ↦ 𝑘𝑥 mod 𝑀 is invertible. Therefore, each participant can apply 𝑘−1 mod 𝑀 to the recovered hidden positions and obtain 𝑛 } ⋂ { −1 𝑋𝑖 . = 1 = 𝑘 𝑡 mod 𝑀 ∶ 𝑡 ∈ 𝑘 , (1 − 𝜌𝑡 )𝑧𝖲𝑡 + 𝜌𝑡 𝑧𝖮 𝑡 𝑖=1
𝜗𝑖,𝑡 + Θ𝑡 .
𝑖=1
Let 𝑟𝑡 = 𝑖=1 𝑌𝑖,𝑡 . Since 𝜗𝑖,𝑡 = 𝜋∕𝑛 if 𝑌𝑖,𝑡 = 1 and 𝜗𝑖,𝑡 = 0 𝑟𝜋 otherwise, the residual rotation at position 𝑡 is 𝑡𝑛 + Θ𝑡 = 𝑟𝑡 𝜋 + 𝑏𝑡 𝜋. We consider the following three cases. 𝑛 Case 1: 𝑟𝑡 = 0. No participant holds the encoded element at position 𝑡, so the residual rotation is 𝑏𝑡 𝜋. Hence the final measurement relation is all-same when 𝑏𝑡 = 0, and allopposite when 𝑏𝑡 = 1. Case 2: 1 ≤ 𝑟𝑡 ≤ 𝑛 − 1. Only a proper subset of participants holds the encoded element at position 𝑡, and the 𝑟𝜋 residual rotation is 𝑡𝑛 +𝑏𝑡 𝜋, which is neither 0 nor 𝜋 modulo 2𝜋. Therefore, the resulting sequence are in superposition states. Over the 𝓁 repeated sequences, such a position is recorded as "mixed". Case 3: 𝑟𝑡 = 𝑛. All participants hold the encoded element at position 𝑡, so the residual rotation is 𝜋 + 𝑏𝑡 𝜋 ≡ (1 ⊕ 𝑏𝑡 )𝜋 (mod 2𝜋). Hence the final measurement relation is allopposite when 𝑏𝑡 = 0, and all-same when 𝑏𝑡 = 1. Consequently, 𝑧𝖲𝑡 and 𝑧𝖮 𝑡 encode the deterministic nonintersection and intersection labels after the participant-side flip 𝑏𝑡 , while partially matched positions are classified as "mixed". Thus, the vectors 𝑧𝖲 and 𝑧𝖮 correctly represent the Zixian Gong et al.: Preprint submitted to Elsevier
intersection pattern over the augmented domain under the label-flip vector 𝐛.
5.2. Security Analysis In this subsection, we analyze the security of the proposed protocol from the following three aspects: (1) Any outside eavesdropper cannot obtain information about the private sets of the participants; (2) TP cannot obtain private information about the participants, including their private sets, the intersection indices, or the exact intersection cardinality; (3) No participant can obtain extra information about the private sets of other participants even when colluding with other participants. together with a remark on the detection of tampering behavior when TP modifies the reported measurement results. Theorem 4 (Privacy against eavesdroppers). Outside eavesdropper can not learn information about the participants’ private sets through common attacks. Proof. Suppose that an outside eavesdropper Eve attempts to learn information about the private sets of the participants from the transmitted photon sequences. However, every transmission is protected by randomly inserted decoy Page 6 of 11
QTPSI
photons chosen from {|0⟩, |1⟩, |+⟩, |−⟩}, whose positions and preparation bases are unknown to Eve. We consider two representative attacks: Intercept–Resend Attack. If Eve intercepts a transmitted sequence, measures each photon with a guessed basis, and resends a fabricated sequence, Eve inevitably disturbs a fraction of the decoy photons during her eavesdropping attempt. For each decoy photon, she avoids detection with a maximum probability of 3∕4. Consequently, if 𝛿 decoy photons are transmitted, the probability of Eve bypassing the eavesdropping check is at most (3∕4)𝛿 , while the detection probability is at least 1 − (3∕4)𝛿 . Auxiliary-qubit attack. Eve may also attach an auxiliary qubit |0⟩𝑎 to a transmitted decoy photon |𝜓⟩𝑑 and apply an oracle-type operation 𝑈𝑓 |𝑥⟩𝑑 |𝑦⟩𝑎 = |𝑥⟩𝑑 |𝑦 ⊕ 𝑓 (𝑥)⟩𝑎 . For computational-basis states, one has 𝑈𝑓 |0⟩𝑑 |0⟩𝑎 = |0⟩𝑑 |𝑓 (0)⟩𝑎 , 𝑈𝑓 |1⟩𝑑 |0⟩𝑎 = |1⟩𝑑 |𝑓 (1)⟩𝑎 . Thus, if the decoy photon were known to be in the 𝑍-basis, Eve might try to encode basis information into the auxiliary qubit. However, when the decoy photon is prepared in the 𝑋-basis, namely |𝜓⟩𝑑 ∈ {|+⟩, |−⟩}, we have ) 1 ( 𝑈𝑓 |±⟩𝑑 |0⟩𝑎 = √ 𝑈𝑓 |0⟩𝑑 |0⟩𝑎 ± 𝑈𝑓 |1⟩𝑑 |0⟩𝑎 2 ) 1 ( = √ |0⟩𝑑 |𝑓 (0)⟩𝑎 ± |1⟩𝑑 |𝑓 (1)⟩𝑎 2 [ ] |𝑓 (0)⟩𝑎 ± |𝑓 (1)⟩𝑎 |𝑓 (0)⟩𝑎 ∓ |𝑓 (1)⟩𝑎 1 = √ |+⟩𝑑 + |−⟩𝑑 . √ √ 2 2 2 the reduced state of Eve’s auxiliary qubit is identical for the two possible decoy states. Hence, Eve cannot distinguish |+⟩ from |−⟩ from the auxiliary system. Furthermore, Since Eve knows neither the decoy positions nor their bases of |𝜓⟩𝑑 , the auxiliary-qubit attack cannot reveal useful information without being exposed by the decoy check. Theorem 5 (Privacy against TP). TP learns neither the participants’ private sets, nor the intersection indices, nor the exact intersection cardinality. Proof. (1) TP cannot learn any participants’ private sets. To recover the private set 𝑋𝑖 , TP would have to determine the encoded membership vector 𝑌𝑖 , or equivalently, distinguish whether 𝑃𝑖 applies the data-dependent rotation 𝜗𝑖,𝑡 = 0 or 𝜗𝑖,𝑡 = 𝜋∕𝑛 at each position 𝑡. TP may attempt to prepare entangled photons instead of single photons, keep one subsystem, and send the other subsystem through the protocol. Let 𝜌𝐴𝐵 be such an entangled state, where subsystem 𝐴 is retained by TP and subsystem 𝐵 is sent to 𝑃𝑖 . If 𝑃𝑖 applies a local unitary 𝑈𝑖 on subsystem 𝐵, then the reduced state available to TP is [ ] Tr 𝐵 (𝐼 ⊗ 𝑈𝑖 )𝜌𝐴𝐵 (𝐼 ⊗ 𝑈𝑖† ) = Tr 𝐵 (𝜌𝐴𝐵 ). Zixian Gong et al.: Preprint submitted to Elsevier
Hence, the subsystem kept by TP is independent of the rotation applied by 𝑃𝑖 . TP may also intercept the sequence immediately after 𝑃𝑖 and attempt to distinguish whether 𝑃𝑖 applies 𝜗𝑖,𝑡 = 0 or 𝜗𝑖,𝑡 = 𝜋∕𝑛 at position 𝑡 via unambiguous state discrimination (USD) test [HB05, CB98]. Let |𝜙𝑖,𝑡 ⟩ be the photon received by 𝑃𝑖 . The two possible output states are |𝜙0 ⟩ = 𝑅𝑦 (𝑇𝑖,𝑡 + Δ𝑖,𝑡 )|𝜙𝑖,𝑡 ⟩, ) ( 𝜋 + 𝑇𝑖,𝑡 + Δ𝑖,𝑡 |𝜙𝑖,𝑡 ⟩. |𝜙1 ⟩ = 𝑅𝑦 𝑛 For any fixed incoming state, they can be written as |𝜙0 ⟩ = cos(𝜔)|0⟩ + sin(𝜔)|1⟩, ) ( ) ( 𝜋 𝜋 |0⟩ + sin 𝜔 + |1⟩, |𝜙1 ⟩ = cos 𝜔 + 2𝑛 2𝑛 where 𝜔 collects all rotations common to the two cases. For two nonorthogonal pure states, the optimal USD success probability is governed by their overlap [CB98]. Hence, ( ) 𝜋 𝖯𝗋𝗈𝖻USD = 1 − ||⟨𝜙0 ∣ 𝜙1 ⟩|| = 1 − cos . 2𝑛 This bound already assumes that TP knows the incoming state and the common rotation offset. In the actual protocol, TP does not know Δ𝑖,𝑡 ; moreover, the encoded vector 𝑌𝑖 is generated after the hiding map 𝑥 ↦ 𝑘𝑥 mod 𝑀, where 𝑘 is unknown to TP; For 𝑖 > 1, the incoming photons are further masked by preceding participants. Hence, TP cannot reliably infer 𝑌𝑖,𝑡 , and therefore cannot recover 𝑃𝑖 ’s private set. (2) TP cannot interpret 𝑧𝖲 , 𝑧𝖮 . After the measurement phase, the semantic meaning of these labels is determined by the participant-side flip vector 𝐛, which is realized through the correlated aggregate rotations {Δ𝑖,𝑡 }𝑛𝑖=1 and is unknown to TP. Moreover, TP does not know the hidden real-domain selector 𝑚 , the anchor selector 𝑚 , or the position-hiding key 𝑘. Hence, TP can neither map measurement labels to actual intersection coordinates nor distinguish between realdomain and anchor positions. (3) TP cannot recover the cardinality. Since TP cannot interpret 𝑧𝖲 and 𝑧𝖮 , it cannot derive the exact intersection cardinality directly from the quantum measurement results. The classical cardinality-testing phase does not reveal it either: the OIP calls provide only additive shares of the required inner products, and the garbled circuit outputs only the predicate bit 𝖿 𝗅𝖺𝗀. At most, by counting the deterministic outcomes represented by 𝑧𝖲 and 𝑧𝖮 , TP may infer the aggre|⋂ | ⋃ gate |||| 𝑛𝑖=1 𝑋𝑖 || + || ⧵ 𝑛𝑖=1 𝑋𝑖 || + |+ | + |− ||| up to the | | statistical classification error controlled by 𝓁 which is insufficient to determine the exact intersection cardinality. Remark 1 (Anchor-based tamper detection). Although TP is assumed to be semi-honest, the anchor positions provide a lightweight consistency check against modification of the reported vectors 𝑧𝖲 and 𝑧𝖮 . Suppose that TP modifies the reported measurement labels at 𝑟 distinct positions. Any nontrivial modification on an anchor position violates the anchor-consistency condition 𝑑 = 0. Hence, TP avoids Page 7 of 11
QTPSI Table 2 Rotation vectors used in the toy-model simulation. Participant
Data rotation 𝝑𝑖
Pairwise mask 𝑇𝑖
Flip share 𝚫𝑖
Total rotation 𝝑𝑖 + 𝑇𝑖 + 𝚫𝑖
( 𝜋6 , 𝜋4 , 𝜋3 , 5𝜋 , 𝜋 , 𝜋 , 𝜋 , 5𝜋 ) 12 6 4 3 12
( 𝜋4 , 5𝜋 , 13𝜋 , 4𝜋 , 5𝜋 , 7𝜋 , 𝜋 , 3𝜋 ) 6 12 3 4 6 2 4
( 𝜋3 , 𝜋6 , 𝜋4 , 𝜋6 , 𝜋3 , 𝜋6 , 𝜋4 , 𝜋6 )
( 𝜋2 , 5𝜋 , 13𝜋 , 7𝜋 , 7𝜋 , 𝜋 , 5𝜋 , 11𝜋 ) 6 12 6 6 6 6 12
𝑃1
𝜋 𝜋 5𝜋 7𝜋 3𝜋 11𝜋 𝜋 𝜋 (0, 𝜋3 , 𝜋3 , 𝜋3 , 𝜋3 , 0, 0, 0) ( 12 , 4 , 12 , 12 , 4 , 12 , 6 , 3 )
𝑃2
(0, 𝜋3 , 𝜋3 , 𝜋3 , 0, 0, 𝜋3 , 𝜋3 )
𝑃3
(0, 𝜋3 , 𝜋3 , 𝜋3 , 𝜋3 , 0, 0, 𝜋3 ) ( 𝜋4 , 5𝜋 , 7𝜋 , 3𝜋 , 11𝜋 , 𝜋 , 𝜋 , 𝜋 ) ( 3𝜋 , 7𝜋 , 17𝜋 , 5𝜋 , 3𝜋 , 7𝜋 , 17𝜋 , 17𝜋 ) ( 7𝜋 , 4𝜋 , 7𝜋 , 3𝜋 , 11𝜋 , 2𝜋 , 7𝜋 , 9𝜋 ) 12 12 4 12 12 3 2 2 12 12 12 2 12 12 12 4 3 3 2 4 3 4 4
( 𝜋6 , 𝜋3 , 𝜋2 , 2𝜋 , 5𝜋 , 0, 𝜋4 , 5𝜋 ) 3 6 12
detection only if all modified positions fall inside the hidden ( ) ( ) real domain 𝑘 with 𝖯𝗋𝗈𝖻Undetected = |𝑟 | ∕ 𝑀𝑟 . Theorem 6 (Privacy against other participants). No participant learns information about another participant’s private set even in collusion with other participants. Proof. We consider an target participant 𝑃𝑖 and assume, as TP does not collude with any participant. To recover 𝑋𝑖 , a dishonest participant or a coalition of participants must infer the encoded membership bit 𝑌𝑖,𝑡 at each position 𝑡, namely, whether 𝑃𝑖 applies 𝜗𝑖,𝑡 = 0 or 𝜗𝑖,𝑡 = 𝜋∕𝑛. Direct observation by the next participant. Consider first the participant 𝑃𝑖+1 , who receives the photon sequence immediately after 𝑃𝑖 . At position 𝑡, the outgoing state of 𝑃𝑖 is of the form 𝑅𝑦 (𝜗𝑖,𝑡 + 𝑇𝑖,𝑡 + Δ𝑖,𝑡 )|𝜙𝑖,𝑡 ⟩. The next participant does not know |𝜙𝑖,𝑡 ⟩, nor the TP–𝑃𝑖 secret rotation 𝑇𝑖,𝑡 . In particular, for 𝑖 = 1, the state sent to 𝑃1 is already blinded by TP’s initial rotation 𝜗0,𝑡 . Collusion of neighboring participants. Now consider a stronger attack in which 𝑃𝑖−1 and 𝑃𝑖+1 collude to recover 𝑃𝑖 ’s private set. They may even replace the legitimate incoming photon by a known state |𝜑𝑡 ⟩ before sending it to 𝑃𝑖 , and then inspect the state returned by 𝑃𝑖 . In this case, the security argument is essentially the same as the USD-based analysis in Part (1) of Section 5. The only difference is that the unknown blinding rotation is now the 𝑇𝑖,𝑡 rather than Δ𝑖,𝑡 . Hence, the same USD bound applies. The same argument extends to any larger coalition of participants: regardless of how many other participants conspire, the target participant’s TP-shared mask 𝑇𝑖 remains unavailable to them. Therefore, they cannot recover 𝑌𝑖 , and hence cannot obtain the private set 𝑋𝑖 .
Table 3 Measurement results of the toy-model simulation. 𝑡 0 1 2 3 4 5 6 7
Origin real(0) real(3) + real(1) real(4) − real(2) real(5)
Class all-same all-same all-opposite all-same mixed all-opposite mixed mixed
Theory
Noisy
Same
Opp.
Same
Opp.
1.000 1.000 0.000 1.000 0.250 0.000 0.750 0.250
0.000 0.000 1.000 0.000 0.750 1.000 0.250 0.750
0.988 0.984 0.013 0.984 0.257 0.016 0.742 0.256
0.012 0.016 0.987 0.016 0.743 0.984 0.258 0.744
̃ = {0, 1, 2+ , 3, 4, 5− , 6, 7}, This yields the position 𝑘 ̃1 = {1, 2, 3, 4}, 𝑘𝑋 ̃2 = {1, 2, 3, 6, 7}, 𝑘𝑋 ̃3 = and 𝑘𝑋 {1, 2, 3, 4, 7}. Accordingly, the encoded indicator vectors are 𝑌1 = (0, 1, 1, 1, 1, 0, 0, 0), 𝑌2 = (0, 1, 1, 1, 0, 0, 1, 1), 𝑌3 = (0, 1, 1, 1, 1, 0, 0, 1). For the hidden semantic flip, we fix 𝐛 = (0, 1, 0, 1, 0, 1, 0, 0), which determines the aggregate flip angles 𝚯 = (0, 𝜋, 0, 𝜋, 0, 𝜋, 0, 0) (mod 2𝜋). The resulting participantside reference label vector is 𝜌 = (1, 0, 1+ , 0, 1, 1− , 1, 1). The corresponding correlated aggregate rotation shares are chosen as Δ1 = ( 𝜋6 , 𝜋4 , 𝜋3 , 5𝜋 , 𝜋 , 𝜋 , 𝜋 , 5𝜋 ), Δ2 = ( 𝜋3 , 𝜋6 , 12 6 4 3 12
𝜋 𝜋 𝜋 𝜋 𝜋 𝜋 , , , , , ), Δ3 = ( 3𝜋 , 7𝜋 , 17𝜋 , 5𝜋 , 3𝜋 , 7𝜋 , 17𝜋 , 17𝜋 ), 4 6 3 6 4 6 2 12 12 12 2 12 12 12 which satisfy Δ1,𝑡 + Δ2,𝑡 + Δ3,𝑡 ≡ Θ𝑡 (mod 2𝜋) for every
𝑡 ∈ {0, … , 7}. For the TP–participant pairwise rotation 𝜋 𝜋 5𝜋 7𝜋 3𝜋 11𝜋 𝜋 𝜋 , 4 , 12 , 12 , 4 , 12 , 6 , 3 ), 𝑇2 = ( 𝜋6 , masks, we take 𝑇1 = ( 12 𝜋 𝜋 2𝜋 5𝜋 , , , , 0, 𝜋4 , 5𝜋 ), 𝑇3 3 2 3 6 12
6. Simulation and Performance Evaluation 6.1. Experimental Simulation Toy Model. To illustrate the quantum phase of the proposed protocol, we consider a toy instance with 𝑛 = 3 participants. The original domain is = {0, 1, 2, 3, 4, 5}, and we introduce one positive anchor and one negative anchor, + = {6} ̃ = ∪ + ∪ − and 𝑀 = | ̃| = and − = {7}. Hence, 8. We set the threshold as 𝜏 = 2. The private sets of the three participants are 𝑋1 = {1, 3, 4}, 𝑋2 = {1, 2, 3, 5}, 𝑋3 = {1, 3, 4, 5}, whose real intersection is 𝑋1 ∩𝑋2 ∩𝑋3 = {1, 3}. Each participant appends the positive anchor set and apply the position-hiding map with hiding key 𝑘 = 3 ∈ ℤ∗8 . Zixian Gong et al.: Preprint submitted to Elsevier
= ( 𝜋4 , 5𝜋 , 7𝜋 , 3𝜋 , 11𝜋 , 𝜋 , 𝜋 , 𝜋 ). 12 12 4 12 12 3 2 𝜋 𝜋 TP further samples the initial blinding rotation 𝝑0 = ( 12 , 6, 𝜋 𝜋 5𝜋 𝜋 7𝜋 2𝜋 , , 12 , 2 , 12 , 3 ) and prepares the initial photon sequence 4 3 ( )
𝑆0 = |0⟩, |+⟩, |1⟩, |−⟩, |0⟩, |+⟩, |1⟩, |−⟩ . The summary of rotation in our toy model is shown in Table 2. Qiskit Simulation. Based on the above toy model, we implement the quantum phase of the proposed protocol using Qiskit. The corresponding quantum circuit is shown in Fig. 7. For each hidden position 𝑡, the residual rotation after TP removes its initial blinding rotation and the pairwise ∑𝑛 𝑟𝜋 masks is 𝑡𝑛 + 𝑏𝑡 𝜋, where 𝑟𝑡 = 𝑖=1 𝑌𝑖,𝑡 is the number of participants holding the encoded element at position 𝑡. Hence, the theoretical probabilities of obtaining the same Page 8 of 11
QTPSI Initial states
q0
RY
TP blind
P1
RY /4
/12
RY
P2
/2
RY
P3
RY
7 /4
7 /12
q1
H
RY /6
5 /6
5 /6
4 /3
RY
RY
q2
X
RY
RY
RY
RY
RY
q3
X
RY
/4
13 /12
RY
H
q4
13 /12
RY
7 /4
7 /3
4 /3
7 /6
3 /2
RY
RY
RY
RY
RY
RY
RY
5 /12
7 /6
RY
RY /6
2 /3
RY
RY
RY
RY
RY
RY
RY
RY
RY /2
7 /6
q6
X
RY
q7
X
/2
RY
11 /4
RY
3 /4
9.16
11 /12
H
3 /2
7 /4
5 /6
RY
2 /3
H
7 /3
5 /4
H
7 /12
RY
H
7 /6
/3
q5
H
RY
TP remove
4 /3
9 /4
H
6.02
c 8
0
2
4
6
1
3
5
7
Figure 7: Quantum Circuit of toy model.
1.0
0.988
0.987
0.984
0.984
0.984
Probability
0.8
0.743
Noisy same probability Noisy opposite probability 0.744
0.742
0.6 0.4 0.258
0.257
0.256
0.2 0.0
0.012
t=0
0.016
0.013
t=1
t=2
0.016
t=3
0.016
t=4
Hidden position t
t=5
t=6
t=7
Figure 8: Noisy Probabilities.
and opposite measurement relations are ( ( ) ) 2 𝑟𝑡 𝜋∕𝑛 + 𝑏𝑡 𝜋 2 𝑟𝑡 𝜋∕𝑛 + 𝑏𝑡 𝜋 𝖲 𝖮 𝑝𝑡 = cos , 𝑝𝑡 = sin . 2 2 To evaluate the robustness of the quantum phase, we perform noisy simulation by adding depolarizing noise with rate 0.2%, phase-damping noise with rate 0.4%, and readout error with rate 0.5% which can be realized through Qiskit_aer.noise. These channels are chosen to reflect representative gate, dephasing, and measurement imperfections in the simulated quantum execution. The resulting noisy same/opposite probabilities are plotted in Fig. 8, and their comparison with the theoretical values is summarized in Table 3. Using 0.9 as the acceptance threshold for deterministic classification, the noisy simulation yields 𝑧𝖲sim = = (0, 0, 1, 0, 0, 1, 0, 0), which ex(1, 1, 0, 1, 0, 0, 0, 0), 𝑧𝖮 sim actly agree with the theoretical expectation. Therefore, when these simulated outputs are supplied to the classical subprotocol Π𝜏CT , the anchor-consistency check is satisfied and the threshold condition is accepted. The participants can then reconstruct the real intersection as 𝑋1 ∩ 𝑋2 ∩ 𝑋3 = {1, 3}.
Zixian Gong et al.: Preprint submitted to Elsevier
6.2. Performance and Comparison Quantum Communication Cost. In the quantum phase, TP prepares 𝓁 photon sequences of length 𝑀, i.e., 𝓁𝑀 signal photons in total. These sequences are transmitted along the chain TP → 𝑃1 → ⋯ → 𝑃𝑛 → TP. If 𝛿 decoy photons are inserted in each transmission for eavesdropping detection, then the )total (quantum communication cost is ( ) (𝑛 + 1)(𝓁𝑀 + 𝛿) = 𝑛(𝓁𝑀 + 𝛿) . Quantum Computation Cost. TP applies 𝓁𝑀 initial blinding rotations, 𝓁𝑀 mask-removal rotations, and performs 𝓁𝑀 final measurements on the signal photons. Hence, TP’s quantum computation cost is (𝓁𝑀 + 𝛿). Each participant 𝑃𝑖 performs 𝓁𝑀 local rotation operations and (𝛿) decoy-photon measurements, giving a per-participant cost of (𝓁𝑀+𝛿). Therefore, computation cost of ( the total quantum ) all participants is 𝑛(𝓁𝑀 + 𝛿) . Notice that the anchor sets are chosen with size independent of the asymptotic domain scale, we have 𝑀 = (𝑞). Performance Comparison. Table 4 compares our protocol with representative classical and quantum TPSI schemes. Unlike the classical constructions in [BMR+ 21, ZCL21, HZT+ 24], our protocol is quantum-cryptography based and therefore fits the long-term security motivation of privacypreserving computation in the quantum setting. At the same Page 9 of 11
QTPSI Table 4 Comparison of TPSI protocols. Protocol
Party Scenarios
Quantum Cryptography Based
[BMR+ 21] Multi-Party
No
[ZCL21]
Two-Party
No
Two-Party [MSD+ 24] Two-Party [LZY+ 26] Multi-Party [WLS+ 26] Multi-Party
No Yes Yes Yes
[HZT+ 24]
Ours
Multi-Party
Yes
Technologies
TP Model
TFHE None GBF None OT Extension FHE None Rotation Trusted Rotation Semi-honest QHE Trusted Rotation Semi-honest OLE
Cardinality Testing Yes Yes Yes No No No Yes
Communication Computation Complexity Complexity ( ) ( )4 𝑛𝜏 𝑛−𝜏 ( ) ( ) 𝜆𝐵 𝑛 log 𝑛 ( √ ( ( 𝑞𝑆𝑁𝑑𝑘𝑠 𝐵)) ( 𝑞 𝑆) ) ( 𝑞 + (𝓁 + 𝛿)𝑞 ) ( 𝑞 + (𝓁 + 𝛿)𝑞 ) 𝑛𝑄(+ 𝑛𝑞(𝓁 +) 𝛿) 𝑛𝑄(+ 𝑛𝑞(𝓁 +) 𝛿) 𝑛(𝑞 + 𝛿) 𝑞(𝑛 + 𝛿) ( ) ( ) 𝑛(𝓁𝑞 + 𝛿) 𝑛(𝓁𝑞 + 𝛿)
Note: 𝑛 : number of participating parties; 𝑞 : data size of each participant; 𝓁 : number of repeated sequences; 𝛿 : number of decoy positions; 𝑄 : number of initial qubits prepared by SA-OQKD; 𝐵 : number of hash functions in the Bloom filter; 𝑁 : lattice dimension of LWE; 𝑑𝑘𝑠 denotes a small constant associated with the KeySwitch technique; 𝑆 : size of the server-side dataset; and 𝜆 : security parameter.
time, our construction relies only on single-photon rotations in the quantum phase and a lightweight OLE-based classical post-processing step. This differs from the QHE-based design of [WLS+ 26], whose encrypted quantum evaluation introduces Clifford gates. More importantly, our protocol explicitly [ ⋂ realizes car] dinality testing: it outputs the predicate 𝟏 || 𝑛𝑖=1 𝑋𝑖 || ≥ 𝜏 , rather than first exposing the exact intersection cardinality |⋂𝑛 𝑋 | and then comparing it with 𝜏. This distinction | 𝑖=1 𝑖 | is essential for TPSI specially under the TP setting and makes our functionality consistent with the classical TPSI paradigm represented by [BMR+ 21, ZCL21, HZT+ 24]. By contrast, in the existing quantum TPSI protocols [MSD+ 24, LZY+ 26, WLS+ 26], TP remains responsible not only for measurement, but also for interpreting the measurement outcomes and determining the intersection-related result. Our protocol separates these roles: TP is reduced to a blinded measurement party, while the threshold decision is delegated to the classical subprotocol Π𝜏CT .
7. Conclusion Conclusion. This paper presented a rotation based MPQTPSI protocol with explicit cardinality testing. Unlike existing quantum TPSI constructions that rely on TP to recover the intersection cardinality before threshold comparison, our protocol decouples TP’s measurement role from the threshold-testing functionality. By combining hiddenlabel quantum measurements, participant-side correlated rotations, and a classical OLE-assisted testing] procedure, the [⋂ proposed protocol realizes 𝟏 || 𝑛𝑖=1 𝑋𝑖 || ≥ 𝜏 without exposing the exact intersection cardinality. An additional advantage of the hidden-label testing framework is its flexibility. Since the final decision is reduced to a classical predicate over secret-shared consistency statistics, the present threshold rule can be naturally extended to richer policies, such as weighted threshold, ratiobased threshold [BMR+ 21], or over-threshold [ABK25] without changing the core quantum interaction structure.
Zixian Gong et al.: Preprint submitted to Elsevier
Future Work. (1) it is meaningful to extend the current semi-honest TP model to stronger adversarial settings, including malicious TP behavior and possible collusion between TP and participants; (2) it is worth investigating whether the quantum communication and computation costs can be made threshold-dependent, analogous to classical TPSI designs such as [GS19], rather than scaling with the full encoded domain length; (3) although current quantum PSI-type protocols do not require participants to hold sets of equal cardinality, they typically encode inputs into equallength indicator vectors, which still reflects a balancedPSI style representation. Developing genuinely unbalanced quantum PSI may further reduce quantum resources and improve practicality in highly skewed data regimes.
References [ABC+ 20] N. Angelou, A. Benaissa, B. Cebere, W. Clark, A. J. Hall, M. A. Hoeh, D. Liu, P. Papadopoulos, R. Roehm, R. Sandmann, P. Schoppmann, and T. Titcombe. Asymmetric private set intersection with applications to contact tracing and private vertical federated machine learning. In NeurIPS 2020 Workshop on Privacy Preserving Machine Learning (PPML ’20), Nov 2020. [ABK25] Onur Eren Arpaci, Raouf Boutaba, and Florian Kerschbaum. Over-threshold multiparty private set intersection for collaborative network intrusion detection. ArXiv, abs/2510.12045, 2025. [BB14] Charles H. Bennett and Gilles Brassard. Quantum cryptography: Public key distribution and coin tossing. Theor. Comput. Sci., 560:7–11, 2014. [BCG+ 18] Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai. Compressing vector OLE. In ACM CCS, pages 896–912, 2018. [BEPU+ 22] Carsten Baum, Daniel Escudero, Alberto Pedrouzo-Ulloa, Peter Scholl, and Juan Ramón Troncoso-Pastoriza. Efficient protocols for oblivious linear function evaluation from ringLWE. J. Comput. Secur., 30(1):39–78, 2022. [BMR+ 21] Saikrishna Badrinarayanan, Peihan Miao, Srinivasan Raghuraman, and Peter Rindal. Multi-party threshold private set intersection with sublinear communication. In Public-Key Cryptography – PKC 2021, pages 349–379, 2021.
Page 10 of 11
QTPSI [CB98] Anthony Chefles and Stephen M. Barnett. Quantum state separation, unambiguous discrimination and exact cloning. Journal of Physics A: Mathematical and General, 31(50):10097– 10103, 1998. [DD15] Sumit Kumar Debnath and Ratna Dutta. Secure and efficient private set intersection cardinality using bloom filter. In Information Security – ISC 2015, pages 209–226, 2015. [FNP04] Michael J. Freedman, Kobbi Nissim, and Benny Pinkas. Efficient private matching and set intersection. In Advances in Cryptology – EUROCRYPT 2004, pages 1–19, 2004. [FYC+ 15] Yao Fu, Hua-Lei Yin, Teng-Yun Chen, and Zeng-Bing Chen. Long-distance measurement-device-independent multiparty quantum communication. Phys. Rev. Lett., 114(9):090501, 2015. [GS19] Satrajit Ghosh and Mark Simkin. The communication complexity of threshold private set intersection. In Advances in Cryptology – CRYPTO 2019, pages 3–29, 2019. [GS23] Satrajit Ghosh and Mark Simkin. Threshold private set intersection with better communication complexity. In Public-Key Cryptography – PKC 2023, pages 251–272, 2023. [HB05] Ulrike Herzog and János A. Bergou. Optimum unambiguous discrimination of two mixed quantum states. Phys. Rev. A, 71:050301, 2005. [HEK12] Yan Huang, David Evans, and Jonathan Katz. Private set intersection: Are garbled circuits better than custom protocols? In NDSS, 2012. [HOS17] Per Hallgren, Claudio Orlandi, and Andrei Sabelfeld. PrivatePool: Privacy-preserving ridesharing. In IEEE Computer Security Foundations Symposium – CSF 2017, pages 276– 291, 2017. [HZT+ 24] Jingwei Hu, Yongjun Zhao, Benjamin Hong Meng Tan, Khin Mi Mi Aung, and Huaxiong Wang. Enabling threshold functionality for private set intersection protocols in cloud computing. Trans. Info. For. Sec., 19:6184–6196, 2024. [HZZ24] Xi Huang, Wenfang Zhang, and Shibin Zhang. Quantum multi-party private set intersection using single photons. Physica A: Statistical Mechanics and its Applications, 649:129974, 2024. [IKN+ 17] Mihaela Ion, Ben Kreuter, Erhan Nergiz, Sarvar Patel, Shobhit Saxena, Karn Seth, David Shanahan, and Moti Yung. Private intersection-sum protocol with applications to attributing aggregate ad conversions. Cryptology ePrint Archive, Paper 2017/738, 2017. [LZY+ 26] Xiang-Rui Li, Yi-Hua Zhou, Yu-Guang Yang, and Wei-Min Shi. A multiparty quantum threshold private set intersection and union cardinality protocol based only on single-particle states. Chinese Journal of Physics, 101:617–633, 2026. [MD23] Tapaswini Mohanty and Sumit Kumar Debnath. An information-theoretically secure quantum multiparty private set intersection. Journal of Information Security and Applications, 78:103623, 2023. [Mea86] Catherine A. Meadows. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. IEEE S&P, pages 134–134, 1986. [MSD+ 24] Tapaswini Mohanty, Vikas Srivastava, Sumit Kumar Debnath, Ashok Kumar Das, and Biplab Sikdar. Quantum secure threshold private set intersection protocol for IoT-enabled privacy-preserving ride-sharing application. IEEE Internet of Things Journal, 11(1):1761–1772, 2024. [NP99] Moni Naor and Benny Pinkas. Oblivious transfer and polynomial evaluation. In 31st STOC, pages 245–254, 1999. [PHG+ 21] Massimiliano Proietti, Joseph Ho, Federico Grasselli, Peter Barrow, Mehul Malik, and Alessandro Fedrizzi. Experimental quantum conference key agreement. Science Advances, 7(23):eabe0395, 2021. [RS21] Peter Rindal and Phillipp Schoppmann. VOLE-PSI: Fast OPRF and circuit-PSI from vector-OLE. In Advances in Cryptology – EUROCRYPT 2021, pages 901–930, 2021.
Zixian Gong et al.: Preprint submitted to Elsevier
[SCW+ 18] Liyan Shen, Xiaojun Chen, Dakui Wang, Binxing Fang, and Ye Dong. Efficient and private set intersection of human genomes. In IEEE International Conference on Bioinformatics and Biomedicine (BIBM), pages 761–764, 2018. [Sho97] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5):1484–1509, 1997. [SMZ+ 16] Runhua Shi, Yi Mu, Hong Zhong, Jie Cui, and Shun Zhang. An efficient quantum scheme for private set intersection. Quantum Information Processing, 15(1):363–371, 2016. [UCK+ 21] Erkam Uzun, Simon P. Chung, Vladimir Kolesnikov, Alexandra Boldyreva, and Wenke Lee. Fuzzy labeled private set intersection with applications to private Real-Time biometric search. In USENIX Security, pages 911–928, 2021. [WLS+ 26] Tianyin Wang, Shuang Li, Shuaijia Song, Jiao Du, Chunyan Wei, and Xiaoqiu Cai. Flexible threshold private set intersection based on quantum homomorphic encryption. IEEE Internet of Things Journal, 13(6):12220–12227, 2026. [WYK+ 21] Chenkai Weng, Kang Yang, Jonathan Katz, and Xiao Wang. Wolverine: Fast, scalable, and communication-efficient zeroknowledge proofs for boolean and arithmetic circuits. In IEEE S&P, pages 1074–1091, 2021. [Yao86] Andrew Chi-Chih Yao. How to generate and exchange secrets. In FOCS’86, page 162–167, 1986. [ZC18] Yongjun Zhao and Sherman S. M. Chow. Can you find the one for me? In Proceedings of the 2018 Workshop on Privacy in the Electronic Society, pages 54–65, 2018. [ZCL21] En Zhang, Jian Chang, and Yu Li. Efficient threshold private set intersection. IEEE Access, 9:6560–6570, 2021. [ZLS+ 20] Cai Zhang, Yinxiang Long, Zhiwei Sun, Qin Li, and Qiong Huang. Three-party quantum private computation of cardinalities of set intersection and union based on GHZ states. Scientific Reports, 10:22246, 2020.
Page 11 of 11