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

Verifiable and Collusion-Resistant Multi-Party Quantum Private Set Operations Zixian Gonga,∗ , Kun Tiana , Yi Zhanga and Fengxia Liub a School of Mathematics, Renmin University of China, Beijing, 100872, P. R. China

arXiv:2606.27994v1 [quant-ph] 26 Jun 2026

b Great Bay University, DongGuan, 523808, P. R. China

ARTICLE INFO

ABSTRACT

Keywords: Quantum private set intersection Verifiable quantum homomorphic encryption Threshold fully homorphic encryption Collusion resistance Verifiable computation

Private set intersection (PSI) and, more broadly, private set operations (PSO) are fundamental primitives for secure multiparty computation (SMC), enabling participants to jointly compute set relations while revealing no information beyond the prescribed output. As quantum technologies advance, PSI have correspondingly evolved toward quantum secure phase. Existing quantum PSI (QPSI) solutions are limited in their threat models and collusion behavior between third party (TP) and participants. In this work, we present a multi-party QPSI (MP-QPSI) protocol that integrates verifiable quantum fully homomorphic encryption (vQFHE) as the verifiable outsourced quantum-evaluation layer and threshold fully homomorphic encryption (TFHE) as the threshold key-management mechanism. We instantiate the intersection computation via a 𝐶 𝖠𝖭𝖣 circuit accompanied by simulations on IBM Quantum Platform. We analyze correctness and participant privacy against TP, external eavesdroppers, and collusive behaviors, and we further prove verifiability against a malicious TP under the semantic security model. Finally, we present a modular framework perspective with several realizations, show how to extend the construction to quantum private set union (QPSU) via opencontrolled operations. Compared with prior schemes, our protocol provides flexible set operations and stronger resilience under the TP model, including TP-participant collusion, thereby offering enhanced security and broader applicability.

1. Introduction Private set intersection (PSI) is an important branch of secure multiparty computation (SMC), enabling parties to learn the intersection of their private sets while revealing no additional information beyond the intersection [Mea86, FNP04]. Owing to its strong privacy guarantees, PSI has become a key building block in a broad range of privacypreserving applications, such as vertical federated learning [ABC+ 20], contact discovery [DRR+ 18], genomic data analysis [SCW+ 18]. As privacy requirements evolve, this primitive has been extended into a family of variants. Representative examples include private set union (PSU) [KRT+ 19], which enables parties to compute the union of private sets, as well as the cardinality-only variants PSI-CA and PSU-CA [DCGT12], which reveal only the size of the intersection or union. Collectively, these and other functionality-oriented extensions for privacy-preserving set computation are often referred to as private set operations (PSO) [KS05]. These privacypreserving set computation protocols are primarily instantiated via three mainstream cryptographic paradigms: homomorphic encryption (HE) [CLR17], oblivious transfer (OT) and OT-extension, and oblivious pseudorandom functions (OPRF) [PSZ14]. More recently, PSI constructions based on oblivious key-value stores (OKVS) have also gained significant traction [PRT+ 20]. With the rapid progress of quantum technologies and advent of Shor’s algorithm [Sho95], many cryptographic schemes based on number theoretical hard ∗ Corresponding author

ArtoriasGong@ruc.edu.cn (F. Liu)

ORCID (s): 0009-0005-7059-5040 (Z. Gong)

Zixian Gong et al.: Preprint submitted to Elsevier

problems have become vulnerable. Beyond ongoing efforts on post-quantum cryptography (PQC) as an interim solution, a growing line of work turns to quantum cryptography and leverages properties of quantum mechanics to design quantum PSI (QPSI) protocols. In 2015, [SMZ+ 15] proposed the first two-party QPSI protocol. However, [CGC16] later pointed out that it suffers from a fairness issue, and suggested introducing a trusted third party to remedy this limitation. Building on GHZ states, [ZLS+ 20] extended the setting to three-parties and realized PSI-CA and PSU-CA under TP formulation, their protocol further provides resistance against collusion between the two participating parties. Subsequently, [MD23] used single photons and unitary operations to extend QPSI to the multi-party setting (MP-QPSI), but their security guarantee only tolerates corruption of at most one participant, which is overly restrictive in large-scale setting. More recently, [HZZ24] achieved MP-QPSI via rotation operations, and under the TP formulation, they addressed collusion among participants. Among all the proposed QPSO schemes, some of them have deception-sensitive techniques against a semihonest TP [SMZ+ 15, HZZ24], their security guarantees typically rely on the assumption that the TP can not collude with any participant. This lack of TP-client collusion resistance constitutes a central motivation of our work. To address it, we turn to another key cryptographic primitive that has advanced alongside quantum technologies, the fully HE (FHE). After the early conceptual proposal [RAD78] and the breakthrough construction of FHE [Gen09], with the extensive follow-up research and implementation in the classical setting, researchers naturally began to ask whether one could Page 1 of 14

QPSO

encrypt quantum data while still allowing a server to perform arbitrary quantum computations over the ciphertext. QHE was proposed firstly in 2014 [YPDF14]. In 2015, [BJ15] introduced a quantum HE (QHE) scheme that the quantum information is encrypted via the quantum one-time pad (QOTP), while the corresponding QOTP keys are encrypted under a classical FHE scheme, enabling the TP to carry out quantum evaluation without learning the underlying plaintext. Because non-Clifford gates (in particular, the 𝖳 gate) induce correction terms that depend nonlinearly on the QOTP masks and thus cannot be captured by Pauli X∕Z masks alone, [DSS16] used the garden-hose model [BFS+ 13] to construct quantum gadgets to remove the additional corrections. Although a variety of QHE constructions have since been developed, unlike classical HE, they did not systematically incorporate verifiability of evaluation results until the introduction of verifiable QFHE (vQFHE) in [ADS+ 17]. Contribution. In the QHE setting, the TP or server is typically assumed to possess strong quantum capabilities and can therefore execute relatively complex quantum circuits, and aims to enable such quantum computation while preventing the TP from learning any private information, it aligns naturally with the design objectives of QPSI. Moreover, vQFHE can verify the correctness of the evaluated results. Building on this property, our contributions are as follows: • We combine Threshold FHE (TFHE) [AJLA+ 12, BGG+ 18] with the vQFHE construction TrapTP from [ADS+ 17] to extend it to a multi-party setting. Specifically, in a model consisting of a powerful quantum TP, 𝑛 data-holding participants, and a trusted authority (TA) responsible for key generation, we instantiate the intersection computation via a 𝐶 𝖠𝖭𝖣 circuit and simulated it on the IBM Quantum platform and thereby realize a MP-QPSI protocol. • By leveraging the verifiability of vQFHE, our protocol achieves a key distinguishing property compared to existing QPSI schemes: it can use the intermediate classical information to efficiently detect whether the TP deviates from the prescribed target circuit, thereby ensuring the correctness of the output and mitigating malicious behavior by the TP. • Owing to TFHE’s threshold key sharing, our protocol our protocol provides collusion resistance that is absent from prior QPSI: as long as the number of corrupted parties is below the threshold 𝑛𝑡 , neither collusion among participants nor collusion between the participants and the TP can recover the secret key or learn the private inputs of honest parties including the final intersection information. Moreover, the structure improves availability in multi-party setting, allowing decryption and result recovery to proceed at least 𝑛𝑡 parties remain online, thereby tolerating temporary participants offline. • We further demonstrate the extensibility of our construction: by replacing specific modules, the protocol can be adapted to realize different functionalities, Zixian Gong et al.: Preprint submitted to Elsevier

such as reducing circuit complexity and enabling MPQPSU via open-controlled operations. Outline. The remainder of this paper is organized as follows. Section 2 provides the necessary preliminaries. The proposed MP-QPSI protocol is presented in detail in Section 3. Security analysis and proofs are given in Section 4. A framework perspective and performance comparisons with related schemes are provided in Sections 5 and 6, respectively. Finally, Section 7 will give a conclusion.

2. Preliminaries 2.1. Threshold FHE & Secret Sharing Definition 1 (TFHE). [AJLA+ 12] For a set of 𝑛 parties {𝑃𝑖 }𝑖∈[𝑛] with threshold 𝑡 ≤ 𝑛. A 𝑡-out-of-𝑛 𝖳𝖥𝖧𝖤 scheme is a 4-tuple of algorithms (𝖳𝖥𝖧𝖤.𝖪𝖾𝗒𝖦𝖾𝗇, 𝖳𝖥𝖧𝖤.𝖤𝗇𝖼, 𝖳𝖥𝖧𝖤.𝖤𝗏 𝖺𝗅, 𝖳𝖥𝖧𝖤.𝖣𝖾𝖼) defined as follows: • 𝖳𝖥𝖧𝖤.𝖪𝖾𝗒𝖦𝖾𝗇(1𝜅 ): Take as input the security parameter 𝜅, each party 𝑃𝑖 obtains a tubple of keys including the common public key 𝑝𝑘, evaluation key 𝑒𝑣𝑘 and a private share 𝑠𝑘𝑖 of the secret key 𝑠𝑘. • 𝖳𝖥𝖧𝖤.𝖤𝗇𝖼𝑝𝑘 (𝜇): Input the public key 𝑝𝑘 and a plaintext in message space 𝜇 ∈ , output a ciphertext 𝑐. • 𝖳𝖥𝖧𝖤.𝖤𝗏𝖺𝗅𝑒𝑣𝑘 (𝑓 , 𝑐1 , … , 𝑐𝓁 ): For some ciphertexts 𝑐1 , … , 𝑐𝓁 and a bounded boolean circuit 𝑓 , this deterministic poly-time algorithm uses 𝑒𝑣𝑘 and output an evaluated ciphertext 𝑐 ′ . • 𝖳𝖥𝖧𝖤.𝖣𝖾𝖼{𝑠𝑘𝑖 }𝑖∈𝑆 (𝑐 ′ ): Given an evaluated ciphertext 𝑐 ′ and the {𝑠𝑘𝑖 } of any subset 𝑆 ⊆ [𝑛] with |𝑆| ≥ 𝑡, the parties in 𝑆 jointly decrypt 𝑐 ′ to obtain a plaintext 𝑢′ = 𝑓 (𝑢1 , … , 𝑢𝓁 ). Definition 2 (TFHE Evaluation Correctness). For a 𝑡out-of-𝑛 𝖳𝖥𝖧𝖤 scheme as in Definition 1. We say that it satisfies evaluation correctness if for all security parameters 𝜅, all circuits 𝑓 in the supported class, and every subset 𝑆 ⊆ [𝑛] with |𝑆| ≥ 𝑡. Let (𝑝𝑘, {𝑠𝑘𝑖 }𝑖∈[𝑛] ) ← 𝖳𝖥𝖧𝖤.𝖪𝖾𝗒𝖦𝖾𝗇(1𝜅 ) and 𝑐𝑖 ← 𝖳𝖥𝖧𝖤.𝖤𝗇𝖼𝑝𝑘 (𝜇𝑖 ) (𝑖 ∈ [𝓁]), 𝑐 ′ ← 𝖳𝖥𝖧𝖤.𝖤𝗏𝖺𝗅𝑒𝑣𝑘 (𝑓 , 𝑐1 , … , 𝑐𝓁 ), the following holds: [ ] Pr 𝖳𝖥𝖧𝖤.𝖣𝖾𝖼{𝑠𝑘𝑖 }𝑖∈𝑆 (𝑐 ′ ) = 𝑓 (𝜇1 , … , 𝜇𝓁 ) = 1−𝗇𝖾𝗀𝗅(𝜅). Definition 3 (Threshold SS). [BGG+ 18] Let 𝑃 = {𝑃𝑖 }𝑖∈[𝑛] be a set of parties and 𝑡 ≤ 𝑛. A (𝑡, 𝑛)-threshold secret sharing scheme for secret space  is a pair of algorithms 𝖲𝖲 = (𝖲𝖲.𝖲𝗁𝖺𝗋𝖾, 𝖲𝖲.𝖢𝗈𝗆𝖻𝗂𝗇𝖾): • 𝖲𝖲.𝖲𝗁𝖺𝗋𝖾(𝑘) → (𝑠1 , … , 𝑠𝑛 ): On input a secret 𝑘 ∈  outputs a share 𝑠𝑖 for each party 𝑃𝑖 . • 𝖲𝖲.𝖢𝗈𝗆𝖻𝗂𝗇𝖾({𝑠𝑖 }𝑖∈𝑆 ) → 𝑘: On input the shares of a subset 𝑆 ⊆ [𝑛] for |𝑆| ≥ 𝑡 outputs either a secret 𝑘 ∈  or ⟂. Definition 4 (SS Correctness). A (𝑡, 𝑛)-threshold secret sharing scheme in Definition 3 is correct if for all 𝑘 ∈  and all 𝑆 ⊆ [𝑛] with |𝑆| ≥ 𝑡, letting (𝑠1 , … , 𝑠𝑛 ) ← 𝖲𝖲.𝖲𝗁𝖺𝗋𝖾(𝑘) we have [ ] Pr 𝖲𝖲.𝖢𝗈𝗆𝖻𝗂𝗇𝖾({𝑠𝑖 }𝑖∈𝑆 ) = 𝑘 = 1. Page 2 of 14

