Guowei Ling (Shanghai Jiaotong University), Peng Tang (Shanghai Jiao Tong University), Jinyong Shan (Beijing Smartchip Microelectronics Technology Co., Ltd.), Liyao Xiang (Shanghai Jiao Tong University), Weidong Qiu (School of Cyber Science and Engineering, Shanghai Jiao Tong University, China)
In this work, we present a new lightweight two-party Private Set Intersection (PSI) paradigm in both the semi-honest and malicious models. It requires only a small number of base OTs and a single Oblivious Key-Value Stores (OKVS) encoding and decoding. All computations (except for the base OTs) can be implemented using SIMD-accelerated symmetric cryptographic instructions and efficient 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 show that the proposed PSI outperforms the most efficient VOLE-based PSI by approximately 40% in runtime, while consistently incurring lower communication overhead under the same settings. For circuit PSI, it is up to $3.7times$ faster and reduces communication by a factor of $1.5$ compared to VOLE-based circuit PSI constructions. In the cases of PSI-cardinality and PSI-sum, it achieves speedups of up to $12.4times$ and $10times$, respectively, while incurring only moderate communication overhead. For PJC, the proposed protocol outperforms prior work by $762times$ in runtime and achieves a $3.2times$ reduction in communication, maintaining high efficiency even under a low-bandwidth condition.