arXiv CSopen access

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

[email protected] (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.