Paper 2026/1436

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

Abstract

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 \(C^{\mathsf{AND}}\) 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 open-controlled 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.