More Efficient, Privacy-Enhanced, and Powerful Privacy-Preserving Feature Retrieval Private Set Intersection

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 (P<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>FRPSI) is a variant of PSI. In P<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>FRPSI, 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 P<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>FRPSI protocol reveals the output size and the original intersection size to the sender. We also observed that the existing P<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>FRPSI 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 P<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>FRPSI protocols, one based on DH key agreement and the other based on OPRF, to fully address the issues present in existing P<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>FRPSI protocols. Our DH-based P<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>FRPSI is 30× faster than the existing DH-based protocol, with only a 36% increase in communication overhead. Furthermore, our OPRF-based P<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>FRPSI protocol is 2× as fast as existing OPRF-based protocol and reduces communication overhead by a factor of 4.6. Our DH-based P<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>FRPSI 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.