More Efficient, Privacy-Enhanced, and Powerful Privacy-Preserving Feature Retrieval Private Set Intersection
Guowei Ling, Peng Tang, Jinyong Shan, Fei Tang, Weidong Qiu · IEEE Transactions on Information Forensics and Security · 2025
Private Set Intersection (PSI) allows two parties, the sender and the receiver, each possessing a private set, to compute the intersection of their sets, with only the receiver learning the intersection and without revealing any additional information. Privacy-Preserving Feature Retrieval PSI (P2FRPSI) is a variant of PSI. In P2FRPSI, the receiver designs a predicate and obtains the intersection of private sets that satisfy this predicate, while the sender learns nothing about the predicate. However, the existing two PRFPSI protocols (TIFS 2024), based respectively on the DH key agreement and Oblivious Pseudo- Random Function (OPRF), are not highly efficient due to their reliance on expensive homomorphic encryption. Moreover, the existing DH-based P2FRPSI protocol reveals the output size and the original intersection size to the sender. We also observed that the existing P2FRPSI protocols do not support threshold retrieval and the logical connective OR and can only work when feature values of the sender have very low dimensionality. This paper also proposes two new P2FRPSI protocols, one based on DH key agreement and the other based on OPRF, to fully address the issues present in existing P2FRPSI protocols. Our DH-based P2FRPSI is 30× faster than the existing DH-based protocol, with only a 36% increase in communication overhead. Furthermore, our OPRF-based P2FRPSI protocol is 2× as fast as existing OPRF-based protocol and reduces communication overhead by a factor of 4.6. Our DH-based P2FRPSI protocol completely eliminates the leakage of the original intersection size and the output size. Meanwhile, our protocols support the logical connective OR for linking sub-predicates and also enable threshold-based retrieval. They are proven to be secure in the semi-honest model. Our open-source implementations can be found at https://github.com/ShallMate/pfrpsi, which can help readers understand our protocols and reproduce the experiments.