Fast and Fuzzy Private Set Intersection
This work addresses the need for efficient and scalable PSI in privacy-preserving applications, though it is incremental as it builds on existing PSI concepts by introducing a trade-off between speed and accuracy.
The authors tackled the problem of Private Set Intersection (PSI) by proposing a simpler method where each set is encrypted only once, enabling faster comparisons between user pairs at the cost of some fuzziness in matching. They demonstrated this approach with English words processed using WordNet, achieving orders of magnitude speed improvements over ordinary PSI.
Private Set Intersection (PSI) is usually implemented as a sequence of encryption rounds between pairs of users, whereas the present work implements PSI in a simpler fashion: each set only needs to be encrypted once, after which each pair of users need only one ordinary set comparison. This is typically orders of magnitude faster than ordinary PSI at the cost of some ``fuzziness" in the matching, which may nonetheless be tolerable or even desirable. This is demonstrated in the case where the sets consist of English words processed with WordNet.