Faster Than Ever: A New Lightweight Private Set Intersection and Its Variants

In this work, we present a new lightweight twoparty Private Set Intersection (PSI) paradigm in both the semihonest and malicious models. It requires only a small number of base Oblivious Transfers (OTs), along with a single Oblivious Key-Value Store (OKVS) encoding and a number of decodings equal to the sender input size. All computations (except for the base OTs) can be implemented using efficient hash and bitwise operations. Furthermore, we extend the proposed PSI protocol to circuit PSI and, subsequently, to several PSI variants, including PSI-cardinality, PSI-sum, and Private Join and Compute (PJC). All proposed protocols are evaluated under both LAN and WAN settings, with performance compared against existing works. Experimental results demonstrate that the proposed PSI achieves about 1.5× faster runtime than the most efficient Vector Oblivious Linear Evaluation (VOLE)-based PSI, while maintaining consistently lower communication overhead under identical settings. For circuit PSI, it is up to 3.6× faster and reduces communication by a factor of 1.5 compared to VOLEbased circuit PSI constructions. In the cases of PSI-cardinality and PSI-sum, they achieve speedups of up to 12.2× and 10×, respectively, while incurring only moderate communication overhead. For PJC, the proposed protocol outperforms prior work by 731× in runtime and achieves a 3.2× reduction in communication, maintaining high efficiency even under a lowbandwidth condition. The performance under the unbalanced setting is also evaluated, showing that our PSI achieves at most two orders of magnitude improvement in the LAN setting compared with existing unbalanced PSI protocols, and gradually gains superiority under the WAN setting as the receiver set size increases.