QPSO

Definition 5 (SS Privacy). [Sha79] A (𝑡, 𝑛)-threshold secret sharing scheme has 𝑡-privacy if for all 𝑆 ⊆ [𝑛] with |𝑆| ≤ 𝑡 − 1, any 𝑘0 , 𝑘1 ∈ , and independent randomness, if (𝑠𝑏,1 , … , 𝑠𝑏,𝑛 ) ← 𝖲𝖲.𝖲𝗁𝖺𝗋𝖾(𝑘𝑏 ) for 𝑏 ∈ {0, 1}, then {𝑠0,𝑖 }𝑖∈𝑆 ≈ {𝑠1,𝑖 }𝑖∈𝑆 . Lemma 1. For a 𝖳𝖥𝖧𝖤 scheme whose secret key 𝑠𝑘 is shared by a (𝑡, 𝑛)-𝖲𝖲 scheme, the following hold: • Any group of 𝑡 or more out of the 𝑛 participants can collectively reconstruct the private key 𝑠𝑘; • Any group of at most 𝑡 − 1 participants cannot reconstruct the private key 𝑠𝑘; • Ciphertexts under 𝖳𝖥𝖧𝖤 can be homomorphically evaluated via 𝖳𝖥𝖧𝖤.𝖤𝗏𝖺𝗅; • Any ciphertext can be correctly decrypted by any qualified set 𝑆 with |𝑆| ≥ 𝑡.

2.2. QHE [BJ15] Definition 6 (QHE). Let 𝜅 be the security parameter. A quantum homomorphic encryption scheme 𝖰𝖧𝖤 for message space  and cipherspace  is a 4-tuple of quantum polynomial-time (QPT) algorithms (𝖰𝖧𝖤.𝖪𝖾𝗒𝖦𝖾𝗇, 𝖰𝖧𝖤.𝖤𝗇𝖼, 𝖰𝖧𝖤.𝖤𝗏𝖺𝗅, 𝖰𝖧𝖤.𝖣𝖾𝖼) defined as follows: • 𝖰𝖧𝖤.𝖪𝖾𝗒𝖦𝖾𝗇(1𝜅 ): On input 1𝜅 outputs a classical public key 𝑝𝑘, a classical secret key 𝑠𝑘, and a quantum evaluation key 𝜌𝖾𝗏𝗄 ∈ 𝐷(𝖾𝗏𝗄 ). • 𝖰𝖧𝖤.𝖤𝗇𝖼𝑝𝑘 (𝜌): Through 𝑝𝑘, this quantum channel maps a message state 𝜌 ∈ 𝐷() to a ciphertext state 𝜎 ∈ 𝐷(). • 𝖰𝖧𝖤.𝖤𝗏𝖺𝗅𝖢 𝜌 (𝜎): For every quantum circuit 𝖢 with 𝑒𝑣𝑘

Φ𝖢 ∶ 𝐷(⊗𝑛 ) → 𝐷(⊗𝑚 ), 𝖰𝖧𝖤.𝖤𝗏𝖺𝗅𝖢 𝜌𝑒𝑣𝑘 uses the evaluation key 𝜌𝖾𝗏𝗄 and maps 𝑛 ciphertext registers 𝜎 to 𝑚 ciphertext registers 𝜎 ′ as 𝐷(𝖾𝗏𝗄 ⊗  ⊗𝑛 ) → 𝐷( ′⊗𝑚 ). • 𝖰𝖧𝖤.𝖣𝖾𝖼𝑠𝑘 (𝜎 ′ ): For every 𝑠𝑘, the quantum channel 𝖰𝖧𝖤.𝖣𝖾𝖼𝑠𝑘 maps the ciphertext state 𝜎 ′ in 𝐷( ′ ) back to a plaintext state 𝜌′ in 𝐷(). Definition 7 (QHE Evaluation Correctness). A 𝖰𝖧𝖤 scheme is correctness if for every efficient quantum circuit 𝖢 with induced channel Φ𝖢 and every input state 𝜌 ∈ 𝐷(⊗𝑛 ), ( ) ‖ ‖ 𝖰𝖧𝖤.𝖤𝗏𝖺𝗅𝖢 (𝖰𝖧𝖤.𝖤𝗇𝖼⊗𝑛 (𝜌)) −Φ𝖢 (𝜌)‖ ‖𝖰𝖧𝖤.𝖣𝖾𝖼⊗𝑚 𝜌 𝑠𝑘 𝑝𝑘 𝖾𝗏𝗄 ‖ ‖tr is at most 𝗇𝖾𝗀𝗅(𝜅).

2.3. vQFHE [ADS+ 17] Definition 8 (vQFHE). Let 𝜅 be the security parameter. A 𝗏𝖰𝖥𝖧𝖤 scheme is a set of QPT algorithms (𝗏𝖰𝖥𝖧𝖤.𝖪𝖾𝗒𝖦𝖾𝗇, 𝗏𝖰𝖥𝖧𝖤.𝖤𝗇𝖼, 𝗏𝖰𝖥𝖧𝖤.𝖤𝗏𝖺𝗅, 𝗏𝖰𝖥𝖧𝖤.𝖵𝖾𝗋𝖣𝖾𝖼) defined as follows: • 𝗏𝖰𝖥𝖧𝖤.𝖪𝖾𝗒𝖦𝖾𝗇(1𝜅 ) and 𝗏𝖰𝖥𝖧𝖤.𝖤𝗇𝖼

𝑝𝑘 (𝜌) have the same syntax as 𝖰𝖧𝖤.𝖪𝖾𝗒𝖦𝖾𝗇 and 𝖰𝖧𝖤.𝖤𝗇𝖼𝑝𝑘 in Definition 6.

Zixian Gong et al.: Preprint submitted to Elsevier

• 𝗏𝖰𝖥𝖧𝖤.𝖤𝗏𝖺𝗅𝖢 𝜌 (𝜎): On input a quantum circuit 𝖢, 𝖾𝗏𝗄

𝗏𝖰𝖧𝖤.𝖤𝗏𝖺𝗅𝖢 𝜌𝑒𝑣𝑘 uses the evaluation key 𝜌𝖾𝗏𝗄 and maps 𝜎 to 𝜎 ′ with an extra classical computation 𝑙𝑜𝑔 output as 𝐷(𝖾𝗏𝗄 ⊗  ⊗𝑛 ) → 𝐷( ⊗  ′⊗𝑚 ). • 𝗏𝖰𝖥𝖧𝖤.𝖵𝖾𝗋𝖣𝖾𝖼𝑠𝑘 (𝖢, 𝑙𝑜𝑔, 𝜎 ′ ): Using the secret key 𝑠𝑘, a circuit 𝖢, a computation 𝑙𝑜𝑔, and a ciphertext state 𝜎 ′ , the algorithm outputs a pair (𝜌′ , 𝑏), where 𝜌′ is the decrypted state and 𝑏 ∈ {𝖺𝖼𝖼, 𝗋𝖾𝗃} is the verification result. Definition 9 (vQFHE Evaluation Correctness). A 𝗏𝖰𝖥𝖧𝖤 scheme is correctness if for every security parameter 𝜅, every key triple (𝑝𝑘, 𝑠𝑘, 𝜌𝖾𝗏𝗄 ) ← 𝗏𝖰𝖥𝖧𝖤.𝖪𝖾𝗒𝖦𝖾𝗇(1𝜅 ) and every poly-size quantum circuit 𝖢 acting on plaintext, the channel induced by honest execution satisfies 𝖢 𝗏𝖰𝖥𝖧𝖤.𝖵𝖾𝗋𝖣𝖾𝖼𝖢 𝑠𝑘 ◦𝗏𝖰𝖥𝖧𝖤.𝖤𝗏𝖺𝗅𝜌 ◦𝗏𝖰𝖥𝖧𝖤.𝖤𝗇𝖼𝑝𝑘 = Φ𝖢 𝖾𝗏𝗄

