Weizhan Jing, Xiaojun Chen, Xudong Chen, Ye Dong, Qiang Liu, Tingyu Fan · Cybersecurity · 2026

JAGUAR: efficient and secure unbalanced PSI under malicious adversaries in the client–server setting

Resumo em português

RESUMO Em muitas aplicações de interseção de conjuntos privados não balanceada (uPSI) no cenário cliente-servidor, o servidor precisa realizar uPSI com múltiplos clientes. Cong et al. (ACM CCS’21) propuseram um protocolo uPSI estado-da-arte (SOTA) baseado em criptografia totalmente homomórfica (FHE), alcançando segurança contra adversários maliciosos ao empregar uma função pseudoaleatória obliterada (OPRF) na fase de pré-processamento. Contudo, reexecutar os protocolos uPSI existentes com cada cliente impõe uma sobrecarga computacional significativa para o servidor. Neste artigo, apresentamos JAGUAR, um protocolo uPSI maliciosamente seguro e eficiente projetado para esse cenário. JAGUAR reduz a computação online através de uma otimização Dividir-e-Combinar, exigindo apenas $$\mathcal{O}(\sqrt{|X|})$$ multiplicações homomórficas. Além disso, utiliza uma nova OPRF baseada em VOLE fixo que permite pré-processamento reutilizável e leve para múltiplos clientes. Resultados experimentais demonstram que JAGUAR alcança até $$2,7\times$$ de melhoria no tempo de execução online em comparação com o protocolo SOTA em LAN. Em cenários com múltiplos clientes, JAGUAR supera ainda mais os protocolos existentes em termos de escalabilidade e desempenho geral.

Resumo original em inglês

Abstract In many unbalanced private set intersection (uPSI) applications of the client–server setting, the server needs to perform uPSI with multiple clients. Cong et al. (ACM CCS’21) proposed a state-of-the-art (SOTA) uPSI protocol based on fully homomorphic encryption (FHE), achieving malicious security by employing an oblivious pseudorandom function (OPRF) in the pre-processing phase. However, re-executing existing uPSI protocols with each client imposes significant computational overhead for the server. In this paper, we present JAGUAR, a maliciously secure and efficient uPSI protocol designed for this setting. JAGUAR reduces online computation through a Divide-and-Combine optimization, requiring only $${\mathcal {O}}(\sqrt{|X|})$$ O ( | X | ) homomorphic multiplications. Furthermore, it employs a novel fixed VOLE-based OPRF that enables reusable and lightweight pre-processing across multiple clients. Experimental results demonstrate that JAGUAR achieves up to $$2.7\times$$ 2.7 × improvement in online runtime compared to the SOTA protocol in LAN. In multi-client scenarios, JAGUAR further outperforms existing protocols by a wide margin in terms of scalability and overall performance.