Ultra-Fast Private Set Intersection From Efficient Oblivious Key-Value Stores
Guowei Ling, Peng Tang, Fei Tang, Shifeng Sun, Shouling Ji, Weidong Qiu · IEEE Transactions on Dependable and Secure Computing · 2025
Private Set Intersection (PSI) enables us to compute the intersection of private sets without leaking additional data. The state-of-the-art PSI protocol$\mathsf {RR22}$(CCS 2022) is derived from an Oblivious Pseudo-Random Function (OPRF) protocol based on Oblivious Key-Value Stores (OKVS). However, the existing OKVS suffers either low computation efficiency or high encoding redundancy. In this work, we propose a new efficient bucket-based OKVS with only 1% redundancy. The encoding algorithm of our OKVS is 4 to 15 times faster than the recent state-of-the-art OKVS (USENIX Security 2023). Specifically, our OKVS can encode$2^{24}$key-value pairs in only 2.1 to 8.5 seconds, corresponding to 30% to 1% redundancy, while the latter takes about 30 seconds with at least 3%. We can then obtain a new ultra-fast PSI protocol with lower communication from our OKVS in both semi-honest and malicious settings. Furthermore, we implemented our PSI protocol and conducted an extensive evaluation, which shows that it outperforms the existing PSI protocols, such as$\mathsf {KKRT16}$(CCS 2016),$\mathsf {CM20}$(Crypto 2020),$\mathsf {RS21}$(EuroCrypt 2021),$\mathsf {RR22}$(CCS 2022), and$\mathsf {KBM23}$(NDSS 2023). Since our PSI features an ultra-low communication overhead, it has overall advantages for the network environment with a small bandwidth. For example, our PSI takes only about 468 and 476 seconds in semi-honest and malicious settings with the input size of$2^{24}$when the bandwidth is 10 Mbps, while the state-of-the-art$\mathsf {RR22}$requires about 541 and 625 seconds. Our implementation is available onhttps://github.com/ShallMate/fastpsi.