with overwhelming probability 1 − 𝗇𝖾𝗀𝗅(𝜅). Definition 10 (𝜅-SEM-VER). As to a 𝗏𝖰𝖥𝖧𝖤 scheme, for any QPT adversary  which manipulates a ciphertext (and side info),  outputs a modified ciphertext together with a circuit description 𝖢 and a computation 𝑙𝑜𝑔, the real channel Φ is defined as follows: 𝖱𝖾𝖺𝗅 ∶= 𝗏𝖰𝖥𝖧𝖤.𝖵𝖾𝗋𝖣𝖾𝖼𝖢 𝑠𝑘 ◦  ◦ 𝗏𝖰𝖥𝖧𝖤.𝖤𝗇𝖼𝑝𝑘 . For any QPT simulator  that never sees a ciphertext but only declares a circuit and an 𝖺𝖼𝖼∕𝗋𝖾𝗃 decision, this defines the ideal channel Φ : 𝖨𝖽𝖾𝖺𝗅 ∶= 𝖼𝗍𝗋𝗅-⊘ ◦ Φ𝖢 ◦ , where Φ𝖢 is the channel implemented on the plaintext directly by the circuit 𝖢, and 𝖼𝗍𝗋𝗅-⊘ replaces the output by a fixed state whenever the decision is "𝗋𝖾𝗃". The 𝗏𝖰𝖥𝖧𝖤 is semantically 𝜅-verifiable if for every QPT adversary , there exists a QPT simulator  such that for all QPT message generators  and distinguishers , ] [ ]| | [ |Pr (𝖱𝖾𝖺𝗅 ((𝜌𝖾𝗏𝗄 ))) = 1 −Pr (𝖨𝖽𝖾𝖺𝗅 ((𝜌𝖾𝗏𝗄 ))) = 1 | | | with negligible probability 𝗇𝖾𝗀𝗅(𝜅).

2.4. QOTP [AMT+ 00, BGS13] Definition 11 (QOTP). For a single-qubit state 𝜌 and a classical key (𝑎, 𝑏) ∈ {0, 1}2 , the quantum one-time pad masks 𝜌 by Pauli operators QOTP𝑎,𝑏 (𝜌) = 𝖷𝑎 𝖹𝑏 𝜌 𝖹𝑏 𝖷𝑎 . Using the same key (𝑎, 𝑏) again removes the mask, so the plaintext is easily recovered. If (𝑎, 𝑏) is chosen uniformly at random, then for all 𝜌, 𝕀 1 ∑ 𝖷𝑎 𝖹𝑏 𝜌 𝖹𝑏 𝖷𝑎 = 2 , 4 𝑎,𝑏∈{0,1} 2 This property is used in the 𝖰𝖧𝖤.𝖤𝗇𝖼 that the encrypted state is maximally mixed from the adversary’s point of view. Page 3 of 14

QPSO

2.5. MAC [BW16] Definition 12 (MAC). Let  be a message space and  be a tag space. A MAC is a triple of algorithms 𝖬𝖠𝖢 = (𝖬𝖠𝖢.𝖪𝖾𝗒𝖦𝖾𝗇, 𝖬𝖠𝖢.𝖲𝗂𝗀𝗇, 𝖬𝖠𝖢.𝖵𝖾𝗋) defined as follows: • 𝖬𝖠𝖢.𝖪𝖾𝗒𝖦𝖾𝗇(1𝜅 ): Outputs a MAC key 𝑘. • 𝖬𝖠𝖢.𝖲𝗂𝗀𝗇𝑘 (𝑚): Using the MAC key 𝑘, for a message 𝑚 ∈  returns a tag pair (𝑚, 𝜏) where 𝜏 ∈  . • 𝖬𝖠𝖢.𝖵𝖾𝗋𝑘 (𝑚, 𝜏): For (𝑚, 𝜏) ∈  ×  returns a bit 𝑏 ∈ {0, 1} indicating whether 𝜏 is a valid tag on 𝑚 under key 𝑘. Definition 13 (MAC Correctness). For a 𝖬𝖠𝖢 scheme as defined in Definition 12. We say that 𝖬𝖠𝖢 satisfies correctness if for every security parameter 𝜅 and every message 𝑚 ∈ , 𝑘 ← 𝖬𝖠𝖢.𝖪𝖾𝗒𝖦𝖾𝗇(1𝜅 ) and 𝜏 ← 𝖬𝖠𝖢.𝖲𝗂𝗀𝗇𝑘 (𝑚): [ ] Pr 𝑏 = 1 ∶ 𝑏 ← 𝖬𝖠𝖢.𝖵𝖾𝗋𝑘 (𝑚, 𝜏) = 1. Definition 14 (MAC Security). 𝖬𝖠𝖢 is unconditional onetime secure if for every probabilistic algorithms : [ ] $ Pr 𝖬𝖠𝖢.𝖵𝖾𝗋𝑘 (𝑚, 𝜏) = 1 ∶ 𝑘 ←←←← {0, 1}𝜅 , (𝑚, 𝜏) ← (1𝜅 ) is negligible in a security parameter 𝜅. Definition 15 (MAC EUF-CMA Security). Let 𝖬𝖠𝖢 = (𝖬𝖠𝖢.𝖪𝖾𝗒𝖦𝖾𝗇, 𝖬𝖠𝖢.𝖲𝗂𝗀𝗇, 𝖬𝖠𝖢.𝖵𝖾𝗋) be a MAC for message space . Consider the following experiment with an adversary : Experiment 𝖤𝖴𝖥-𝖢𝖬𝖠 (𝜅) 𝖬𝖠𝖢 1. Sample 𝑘 ← 𝖬𝖠𝖢.𝖪𝖾𝗒𝖦𝖾𝗇(1𝜅 ). 2. Give  oracle access to 𝗌𝗂𝗀𝗇 (𝑚) = 𝖬𝖠𝖢.𝖲𝗂𝗀𝗇𝑘 (𝑚). Let 𝑄 be the set of messages queried to this oracle. 3. Eventually  outputs a pair (𝑚⋆ , 𝜏 ⋆ ). The experiment outputs 1 (“ wins”) iff 𝖬𝖠𝖢.𝖵𝖾𝗋𝑘 (𝑚⋆ , 𝜏 ⋆ ) = 1 and 𝑚⋆ ∉ 𝑄. We say that 𝖬𝖠𝖢 is existentially unforgeable under adaptive chosen-message attacks (EUF-CMA secure) if for every PPT adversary , [ ] Pr 𝖤𝖴𝖥-𝖢𝖬𝖠 (𝜅) = 1 ≤ 𝗇𝖾𝗀𝗅(𝜅). 𝖬𝖠𝖢

3. Proposed Protocol Protocol Overview. In this section we explain how TrapTPbased vQFHE, combined with a classical threshold FHE scheme, can be lifted to the multi-party setting and instantiated in our MP-QPSI protocol in Protocol 1. For ease of exposition, we first provide a high-level flowchart of the whole protocol in Fig. 1. As illustrated there, the protocol proceeds in four phases. From a capability perspective, we model the TP as a powerful quantum server capable of running large-scale quantum computations and the associated classical homomorphic updates. TA is assumed to have only moderate quantum resources, sufficient for preparing a small number of authenticated auxiliary tools for evaluation while Zixian Gong et al.: Preprint submitted to Elsevier

each participant 𝑃𝑖 is a lightweight client equipped with very limited quantum capability, only needed to execute a fixed shallow encryption circuit; all remaining operations on the participants’ side are purely classical. The concrete actions of TP, TA and the participants in each phase will be detailed in the following content. Preparation and KeyGen. In the preparation phase, only the TA is active. TA first initializes the classical TFHE scheme and derives the evaluation keys, which will later be used by TP to homomorphically update QOTP ciphertexts and sampling a permutation 𝜋 to hide the traps. Using the TrapTP GadgetGen algorithm [ADS+ 17] to prepare Tgate gadgets with MagicPool for non-clifford gates in the quantum circuits. TA also generates an auxiliary target block with QOTP mask and signs all classical information above with a fixed EUF-CMA secure MAC [AMR+ 20]. Finally, TA prepares the client-side classical keys by choosing the base encryption key 𝑝𝑘0 , SS.Share the final decryption key into shares {𝑠𝑘𝑡𝑖 }. For the whole protocol, we use ̃⋅ to denote the encryptions of both classical and quantum information. Encryption. In the encryption phase, all participants 𝑃𝑖 are active as depicted in Fig. 2. Following TrapTP [ADS+ 17], we fix a self-dual [[𝑚, 1, 𝑑]] CSS code (so that H and CNOT are transversal), which can correct 𝜅 = 𝑑𝑐 errors where 𝑑 = 2𝑑𝑐 +1 and block size 𝑚 = poly(𝑑) chosen sufficiently large. Each party 𝑃𝑖 first sets its private set 𝑖 into a uniform-length quantum sequence 𝑖𝑄 according to a common ordering of the universe. For every logical qubit, 𝑃𝑖 applies CSS encoding, appends 𝑚 |0⟩-traps and 𝑚 |+⟩-traps, and hides the trap positions using the permutation 𝜋 (in principle, each party could use its own permutation 𝜋𝑖 , at the cost of a more involved classical homomorphic update at TP). The resulting 3𝑚-qubit block is then masked by QOTP, the corresponding QOTP keys are encrypted and MAC-signed using the local key 𝑘𝑖 , and all these ciphertexts are sent to TP. Homomorphic Evaluation. In this phase only TP is active. After receiving the authenticated evaluation key package 𝜌𝖾𝗏𝗄 from TA and the encrypted quantum inputs ̃𝑖𝑄 from all participants, TP homomorphically evaluates the fixed multiparty AND circuit 𝐶 𝖠𝖭𝖣 on these ciphertexts, following the TrapTP evaluation procedure [ADS+ 17] and the standard QHE paradigm [DSS16, BJ15]. The circuit is viewed as an alternating sequence of (𝓁) and non-Clifford 𝖳-layers 𝐶𝖳(𝓁) . For a Clifford layers 𝐶𝖢𝗅𝗂𝖿 𝖿 ′ ′ Clifford layer, the relation 𝖢 𝖷𝑎 𝖹𝑏 = 𝖷𝑎 𝖹𝑏 𝖢 allows TP to use 𝖧𝖤.𝖤𝗏𝖺𝗅 to homomorphically update the encrypted QOTP keys (̃ 𝑎, ̃ 𝑏) to (𝑎̃′ , 𝑏̃′ ) in the classical ciphertext space. When entering a non-Clifford 𝖳-layer, the relation 𝖳𝖷𝑎 𝖹𝑏 = 𝖯𝑎 𝖷𝑎 𝖹𝑏 𝖳 introduces an extra phase 𝖯𝑎 that depends on the secret key bit 𝑎. Since TP is not allowed to learn 𝑎 and only holds its encryption 𝑎̃, Thorough "Gadget" thought in [GC99], TP removes this unwanted phase by consuming

Page 4 of 14

QPSO Phase 1: Preparation and KeyGen

Phase 2: Encryption

Phase 3: Homomorphic Evaluation

Trust Authority (TA) send Parties the 𝒑𝒑𝒑𝒑, permutation 𝝅𝝅 for encryption, and the secret share ​of 𝒔𝒔𝒔𝒔𝒊𝒊 .

​Each party converts its private set into a quantum state sequence and encodes it using the CSS code with traps and the permutation 𝝅𝝅.

​TP uses the 𝒆𝒆𝒆𝒆𝒆𝒆 and gadget to homomorphically evaluate the circuit 𝑪𝑪𝑨𝑨𝑨𝑨𝑨𝑨 , homomorphically updating the encrypted QOTP keys and recording a transcript 𝒍𝒍𝒍𝒍𝒍𝒍.

Trust Authority (TA) send Third Party (TP) the 𝒆𝒆𝒆𝒆𝒆𝒆 and gadget of T-gate for homomorphic evaluation with message authentication code (MAC).

​Apply QOTP and send to TP the QOTP-encrypted quantum states, plus the QOTP keys encrypted with 𝒑𝒑𝒑𝒑 and MAC-signed.

key𝑖𝑖

TP

𝑃𝑃1 … 𝑃𝑃𝑛𝑛

𝜎𝜎� 1

𝑃𝑃1

���

𝜎𝜎� 𝑖𝑖 𝑃𝑃𝑖𝑖

𝜎𝜎� 𝑛𝑛

���

​All parties perform classical verification (MAC, Gate and Transcript checks) on the evaluation 𝒍𝒍𝒍𝒍𝒍𝒍 and run threshold decryption with 𝒔𝒔𝒔𝒔𝒊𝒊 to obtain and send TA the final QOTP keys. ​TA perform MAC check and remove the QOTP, undoes the permutation, checks the traps, 𝐂𝐂𝐂𝐂𝐂𝐂. 𝐃𝐃𝐃𝐃𝐃𝐃𝐃𝐃𝐃𝐃𝐃𝐃 the target and broadcasts intersection indicator 𝒃𝒃 to all parties.

​TP sends the output quantum state with 𝒍𝒍𝒍𝒍𝒍𝒍 to TA, and sends the updated encrypted QOTP keys with 𝒍𝒍𝒍𝒍𝒍𝒍 to all parties.

TA 𝜌𝜌𝑒𝑒𝑒𝑒𝑒𝑒

Phase 4: Verification and Decryption

𝜎𝜎� 𝑜𝑜𝑜𝑜𝑜𝑜 , 𝑙𝑙𝑙𝑙𝑙𝑙

QFHE. Eval 𝐶𝐶 AND

MAC Check

MAC Check Gate Check Transcript Check Accept

Remove QOTP trapCode QOTP 𝑜𝑜𝑜𝑜𝑜𝑜 Threshold Check Decryption

� 𝑜𝑜𝑜𝑜𝑜𝑜 QOTP 𝑙𝑙𝑙𝑙𝑙𝑙

𝑏𝑏

Recover

𝑃𝑃𝑛𝑛

Figure 1: Overview of the proposed MP-QPSI protocol. QOTP |σ1′ ⟩

|σ⟩ |0⟩

CSS Encode

.. .

X a1

|σ2′ ⟩

X a2

.. .

.. .

′ |σm ⟩

|0⟩

|0⟩

⊗m

⊗m

⊗ |+⟩

Z b2

X am

|0⟩

Z bm X am+1

Permutationπ

.. . |0⟩

Z b1

X a2m X a2m+1

.. .

.. . X a3m

σ e

Z b2m

|+⟩

|+⟩

Z bm+1

.. .

Z b2m+1

Z b3m

Traps

Figure 2: Quantum Circuit of Encryption.

one gadget generated by GadgetGen based on the gardenhose model [BFS+ 13]. At the same time, the corresponding classical QOTP-key ciphertexts are homomorphically recrypted, so that after processing all 𝑡 𝖳-gates the final keys are encrypted under the last-level public key 𝑝𝑘𝑡 . To maintain authentication security in the sense of [BW16], due to the introduction of the trap code, permutation and CSS structure, at each logical gate application it is necessary to perform appropriate logical measurements, and to use the evaluation key together with the encrypted permutation 𝜋̃ to homomorphically evaluate the corresponding 𝗎𝗇𝗉𝖾𝗋𝗆𝗎𝗍𝖾 and 𝗉𝖾𝗋𝗆𝗎𝗍𝖾 operations; we refer to [ADS+ 17, BGS13] for the detailed procedure and for a comparison of the underlying trap-code constructions. After 𝐶 𝖠𝖭𝖣 have been processed, the logical multi-party AND has been applied to the prepared auxiliary block 𝜎 ̃𝖺𝗎𝗑 , yielding a output block 𝜎 ̃𝗈𝗎𝗍 and the updated encrypted QOTP keys (̃ 𝑎 𝗈𝗎𝗍 , ̃ 𝑏𝗈𝗎𝗍 ) under 𝑝𝑘𝑡 . TP appends all intermediate classical information—the FHE evaluation transcript, the sequence of evaluated gates to a log that will later be used for verification. Finally, TP sends (̃ 𝑎 𝗈𝗎𝗍 , ̃ 𝑏𝗈𝗎𝗍 , log, 𝐶 𝖠𝖭𝖣 ) to Zixian Gong et al.: Preprint submitted to Elsevier

all participants 𝑃𝑖 , and, due to the no-cloning property of quantum information, forwards the unique quantum output block 𝜎 ̃𝗈𝗎𝗍 together with the same log to TA. Verification and Decryption. In the final phase, the parties jointly run a two-layer verification and decryption procedure, consisting of Classical.VerDec and Quantum.VerDec. On the classical side, all participants 𝑃𝑖 perform MAC check, gate array check and transcript (log) check and apply threshold decryption on the final QOTP keys while TA applies trap-based check on the quantum side and proceeds with the final decryption to recover the intersection result.

4. Security Analysis 4.1. Correctness To validate the correctness of our logical multi-party AND gate, we instantiate the quantum subroutine using the multi-controlled gate with v-chain ancilla through the IBM Quantum Platform and the qiskit library. In particular, for the three-party case we implement a three-controlled gate Page 5 of 14

QPSO

Protocol 1 MP-QPSI 1: Protocol Input: Security parameter 𝜅, the upper bound on the number of 𝖳 and 𝖧 gates 𝑡, ℎ ∈ ℕ, number of parties 𝑛,

and a fixed self-dual CSS code 𝖢𝖲𝖲 [[𝑚, 1, 𝑑]].

2: Protocol Output: ⟂ if protocol abort, else {0,1} represent the intersection output. 3: Phase 1: Preparation and KeyGen 4: For Trust Authority (TA): 5: Run 𝑘𝖳𝖠 ← 𝖬𝖠𝖢.𝖪𝖾𝗒𝖦𝖾𝗇(1𝜅 ) to obtain the MAC key for TA. 6: Uniformly sample a permutation 𝜋 ←𝑅 𝑆3𝑚 from the permutation group on 3𝑚 positions. 7: For each 𝑖 ∈ {0, … , 𝑡}, run (𝑠𝑘𝑖 , 𝑝𝑘𝑖 , 𝑒𝑣𝑘𝑖 ) ← 𝖧𝖤.𝖪𝖾𝗒𝖦𝖾𝗇(1𝜅 ). 8: Set 𝖪𝖤𝖸𝑒𝑣𝑎𝑙 ∶= (𝑒𝑣𝑘0 , … , 𝑒𝑣𝑘𝑡 , 𝑝𝑘0 , … , 𝑝𝑘𝑡 ) and compute 𝜋̃ ← 𝖧𝖤.𝖤𝗇𝖼𝑝𝑘 (𝜋). 9:

0

′ Prepare the target state as 𝜎𝖺𝗎𝗑 , sample QOTP keys (𝑎0 , 𝑏0 ) ←𝑅 {0, 1}, then encrypt 𝜎𝖺𝗎𝗑 from QPTP as: 𝜎𝖺𝗎𝗑 ← 𝑎 𝑏 𝑎 𝑏 𝖷 0 𝖹 0 𝜎𝖺𝗎𝗑 𝖷 0 𝖹 0 and return ′ 𝜎 ̃𝖺𝗎𝗑 ← 𝜎𝖺𝗎𝗑 ⊗ 𝖬𝖠𝖢.𝖲𝗂𝗀𝗇𝑘𝑇 𝐴 (𝖧𝖤.𝖤𝗇𝖼𝑝𝑘0 (𝑎0 , 𝑏0 )).

Using bounds (𝑡, ℎ) and the code 𝖢𝖲𝖲[[𝑚, 1, 𝑑]], prepare a pool of encrypted magic states (for all 𝖳∕𝖧 gates) with traps, and denote the collection by 𝖬𝖺𝗀𝗂𝖼𝖯𝗈𝗈𝗅. 11: Run (Γ1 , … , Γ𝑡 ) ← 𝖦𝖺𝖽𝗀𝖾𝗍𝖦𝖾𝗇(𝑡, 𝑠𝑘0 , … , 𝑠𝑘𝑡−1 ) to generate all 𝖳-gate gadgets. 12: Send the authenticated evaluation key package to TP ( ) ̃𝖺𝗎𝗑 . 𝜌𝖾𝗏𝗄 ← 𝖬𝖠𝖢.𝖲𝗂𝗀𝗇𝑘𝖳𝖠 𝖬𝖠𝖢.𝖲𝗂𝗀𝗇𝑘𝖳𝖠 (𝖪𝖤𝖸𝖾𝗏𝖺𝗅 , 𝜋̃), 𝖬𝖺𝗀𝗂𝖼𝖯𝗈𝗈𝗅, Γ1 , … , Γ𝑡 , 𝜎 10:

13: To obtain the secret shares (𝑠𝑘1𝑡 , … , 𝑠𝑘𝑛𝑡 ) ← 𝖲𝖲.𝖲𝗁𝖺𝗋𝖾(𝑠𝑘𝑡 , 𝑛) and send the key package 𝗄𝖾𝗒𝑖 ∶= (𝑝𝑘0 , 𝑠𝑘𝑖𝑡 , 𝜋) to 𝑃𝑖 . 14: Phase 2: Encryption 15: For Parties 𝑃𝑖 : 16: Run 𝑘𝑖 ← 𝖬𝖠𝖢.𝖪𝖾𝗒𝖦𝖾𝗇(1𝜅 ) to obtain the MAC key for 𝑃𝑖 . 17:

Let 𝑖 = {𝑥(𝑖) , … , 𝑥(𝑖) } and set 𝐿 ∶= max𝑖 𝑙𝑖 . Fix a global ordering  = (𝑥1 , … , 𝑥𝐿 ) of the universe. Prepare a 𝑙 1 𝑖

sequence of 𝐿 qubits 𝑖𝑄 = (|𝜎1𝑖 ⟩, … , |𝜎𝐿𝑖 ⟩) where { |𝜎𝑗𝑖 ⟩ = 18:

|1⟩ ,

if 𝑥𝑗 ∈ 𝑆𝑖 ,

|0⟩ ,

if 𝑥𝑗 ∉ 𝑆𝑖 .

( For all according qubit, 𝑃𝑖 do 𝜎𝑗𝑖′ ← 𝖢𝖲𝖲.𝖤𝗇𝖼𝗈𝖽𝖾(𝜎𝑗𝑖 ) and add traps with permutation 𝜎𝑗𝑖′′ ← 𝗉𝖾𝗋𝗆𝗎𝗍𝖾𝜋 𝜎𝑗𝑖′ ⊗ |0𝑚 ⟩ ⊗ ) 𝑎𝑖 𝑏 𝑖 𝑎𝑖 𝑏𝑖 |+𝑚 ⟩ , and encrypt 𝜎𝑗𝑖′′′ ← 𝖷 𝑗 𝖹 𝑗 𝜎𝑗𝑖′′ 𝖷 𝑗 𝖹 𝑗 with QOTP keys (𝑎𝑖𝑗 , 𝑏𝑖𝑗 ) ←𝑅 {0, 1}3𝑚 and return 𝜎 ̃𝑗𝑖 ← 𝜎𝑗𝑖′′′ ⊗ 𝖬𝖠𝖢.𝖲𝗂𝗀𝗇𝑘𝑖 (𝖧𝖤.𝖤𝗇𝖼𝑝𝑘0 (𝑎𝑖𝑗 , 𝑏𝑖𝑗 )).

19:

Send ̃𝑖𝑄 = (̃ 𝜎1𝑖 , … , 𝜎 ̃𝐿𝑖 ) to TP (Quantum state together with the classical QOTP keys under MAC).

𝖠𝖭𝖣 with controls 𝑞 , 𝑞 , 𝑞 and target 𝑞 , as shown in 𝐶(3) 0 1 2 4 Fig. 3. On the logical level this gate realises the map: 𝖠𝖭𝖣 | 𝐶(3) ∶ |𝑞0 , 𝑞1 , 𝑞2 ⟩𝑄 |0⟩𝑞4 ⟼ ||𝑞0 , 𝑞1 , 𝑞2 ⟩𝑄 ||𝑞0 ∧ 𝑞1 ∧ 𝑞2 ⟩𝑞

for all 𝑞0 , 𝑞1 , 𝑞2 ∈ {0, 1}. We further initialise (𝑞0 , 𝑞1 , 𝑞2 ) ∑ | in the uniform superposition √1 (𝑞0 ,𝑞1 ,𝑞2 )∈{0,1}3 |𝑞0 , 𝑞1 , 𝑞2 ⟩ 8

and simulate the circuit on qiskit. The output distribution of 𝑞4 , reported in Fig. 4, coincides with the ideal truth table of the logical AND. The same functional behaviour extends immediately to an 𝑛-party setting and to all 𝐿 positions of the universe. For each position 𝑗 we therefore use an 𝑛-controlled gate 𝐶 𝖠𝖭𝖣 with controls (𝑞1,𝑗 , … , 𝑞𝑛,𝑗 ) and target 𝑡𝑗 . In our protocol this logical gate is surrounded by CSS code, trap-code encoding, Zixian Gong et al.: Preprint submitted to Elsevier

4

permutation and QOTP, the whole map is as: ( ) −1 𝖢𝖲𝖲.𝖣𝖾𝖼𝗈𝖽𝖾◦𝗉𝖾𝗋𝗆𝗎𝗍𝖾−1 ◦𝐶𝑗𝖠𝖭𝖣 ◦ 𝜋 ◦𝖰𝖮𝖳𝖯 ( )( ⟩ ) | 𝖰𝖮𝖳𝖯◦𝗉𝖾𝗋𝗆𝗎𝗍𝖾𝜋 ◦𝖢𝖲𝖲.𝖤𝗇𝖼𝗈𝖽𝖾 |𝑞1,𝑗 , … , 𝑞𝑛,𝑗 |0⟩𝑡𝑗 | 𝑄𝑗 ⟩ 𝑛 ⟩ ||⋀ | = |𝑞1,𝑗 , … , 𝑞𝑛,𝑗 . | 𝑞𝑖,𝑗 | 𝑄𝑗 | | 𝑖=1 𝑡𝑗 Moreover, the correctness of the encode layer follows immediately from the evaluation correctness of TFHE and the correctness of the MAC (Definitions 2 and 13).

Page 6 of 14

QPSO

Protocol 1 MP-QPSI (continued) 20: Phase 3: Homomorphic Evaluation 21: For Third Party (TP): For clarity of presentation, we suppress the explicit position index 𝑗 and describe the evaluation 22:

on a generic wire; the same procedure is applied independently to every position. Initialise the computation transcript 𝑙𝑜𝑔 and fix the quantum circuit 𝐶 𝖠𝖭𝖣 (i.e. 𝖢𝑛 𝖷) that implements the multi-party logical AND. Decompose it into alternating 𝑐 Clifford and 𝑡 𝖳-layers: (1) (2) (𝑐) 𝐶 𝖠𝖭𝖣 = 𝐶𝖢𝗅𝗂𝖿𝖿 ◦𝐶𝖳(1) ◦𝐶𝖢𝗅𝗂𝖿𝖿 ◦ ⋯ ◦𝐶𝖳(𝑡) ◦𝐶𝖢𝗅𝗂𝖿 . 𝖿

( (𝓁) ) (𝓁) (𝓁) For Clifford layers 𝐶𝖢𝗅𝗂𝖿𝖿 : Processes the 𝖳𝗋𝖺𝗉𝖳𝖯.𝖤𝗏𝖺𝗅𝖢𝗅𝗂𝖿 𝖿 𝐶𝖢𝗅𝗂𝖿 ,𝜎 ̃, 𝑎̃, ̃ 𝑏, 𝖪𝖤𝖸𝑒𝑣𝑎𝑙 , 𝜋̃, 𝑙𝑜𝑔 which applies 𝐶𝖢𝗅𝗂𝖿 to 𝜎 ̃ and, 𝖿 𝖿 via 𝖧𝖤.𝖤𝗏𝖺𝗅, homomorphically update the encrypted QOTP keys (̃ 𝑎, ̃ 𝑏) and append this step to 𝑙𝑜𝑔. ( ) 24: For 𝖳 layers 𝐶𝖳(𝓁) : Processes the 𝖳𝗋𝖺𝗉𝖳𝖯.𝖤𝗏𝖺𝗅𝖳 𝐶𝖳(𝓁) , 𝜎 ̃, 𝑎̃, ̃ 𝑏, Γ𝓁 , 𝖬𝖺𝗀𝗂𝖼𝖯𝗈𝗈𝗅, 𝖪𝖤𝖸𝑒𝑣𝑎𝑙 , 𝜋̃, 𝑙𝑜𝑔 which consumes one gadget Γ𝓁 and performs the required Bell measurements through a magic state from 𝖬𝖺𝗀𝗂𝖼𝖯𝗈𝗈𝗅 to remove the 𝖯-correction caused by 𝖳 gate, and then uses 𝖧𝖤.𝖤𝗏𝖺𝗅 to homomorphically perform the 𝖱𝖾𝖼𝗋𝗒𝗉𝗍 of the QOTP key and intermediate values and randomness are appended to 𝑙𝑜𝑔. Conceptually, ( ) ( ) 𝑎̃[𝑝𝑘𝓁+1 ] , ̃ 𝑏[𝑝𝑘𝓁+1 ] ← 𝖧𝖤.𝖤𝗏𝖺𝗅𝑒𝑣𝑘𝓁 𝑎̃[𝑝𝑘𝓁 ] , ̃ 𝑏[𝑝𝑘𝓁 ] , 𝖪𝖤𝖸𝑒𝑣𝑎𝑙 23:

We write subscript [⋅] for the encryption under the specific key. After all Clifford and 𝖳-layers of 𝐶 𝖠𝖭𝖣 have been processed, the multi–controlled gate 𝖢𝑛 𝖷 implementing the logical AND has been applied to the 𝜎 ̃𝖺𝗎𝗑 resulting the output 𝜎 ̃ with (̃ 𝑎 𝗈𝗎𝗍 , ̃ 𝑏𝗈𝗎𝗍 ) encrypted under 𝑝𝑘𝑡 . ( 𝗈𝗎𝗍 ) 𝗈𝗎𝗍 𝗈𝗎𝗍 ̃ 26: TP sends the classical data with circuit description 𝑎̃ , 𝑏 , 𝑙𝑜𝑔, 𝐶 𝖠𝖭𝖣 to all parties {𝑃𝑖 } and (̃ 𝜎𝗈𝗎𝗍 , 𝑙𝑜𝑔) to TA. 27: Phase 4: Verification and Decryption 28: Classical.VerDec: 29: (𝑃𝑖 ) MAC Check: 𝑃𝑖 verify its own initial QOTP key ciphertexts recorded in 𝑙𝑜𝑔: 𝖬𝖠𝖢.𝖵𝖾𝗋𝑘 (̃ 𝑎𝑖 , ̃ 𝑏𝑖 ). if any check fails, 𝑖 set 𝖢.𝖠𝖼𝖼𝖾𝗉𝗍 ← 0 and abort. 30: (𝑃𝑖 ) Gate array Check: Reconstruct from 𝑙𝑜𝑔 the sequence of evaluated gates and compare it with the prescribed gate array 𝐶 𝖠𝖭𝖣 . If they differ, set 𝖢.𝖠𝖼𝖼𝖾𝗉𝗍 ← 0 and abort. 31: (𝑃𝑖 ) Transcript Check: Jointly run the standard transcript checking procedure on 𝑙𝑜𝑔 using the public evaluation keys 𝖪𝖤𝖸𝑒𝑣𝑎𝑙 and threshold decryption with {𝑠𝑘𝑖𝑡 }𝑖∈[𝑛] : 25:

𝖿 𝗅𝖺𝗀𝖥𝖧𝖤 ← 𝖢𝗁𝖾𝖼𝗄𝖫𝗈𝗀(𝖪𝖤𝖸𝑒𝑣𝑎𝑙 , 𝑙𝑜𝑔, {𝑠𝑘𝑖𝑡 }).

If 𝖿 𝗅𝖺𝗀𝖥𝖧𝖤 = 𝗋𝖾𝗃, set 𝖢.𝖠𝖼𝖼𝖾𝗉𝗍 ← 0 and abort.

32: Otherwise, set 𝖢.𝖠𝖼𝖼𝖾𝗉𝗍 ← 1 and the participants obtain the final QOTP keys (𝑎𝗈𝗎𝗍 , 𝑏𝗈𝗎𝗍 ) via threshold decryption:

(𝑎𝗈𝗎𝗍 , 𝑏𝗈𝗎𝗍 ) ← 𝖳𝖥𝖧𝖤.𝖣𝖾𝖼{𝑠𝑘𝑖 } (̃ 𝑎 𝗈𝗎𝗍 , ̃ 𝑏𝗈𝗎𝗍 ) 𝑡

and send 𝖢.𝖠𝖼𝖼𝖾𝗉𝗍 and (𝑎𝗈𝗎𝗍 , 𝑏𝗈𝗎𝗍 ) to TA. 33: Quantum.VerDec: 34: (TA) MAC Check: TA verifies the MAC on the evaluation package: 𝖬𝖠𝖢.𝖵𝖾𝗋𝑘 (𝜌𝖾𝗏𝗄 ). 𝖳𝖠 35: (TA) Trapcode Check: For the 3𝑚–qubit block, to remove the one–time pad: 𝗈𝗎𝗍

𝜎𝗈𝗎𝗍 ← 𝖷𝑎 𝖹𝑏

𝗈𝗎𝗍

𝗈𝗎𝗍

𝗈𝗎𝗍

𝜎 ̃𝗈𝗎𝗍 𝖷𝑎 𝖹𝑏 .

Undo the permutation and split target and trap registers: (𝜎target , 𝜎 𝖷-trap , 𝜎 𝖹-trap ) ← 𝗉𝖾𝗋𝗆𝗎𝗍𝖾𝜋 −1 (𝜎𝗈𝗎𝗍 ). Measure the 𝖷–trap block 𝜎 𝖷-trap in the computational basis and the 𝖹–trap block 𝜎 𝖹-trap in the Hadamard basis; if any outcome is nonzero (resp. non–|+⟩), then return (⊥, 𝖠𝖼𝖼𝖾𝗉𝗍 ← 0). 36: (TA) Else, set 𝖰.𝖠𝖼𝖼𝖾𝗉𝗍 ← 1, apply 𝖢𝖲𝖲.𝖣𝖾𝖼𝗈𝖽𝖾 to 𝜎target to recover the logical target qubit, measure it in the according basis, compare the outcome with the classical bit associated with 𝜎𝖺𝗎𝗑 to determine the intersection indicator 𝑏 ∈ {0, 1}, and broadcast 𝑏 to all participants with 𝖠𝖼𝖼𝖾𝗉𝗍 ← 1.

4.2. Participant Privacy

Zixian Gong et al.: Preprint submitted to Elsevier

In this section, we will evaluate the privacy of the participants against TP, outside eavesdropper and other participants as follows: Page 7 of 14

QPSO q0 q1 q2

T

q3

H

q4

H

T

T

T

T

H

T

T T

T

T

T

H

T

T

T

T

H

H

c 1

0

Figure 3: Decomposition of the three-controlled AND with v-chain ancilla.



4XDVL3UREDELOLW\

    

































0HDVXUHPHQW2XWFRPH

Figure 4: The Measurement outcome of 𝑞4 together with the 𝑞0 , 𝑞1 , 𝑞2 in uniform superposition.

(1) TP learns nothing about the private sets of 𝑃𝑖 ; (2) Any outside eavesdropper is unable to learn anything about the private sets of 𝑃𝑖 ; (3) 𝑃𝑖 cannot obtain extra information about the private sets of other participants beyond the intersection, even when conspiring with other participants or TP.

Classical part. All input-dependent classical data are encrypted under TFHE and authenticated by MAC. Combining the IND-CPA security of TrapTP and TFHE with Lemma 1 in [DSS16], and EUF-CMA security of the MAC, all classical ciphertexts and tags observed by TP are computationally indistinguishable.

Theorem 1 (Privacy against TP). In the MP-QPSI scheme proposed in Protocol 1, TP cannot obtain any information about the private sets of participants.

Theorem 2 (Privacy against eavesdroppers). Any external adversary  that can wiretap both the quantum and classical channels and perform arbitrary quantum attacks still learns no information about the private sets.

Proof. Quantum part. According to the encryption phase of Protocol 1, from the point of view of the TP who receives quantum state under QOTP: 𝜎̃ = 𝖷𝑎 𝖹𝑏 𝗉𝖾𝗋𝗆𝗎𝗍𝖾𝜋 (𝖢𝖲𝖲.𝖤𝗇𝖼𝗈𝖽𝖾(𝜎)⊗|0𝑚 ⟩⊗|+𝑚 ⟩) 𝖹𝑏 𝖷𝑎 . where (𝑎, 𝑏) ∈ {0, 1}3𝑚 , According to the property and average over the uniformly random key yields TP’s reduced density matrix 1 ∑ 𝕀 𝜌(𝜎) = 𝜎̃ = , TP 3𝑚 3𝑚 4 𝑎,𝑏 2 which is maximally mixed and information-theoretically secure. In particular, 𝜌(0) = 𝜌(1) , so the success probability of TP TP any Unambiguous State Discrimination (USD) test [HB05] is negligible which means TP cannot extract any information on the logical bits from the quantum registers. Zixian Gong et al.: Preprint submitted to Elsevier

Proof. Same as mentioned in Theorem 1, each logical qubit is first encoded under CSS, traps, permutation and QOTP. Thus an outside eavesdropper without the QOTP keys and permutation obtains no information about the private sets due to the fact that the quantum states are maximally mixed, and the classical information are encrypted under TFHE and authenticated by MAC. Moreover, our encoding makes the protocol against standard outside attacks such as intercept-measure-resend, measurement-resend, dense-coding attacks, and auxiliaryqubit attacks. [LK05] For example, any attempt from  to intercept and re-prepare the sequence without knowing the trap positions and their correct measurement bases will inevitably introduce errors which will be detected in the 𝖵𝖾𝗋𝖣𝖾𝖼 procedure, and post-interaction auxiliary qubit can Page 8 of 14

QPSO Abort : ⊥ CS Q′

CS Q

SQ keyi

Enc

log

M

κ

KeyGen

ρevk

F QPSI

ATP

′ CQOTP

SQ

′

⊘

QOTP′ Classical VerDec

c APc

SQ ′

SQ

CQOTP

D

Quantum VerDec C.Accept

Accept

ski ki

0/1

M

D

c κ

S

0/1

Acc(1)/Rej(0)

log

Figure 5: The Real-world (left) and Ideal-world (right) model.

not reveal meaningful information due to the maximally mixed states. Theorem 3. Let 𝐶 be any subset of corrupted participants with |𝐶 | < 𝑡. Even if the parties in 𝐶 collude with the TP, they obtain no information about the honest parties’ private sets beyond the intersection. Proof. (1) Intercepting honest channels to TP. The coalition 𝐶 may try to intercept all classical and quantum messages sent by honest parties to TP and reconstruct their private sets. Classically, honest parties only send TFHE ciphertexts of QOTP keys together with MAC tags. Since the TFHE secret key 𝑠𝑘 is shared with a 𝑛𝑡 -out-of-𝑛 SS scheme like Definition 3, The privacy of SS in Definition 5 and Lemma 1 implie that the shares held by 𝐶 (with |𝑃𝐶 | < 𝑡) reveal no information about 𝑠𝑘. On the quantum side, without the corresponding QOTP keys the intercepted states are exactly the QOTP-masked codewords which is maximally mixed state and information-theoretically secure. (2) Colluding with TP to deviate in the evaluation. The coalition 𝐶 may also collude with TP and ask TP to run a modified evaluation to extract extra information (e.g., a different gate array) and try to pass 𝖢𝗅𝖺𝗌𝗌𝗂𝖼𝖺𝗅.𝖵𝖾𝗋𝖣𝖾𝖼 procedure. Members of 𝐶 can reveal their own MAC keys 𝑘𝑖 to TP to pass the local MAC checks and gate array check of corrupted side, but MAC keys of honest participants remain unknown, any deviation that affects ciphertexts or logs will cause some MAC or gate array check from honest side to fail. We can set a threshold number of necessary passes for the local checks to ensure that the whole 𝖢𝗅𝖺𝗌𝗌𝗂𝖼𝖺𝗅.𝖵𝖾𝗋𝖣𝖾𝖼 process detects and terminates the aforementioned corruption with an overwhelming probability. In both cases, the joint view of 𝐶 can be simulated from its own inputs and the intersection alone, hence 𝐶 gains no extra information about the other participants’ private sets.

4.3. Verifiability Against Malicious TP We now turn to the verifiability of our protocol against a malicious TP. At a high level, the security of a vQFHE scheme requires that any server who deviates significantly from the prescribed evaluation map 𝗏𝖰𝖥𝖧𝖤.𝖤𝗏𝖺𝗅 will be

Zixian Gong et al.: Preprint submitted to Elsevier

caught by the verification procedure: whenever the algorithm 𝖵𝖾𝗋𝖣𝖾𝖼 accepts, the decrypted output state must be close to the ideal output obtained by applying the target circuit to the input. Following the 𝜅-SEM-VER notion in Definition 10, together with the quantum authentication [DNS12, BW16] and semantic secrecy [ABF+ 16], we define a Real experiment and an Ideal experiment for our MP-QPSI protocol as depicted in Fig. 5. Informally, the figure captures that every adversary  with access to the ciphertexts in the Real world can be simulated by a simulator  that has access only to an ideal PSI functionality in the Ideal world. In the remainder of this section, we encapsulate certain components of the Real model into functionality blocks and use hybrid chain to prove the verifiability that for any quantum poly-time distinguisher : ] [ ]| 𝖬𝖯−𝖰𝖯𝖲𝖨 QPSI | [ ) = 1 −Pr (𝖨𝖽𝖾𝖺𝗅 ) = 1 | ≤ 𝗇𝖾𝗀𝗅(𝜅), |Pr (𝖱𝖾𝖺𝗅Π  | | which formalises that the Real and Ideal executions of our protocol are computationally indistinguishable and the protocol is verifiable in the semantic sense. 𝖬𝖯−𝖰𝖯𝖲𝖨

𝐇𝟎 : This is the Real model 𝖱𝖾𝖺𝗅Π as shown in Fig. 5,  which is designed based on the interaction process of our proposed MP-QPSI protocol 1. 𝐇𝟏 : From the Real experiment H0 , we first pass to H1 by encapsulating the KeyGen and Enc modules into a single functionality 𝖤𝗇𝖼∗ as shown in the red areaof Fig. 6. For a subset of honest parties 𝑆 , with |𝑆| ≥ 𝑡. By the correctness of SS (Definition 4), from the viewpoint of the adversary we equivalently treat “TA plus the honest participants” as a single honest entity that locally holds 𝑠𝑘, just as in the original TrapTP setting: ) ) H ( H ( 𝗏𝗂𝖾𝗐0 {𝑠𝑘𝑖 }𝑖∈𝑆 , ⋅ ≡ 𝗏𝗂𝖾𝗐1 𝑠𝑘, ⋅ H

which lead to 𝖠𝖽𝗏𝖧𝗒𝖻H1 () = 0 where 𝖠𝖽𝗏𝖧𝗒𝖻 is used as 0 distinguishing program between hybrid models. 𝐇𝟐 : In Fig. 6, the blue region corresponds to the TP together with a subset of colluding participants 𝐶 . In hybrid H2 we conceptually bundle these components into a single unified Page 9 of 14

QPSO

VerDecsk

SQ

Enc∗

CS Q′

CS Q keyi

Enc

′

SQ

CQOTP log

M

κ

KeyGen

ρevk

ATP

′ CQOTP

QOTP′ Classical VerDec

c APc

Abort : ⊥

C.Accept

0/1

D

Quantum VerDec Accept

ski ki log

A

Figure 6: Modularly encapsulated hybrid of 𝐻0 .

adversary  = (𝖳𝖯 , 𝐶 ) who controls both the TP and the corrupted parties. By Theorem 3 and SS privacy (Definition 5), any information about the honest private sets that can be obtained jointly by 𝖳𝖯 and 𝐶 can be closely simulated from the view of the unified adversary . For H 𝖠𝖽𝗏𝖧𝗒𝖻H2 (): 1

] [ ]| H H | [ |Pr (𝗏𝗂𝖾𝗐1 ( ⋅ )) = 1 −Pr (𝗏𝗂𝖾𝗐2 ( ⋅ , {𝑘𝑖 , 𝑠𝑘𝑖 }𝑖∈𝐶 )) = 1 | | | with probability 𝗇𝖾𝗀𝗅(𝜅). So, treating TP and the colluding participants as a single adversarial interface does not alter the distribution of the adversary’s view with overwhelming probability. 𝐇𝟑 : In H3 , we encapsulate the green part of Fig. 6, namely Classical.VerDec, Quantum.VerDec and the Abort box, into a single verification algorithm 𝖵𝖾𝗋𝖣𝖾𝖼𝑠𝑘 . The critical point in this encapsulation step is whether the distributed verification process in our scheme can achieve the same level of verifiability as 𝖵𝖾𝗋𝖣𝖾𝖼𝑠𝑘 in 𝗏𝖰𝖥𝖧𝖤. That is, any deviation from the target circuit will be rejected at this stage. Lemma 2. For any QPT adversary , there exists adversaries 1 and 2 such that: H

𝖠𝖽𝗏𝖧𝗒𝖻H3 () ≤ 𝖠𝖽𝗏𝖾𝗎𝖿−𝖼𝗆𝖺 (1 )+𝖠𝖽𝗏𝖳𝗋𝖺𝗉 (2 )+𝗇𝖾𝗀𝗅(𝜅). 𝖬𝖠𝖢 2

Proof. In our protocol the verification is combined as 𝖠𝖼𝖼𝖾𝗉𝗍 = 1 ⟺ 𝖢.𝖠𝖼𝖼𝖾𝗉𝗍 = 1 ∧ 𝖰.𝖠𝖼𝖼𝖾𝗉𝗍 = 1, where 𝖢.𝖠𝖼𝖼𝖾𝗉𝗍 is the outcome of Classical.VerDec (MAC check, gate array check and log check) and 𝖰.𝖠𝖼𝖼𝖾𝗉𝗍 is the outcome of Quantum.VerDec (trapcode check). By correctness and EUF–CMA security of the MAC in Definition 13, evaluation correctness of TFHE in Definition 2, and soundness of the trap code. We can directly derive that the probability: [ ] ′ Pr 𝖠𝖼𝖼𝖾𝗉𝗍 = 1 ∧ 𝑆 𝑄 ≠ Φ𝐶 𝖠𝖭𝖣 (𝑆 𝑄 ) Zixian Gong et al.: Preprint submitted to Elsevier

−𝖼𝗆𝖺 is smaller than 𝖠𝖽𝗏𝖾𝗎𝖿 (1 ) + 𝖠𝖽𝗏𝖳𝗋𝖺𝗉 (2 ) + 𝗇𝖾𝗀𝗅(𝜅) 𝖬𝖠𝖢 where they represent the maximal advantages of any QPT adversaries 1 , 2 in breaking the MAC check and the trapcode check, and the negligible errors 𝗇𝖾𝗀𝗅(𝜅) come from two parts: 𝗇𝖾𝗀𝗅𝖧𝖤 (𝜅) comes from evaluation of 𝖧𝖤 in log check and gate array check and 𝗇𝖾𝗀𝗅𝖢𝖲𝖲 (𝜅) comes from the decoding failure [Got09].

According to the Lemma above, the joint map of Classical.VerDec, Quantum.VerDec and Abort is computationally indistinguishable from an ideal single verification routine 𝖵𝖾𝗋𝖣𝖾𝖼𝑠𝑘 . 𝐇𝟒 : After encapsulating the above three blocks, the resulting hybrid model is in fact an instance of the semantic real model of Definition 5 in [ADS+ 17] where the vQFHE is a combination of TrapTP and TFHE, instantiated with our logical circuit 𝐶 𝖠𝖭𝖣 . All structural requirements of that definition are met: our decryption algorithm belongs to 𝖭𝖢1 and the circuit for 𝐶 𝖠𝖭𝖣 has a polynomially bounded number of 𝖳 gates. Moreover, Theorem 5 in [ADS+ 17] already shows that TrapTP is 𝜅-IND-VER, and hence 𝜅-SEM-VER. Applying the definition of 𝜅-SEM-VER in Definition 10 to H3 , we can replace the semantic real model by the corresponding ideal QPSI model. This yields exactly the ideal functionality 𝖨𝖽𝖾𝖺𝗅 H

shown in Fig. 5 and lead to 𝖠𝖽𝗏𝖧𝗒𝖻H4 ≤ 𝗇𝖾𝗀𝗅(𝜅) . 3

H

As mentioned above, we can finally bound 𝖠𝖽𝗏𝖧𝗒𝖻H4 0 by a negligible function in 𝜅 based on the hybrid reduction derived from the preceding intermediate analysis and lead to the verifiability of our scheme mentioned above.

5. Flexible and Modular Realizations of MP-QPSO The verifiability analysis in Section 4.3 already suggests a modular interpretation of our construction. At a high level, the MP-QPSI protocol against malicious TP and collusion

Page 10 of 14

QPSO q0 q1 q2 q3 q4 c

|0

H

T

T

T

T

T

T

X

1

0 0x0

0x1

Figure 7: CCCZ circuit built using only 6 T gates.

can be seen as the composition of a small number of blackbox modules: (i) a threshold layer makes the scheme resistant to collusion of the participants; (ii) a vQFHE layer against any deviation from the target circuit; (iii) a logical quantum circuit implementing the desired set operation. Consequently, different circuit instantiations or alternative QHE constructions can be plugged into the same framework to achieve different effects. In the remainder of this section we illustrate the modular nature of our framework through several examples, including choosing alternative intersection circuits to reduce the number of 𝖳-gates, modifying the circuit to realize QPSU, and replacing the underlying QHE logic to obtain gadgetfree instantiations.

5.1. Circuit-Level Variants for Intersection CCCZ-based reduction of 𝖳-gates. In our basic instantiation, the multi-party AND circuit 𝐶 𝖠𝖭𝖣 is a 𝖢𝑛 𝖷 with vchain ancilla which costs approximately 7(𝑛 − 1) 𝖳-gates for 𝑛 inputs. By instead expressing the intersection as a multicontrolled phase and using the CCCZ construction of [GJ21] (we have simulated the realization in qiskit as Fig. 7), we can implement an 𝑛-controlled AND with only 4𝑛 − 6 𝖳gates. Thus, within the same MP-QPSI framework, replacing the original 𝖢𝑛 𝖷 block by a CCCZ-based realization yields a strictly lower 𝖳-gate complexity for the homomorphic evaluation phase. QuAND realization. When the TP is equipped with strong quantum capabilities (e.g., a high-scalability superconducting processor), the logical AND subroutine in our intersection circuit can be instantiated using the QuAND gate [CHZ+ 21]. A QuAND can be synthesized by combining a single-qubit 𝑋 gate with an iSWAP-like operation that selectively swaps |11⟩ ↔ |20⟩, exploiting the |2⟩ ancilla level only for temporary state transfer while maintaining reversibility. Under this setting, [CHZ+ 21] have experimentally realized the resulting 𝑛-qubit controlled-𝑍 (and thus a generalized Toffoli) on an 8-qubit superconducting platform; when compiled onto a 1D chain, it requires 2𝑛−3 two-qubitgate cycles and achieves overall depth (𝑛).

5.2. From QPSI to QPSU via Open Controls In our MP-QPSI construction, the predicate bit is obtained by the circuit 𝐶 𝖠𝖭𝖣 . To realize QPSU within exactly the same framework, we only need to change this predicate Zixian Gong et al.: Preprint submitted to Elsevier

from an AND to an OR. For Boolean inputs 𝑥1 , … , 𝑥𝑛 ∈ {0, 1}, we use De Morgan’s law ( 𝑛 ) 𝑛 ⋁ ⋀ OR(𝑥1 , … , 𝑥𝑛 ) = 𝑥𝑖 = ¬ ¬𝑥𝑖 . 𝑖=1

𝑖=1

At the circuit level this is implemented by turning the multi–controlled 𝖢𝑛 𝖷 into an multi–open–controlled gate: each control qubit is conjugated by an 𝖷 gate before and after the control place as shown in Fig. 8 (realizing control on |0⟩ instead of |1⟩), and the target qubit is flipped once more to account for the outer negation. x1 x2 t

=

x1

X

X

x2

X

X

t

X

X

Figure 8: Multi-Open-Controlled X Gate

5.3. Alternative vQHE Instantiations The verifiability of the underlying vQFHE scheme is what gives our MP-QPSI protocol its distinguishing ability to detect a TP that deviates from the prescribed circuit. In Protocol 1 we instantiate this layer with TrapTP [ADS+ 17], the first vQFHE construction, whose complicate encoding and trap structure yield very strong security guarantees and a clean 𝜅-SEM/IND-verifiability analysis. This comes at the price of higher complexity: the quantum communication of TrapTP is on the order of (18𝑛). Within our modular framework, the TrapTP component can be replaced by more communication-efficient vQFHE schemes. For example, Broadbent’s information-theoretic secure construction [Bro18] reduces the quantum communication to (6𝑛) at the cost of additional interaction between client and server [LWC+ 25], while more recent schemes such as [HCL+ 24, LWC+ 25] achieve (6𝑛) quantum communication together with essentially non-interactive verification. All these vQHE variants can be plugged into the MPQPSO template and combined with the same TFHE-based threshold layer to obtain multi-party, verifiable QPSI and its extensions.

Page 11 of 14

QPSO Table 1 Comparison of quantum private set protocols. Protocol

Quantum Resources

[SMZ+ 15]

Encoded States

[ZLS+ 20]

GHZ State

[DDK+ 21]

Single Photons

[LRS+ 21]

Single Photons

[MD23]

Single Photons

+

[LLW 23]

Single Photons

+

[CZZ 24]

Bell States

[MSD+ 24]

Single Photons

[HZZ24]

Single Photons

Ours

Encoded States

Quantum Technologies Complicated operator G Pauli operation Asymmetric key distribution Pauli operation Pauli operation QHE Qubit operation Rotation operation Rotation operation vQFHE

Party Scenarios

Supported Functionality

TP Model

Collusion Resistance

Communication Complexity

Two-Party

PSI

Semi-honest

N/A

(𝐿)

Three-Party

PSI-CA PSU-CA

Semi-honest

Client

(𝐿)

Two-Party

PSI

Semi-honest

N/A

(𝐿 + 𝜅)

Two-Party

PSI-CA

Semi-honest

N/A

(𝐿𝑙𝑜𝑔𝐿)

Multi-party

PSI

N/A

Single client

(𝑛𝐿)

Two-party

PSI-CA PSI&PSU Mixed-CA

Semi-honest

N/A

(𝐿)

Semi-honest

None

(𝐿)

Three-party Two-Party

Threshold PSI

Trusted

N/A

(𝜅𝐿)

Multi-party

PSI

Semi-honest

Client

(𝑛𝜅𝐿)

Multi-Party

PSI&PSU

Malicious

TP–client

(𝑛𝜅𝐿)

6. Performance analysis Quantum Communication Cost. Each party encodes its 𝐿-qubit universal private set sequence like the TrapTP scheme [ADS+ 17]. Specifically, each block is encoded via a CSS[[𝑚, 1, 𝑑]] code and augmented with 2𝑚 trap qubits (|0⟩ and |+⟩), resulting in a 3𝑚𝐿-qubit authenticated block. The total communication is thus 3𝑛𝑚𝐿 qubits for 𝑛 parties. Considering the auxiliary information from TA (pre-shared EPR pairs for 𝑡 and ℎ gates and auxiliary quantum information). Due to the feasibility constraints of TrapTP instantiations, the parameters satisfy 𝑚, 𝑡, ℎ = (𝜅), the aggregate quantum communication complexity is (𝑛𝜅𝐿). Quantum Computation Cost. TP homomorphically evaluates the multi-party intersection circuit through 3𝑛𝑚𝐿 qubits. The underlying logical quantum computation consists of (𝑛𝑚𝐿) gate operations. On the verifier side, TA measures 2𝑚𝐿 trap qubits and performs the corresponding decoding checks, which costs (𝑚𝐿). With 𝑚 = (𝜅), the overall quantum computation cost is dominated by TP and can be summarized as (𝑛𝜅𝐿). Performance Comparison. The performance of our proposed MP-QPSO, compared with other state-of-the-art protocols, is summarized in Table 1. The comparison is conducted across several dimensions, including the quantum resources, quantum technologies, party scenarios, supported functionalities (e.g., PSI/PSU or only cardinality), the security level against the TP and parties (collusion), and the communication complexity. Since our Protocol 1 is designed for the multi-party setting and can be straightforwardly extended to MP-QPSU via the open-control described in Section 5.2. More importantly, our framework provides the key distinguishing ability of resisting malicious behaviors

Zixian Gong et al.: Preprint submitted to Elsevier

from the TP, including conspiring between the TP and a threshold number 𝑛𝑡 of parties. Party scenarios: From Table 1, we observe that [SMZ+ 15, DDK+ 21, LRS+ 21, LLW+ 23, MSD+ 24] are restricted to the two-party setting, typically instantiated in a client-server form. The protocols in [ZLS+ 20, CZZ+ 24] target the threeparty setting, whereas only [MD23, HZZ24] and our proposal support the multi-party scenario; Functionality: None of the existing schemes can compute both the intersection and union (PSI&PSU) as our protocol does. Specifically, [SMZ+ 15, DDK+ 21, MD23, MSD+ 24, HZZ24] only support PSI, where [MSD+ 24] further considers threshold PSI that reveals the intersection only when it is large enough. [ZLS+ 20] supports the cardinality of intersection and union (PSI-CA&PSU-CA), while [LRS+ 21, LLW+ 23] provide only PSI-CA. [CZZ+ 24] focuses on a specialized mixed-cardinality functionality like |(𝐴 ∪ 𝐵) ∩ 𝐶|; Security: among the protocols that rely on TP, most adopt a semi-honest TP assumption, although some schemes have attack-resistance or detection mechanisms (e.g., [SMZ+ 15, DDK+ 21, HZZ24]) and most schemes do not address collusion. Only [ZLS+ 20, HZZ24] against collusion which is limited to party-only, these works emphasis that the TP cannot conspire with any party which further highlights another advantage of our MP-QPSO framework: it prevents conspiring between the TP and fewer than a threshold number of parties which is enabled by TFHE.

7. Conclusion Conclusion. In this work, we present Protocol 1, a MPQPSI construction that extends vQFHE to the multi-party

Page 12 of 14

QPSO

setting via TFHE and instantiates the intersection functionality using a 𝐶 𝖠𝖭𝖣 circuit, accompanied by the corresponding quantum circuits and simulations. We then provide a comprehensive analysis of correctness and participant privacy against TP, eavesdroppers, and collusive behaviors, and further establish verifiability against a malicious TP under the semantic security model. Adopting a frameworklevel view, we additionally present several modular realizations of the proposed construction, and show that it can be extended to MP-QPSO via the open-control technique. Finally, we compare our framework with a broad range of existing QPSO schemes, and include Table 1 to highlight our distinguishing advantages in terms of the TP model and collusion resistance: a mechanism to detect TP deviations from the prescribed circuit, as well as resilience against collusion between the TP and a subset of participants. Future work. Although Section 6 and Table 1 indicate that our protocol incurs only a moderate quantum cost, the strong security guarantees inherited from TrapTP [ADS+ 17] lead to a substantially higher classical overhead [LWC+ 25]. This classical–quantum trade-off is largely inherent to QHEbased constructions. Moreover, handling T gates in the evaluated quantum circuit typically requires additional gadget, which increases implementation complexity. Accordingly, our future work will focus on the following directions: (1) leveraging encrypted CNOT operations based on trapdoor claw-free function pairs to avoid gadget-based T-handling and to achieve (2𝑛) quantum communication complexity [Mah18]; (2) redesigning the 𝐶 𝖠𝖭𝖣 circuit to completely eliminate the complexity from T gates; and (3) exploiting the presence of the TA to further relax the quantum capability requirements imposed on all participants.

References [ABC+ 20] Nick Angelou, Ayoub Benaissa, Bogdan Cebere, William Clark, Adam James Hall, Michael A. Hoeh, Daniel Liu, Pavlos Papadopoulos, Robin Roehm, Robert Sandmann, Phillipp Schoppmann, and Tom Titcombe. Asymmetric private set intersection with applications to contact tracing and private vertical federated machine learning. ArXiv, abs/2011.09350, 2020. [ABF+ 16] Gorjan Alagic, Anne Broadbent, Bill Fefferman, Tommaso Gagliardoni, Christian Schaffner, and Michael St. Jules. Computational security of quantum encryption. In Information Theoretic Security, pages 47–71, 2016. [ADS+ 17] Gorjan Alagic, Yfke Dulek, Christian Schaffner, and Florian Speelman. Quantum fully homomorphic encryption with verification. In Advances in Cryptology – ASIACRYPT 2017, pages 438–467, 2017. [AJLA+ 12] Gilad Asharov, Abhishek Jain, Adriana López-Alt, Eran Tromer, Vinod Vaikuntanathan, and Daniel Wichs. Multiparty computation with low communication, computation and interaction via threshold fhe. In Advances in Cryptology – EUROCRYPT 2012, pages 483–501, 2012. [AMR+ 20] Gorjan Alagic, Christian Majenz, Alexander Russell, and Fang Song. Quantum-access-secure message authentication via blind-unforgeability. In Advances in Cryptology – EUROCRYPT 2020, pages 788–817, 2020. [AMT+ 00] A. Ambainis, M. Mosca, A. Tapp, and R. De Wolf. Private quantum channels. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 547–553, 2000.

Zixian Gong et al.: Preprint submitted to Elsevier

[BFS+ 13] Harry Buhrman, Serge Fehr, Christian Schaffner, and Florian Speelman. The garden-hose model. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS ’13, page 145–158, 2013. [BGG+ 18] Dan Boneh, Rosario Gennaro, Steven Goldfeder, Aayush Jain, Sam Kim, Peter M. R. Rasmussen, and Amit Sahai. Threshold cryptosystems from threshold fully homomorphic encryption. In Advances in Cryptology – CRYPTO 2018, pages 565–596, 2018. [BGS13] Anne Broadbent, Gus Gutoski, and Douglas Stebila. Quantum one-time programs. In Advances in Cryptology – CRYPTO 2013, pages 344–360, 2013. [BJ15] Anne Broadbent and Stacey Jeffery. Quantum homomorphic encryption for circuits of low t-gate complexity. In Advances in Cryptology – CRYPTO 2015, pages 609–629, 2015. [Bro18] Anne Broadbent. How to verify a quantum computation. Theory of Computing, 14(11):1–37, 2018. [BW16] Anne Broadbent and Evelyn Wainewright. Efficient simulation for quantum message authentication. In Information Theoretic Security, pages 72–91, 2016. [CGC16] Xiaogang Cheng, Ren Guo, and Yonghong Chen. Cryptanalysis and improvement of a quantum private set intersection protocol. Quantum Information Processing, 16, 2016. [CHZ+ 21] Ji Chu, Xiaoyu He, Yuxuan Zhou, and Jiahao Yuan. et al. Scalable algorithm simplification using quantum and logic. Nature Physics, 19:126–131, 2021. [CLR17] Hao Chen, Kim Laine, and Peter Rindal. Fast private set intersection from homomorphic encryption. Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017. [CZZ+ 24] Yue-Ping Chi, Yu Zhang, Ke Zhang, Gang Xu, and XiuBo Chen. A new protocol for semi-quantum private set of intersection and union mixed cardinality for any tripartite based on bell states. Advanced Quantum Technologies, 7, 2024. [DCGT12] Emiliano De Cristofaro, Paolo Gasti, and Gene Tsudik. Fast and private computation of cardinality of set intersection and union. In Cryptology and Network Security, pages 218–231, 2012. [DDK+ 21] Sumit Kumar Debnath, Kunal Dey, Nibedita Kundu, and Tanmay Choudhury. Feasible private set intersection in quantum domain. Quantum Information Processing, 20, 2021. [DNS12] Frédéric Dupuis, Jesper Buus Nielsen, and Louis Salvail. Actively secure two-party evaluation of any quantum operation. In Advances in Cryptology – CRYPTO 2012, pages 794–811, 2012. [DRR+ 18] Daniel Demmler, Peter Rindal, Mike Rosulek, and Ni Trieu. Pir-psi: Scaling private contact discovery. Proceedings on Privacy Enhancing Technologies, 2018:159 – 178, 2018. [DSS16] Yfke Dulek, Christian Schaffner, and Florian Speelman. Quantum homomorphic encryption for polynomial-sized circuits. In Proceedings, Part III, of the 36th Annual International Cryptology Conference on Advances in Cryptology — CRYPTO 2016 - Volume 9816, page 3–32, 2016. [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. [GC99] Daniel Gottesman and Isaac L. Chuang. Demonstrating the viability of universal quantum computation using teleportation and single-qubit operations. Nature, 402:390–393, 1999. [Gen09] Craig Gentry. Fully homomorphic encryption using ideal lattices. In Symposium on the Theory of Computing, 2009. [GJ21] Craig Gidney and N. Cody Jones. A cccz gate performed with 6 t gates, 2021. [Got09] Daniel Gottesman. An introduction to quantum error correction and fault-tolerant quantum computation. arXiv: Quantum Physics, 2009.

Page 13 of 14

QPSO [HB05] Ulrike Herzog and János A. Bergou. Optimum unambiguous discrimination of two mixed quantum states. Phys. Rev. A, 71:050301, 2005. [HCL+ 24] Renke He, Lingli Chen, Qin Li, Xiaoqing Tan, and Lv Chen. Verifiable quantum homomorphic encryption based on garbled evaluation. Quantum Science and Technology, 9(4):045051, 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. [KRT+ 19] Vladimir Kolesnikov, Mike Rosulek, Ni Trieu, and Xiao Wang. Scalable private set union from symmetric-key techniques. In Advances in Cryptology – ASIACRYPT 2019, pages 636–666, Cham, 2019. Springer International Publishing. [KS05] Lea Kissner and Dawn Song. Privacy-preserving set operations. In Advances in Cryptology – CRYPTO 2005, pages 241–257, 2005. [LK05] Hoi-Kwong Lo and Tsz-Mei Ko. Some attacks on quantumbased cryptographic protocols. Quantum Info. Comput., 5(1):41–48, 2005. [LLW+ 23] Wen Liu, Yangzhi Li, Zhirao Wang, and Yugang Li. A new quantum private protocol for set intersection cardinality based on a quantum homomorphic encryption scheme for toffoli gate. Entropy, 25, 2023. [LRS+ 21] Bai Liu, Ou Ruan, Runhua Shi, and Mingwu Zhang. Quantum private set intersection cardinality based on bloom filter. Scientific Reports, 11, 2021. [LWC+ 25] Qin Li, Yuxun Wang, Lingli Chen, and Lvzhou Li. Verifiable quantum homomorphic encryption. IEEE Journal on Selected Areas in Communications, 43(8):2898–2911, 2025. [Mah18] Urmila Mahadev. Classical homomorphic encryption for quantum circuits. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 332–338, 2018. [MD23] Tapaswini Mohanty and Sumit Kumar Debnath. An information-theoretically secure quantum multiparty private set intersection. J. Inf. Secur. Appl., 78:103623, 2023. [Mea86] Catherine A. Meadows. A more efficient cryptographic matchmaking protocol for use in the absence of a continuously available third party. 1986 IEEE Symposium on Security and Privacy, pages 134–134, 1986. [MSD+ 24] Tapaswini Mohanty, Vikas Srivastava, Sumit Kumar Debnath, Ashok Kumar Das, and Biplab Kumar Sikdar. Quantum secure threshold private set intersection protocol for iot-enabled privacy-preserving ride-sharing application. IEEE Internet of Things Journal, 11:1761–1772, 2024. [PRT+ 20] Benny Pinkas, Mike Rosulek, Ni Trieu, and Avishay Yanai. Psi from paxos: Fast, malicious private set intersection. Advances in Cryptology – EUROCRYPT 2020, 12106:739 – 767, 2020. [PSZ14] Benny Pinkas, T. Schneider, and Michael Zohner. Faster private set intersection based on ot extension. In USENIX Security Symposium, 2014. [RAD78] R. Rivest, L. Adleman, and M. Dertouzos. On data banks and privacy homomorphism. Foundations of Secure Computation, pages 169–179, 1978. [SCW+ 18] Liyan Shen, Xiaojun Chen, Dakui Wang, Binxing Fang, and Ye Dong. Efficient and private set intersection of human genomes. 2018 IEEE International Conference on Bioinformatics and Biomedicine (BIBM), pages 761–764, 2018. [Sha79] Adi Shamir. How to share a secret. Commun. ACM, 22(11):612–613, 1979. [Sho95] Peter W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev., 41:303–332, 1995. [SMZ+ 15] Runhua Shi, Yi Mu, Hong Zhong, Jie Cui, and Shun Zhang. An efficient quantum scheme for private set intersection.

Zixian Gong et al.: Preprint submitted to Elsevier

Quantum Information Processing, 15:363 – 371, 2015. [YPDF14] Li Yu, Carlos A. Pérez-Delgado, and Joseph F. Fitzsimons. Limitations on information-theoretically-secure quantum homomorphic encryption. Phys. Rev. A, 90:050303(R), Nov 2014. [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, 2020.

Page 14 of 14

Related documents

• The security of practical quantum key distribution#6600
• Beyond the Canonical Protocol: Quantum Encrypted Cloning from Secret-Sharing Access Structures#266135
• Privacy in continuous-variable distributed quantum sensing#927158
• One-Way Quantum Symmetric Private Information Retrieval Protocol From A Single Database Server Using NISQ Devices#1157441
• Quantum Meets Statistical-Physical Secrecy: A Novel Hybrid Key Distribution Architecture#196422