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.

Private set intersection (PSI) allows two participants to compute the intersection of their private sets without revealing any additional information beyond the intersection itself. It is known that oblivious linear evaluation (OLE) can be used to construct the online efficient PSI protocol. However, oblivious transfer (OT) and fully homomorphic encryption (FHE)-based offline OLE generation are expensive, and the online computational complexity is super-linear and still a heavy burden for large-scale sets. In this paper, we propose VCR, an efficient PSI protocol from vector OLE (VOLE) with the offline-online paradigm. Concretely, we first propose the batched short VOLE protocol to reduce offline overhead for generating VOLE tuples. Then, we design a batched private membership test protocol from pre-computed VOLE to accelerate the online computation. Experiments demonstrate that VCR outperforms prior art. Compared to state-of-the-art work, we reduce the total communication costs (resp. running time) by 341× and 9.1× (resp. 6.5× and 2.5×) on average for OT and FHE-based protocols.

With the widespread deployment of Deep-Learning-as-a-Service, secure multi-party computation-based outsourcing neural network (NN) inference has garnered significant attention for its high-security guarantee. Nevertheless, under the dishonest-majority setting with malicious adversaries, prior secure inference works are still costly in terms of communication and run-time. Additionally, existing outsourcing frameworks impose a substantial client-side design, which leads to obstacles in resource-constrained devices. To address the above challenges, we propose MD-SONIC, an online efficient and maliciously-secure framework for outsourcing NN inference with a dishonest majority. We first construct communication-efficient n-party protocols for the basic primitives such as fixed-point multiplication and most significant bit extraction by combining mask-sharing and TinyOT-sharing with SPD$\mathbb {Z}_{2^{k}}$seamlessly. Then, we build fast secure blocks for the widely used NN operators, including matrix multiplication, ReLU, and Maxpool, on top of our basic primitives. To enable an arbitrary number of users to outsource the secure inference task to n computing servers, we propose a lightweight-client and fast$\Sigma $paradigm named SPIN, stemming from zero-knowledge proofs. Our SPIN can be instantiated into a set of efficient outsourcing protocols over multiple algebraic structures (e.g., finite field and ring). We also conduct extensive evaluations of MD-SONIC on various neural networks. Compared to the work by Damgård et al. (IEEE S&P’19) and MD-ML (USENIX Security’24), we achieve up to$594.4\times $and$45.1\times $online communication improvements, and improve the online execution time by at most$14.3\times $(resp.$20.5\times $) and$1.8\times $(resp.$2.3\times $) in LAN (resp. WAN).