Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

In fuzzy private set intersection (fuzzy PSI), there are two parties, a sender holding a set of 𝑑-dimensional points 𝑄 = 𝒒 1 , . . . , 𝒒 𝑚 and a receiver holding a set 𝑊 = 𝒘 1 , . . . , 𝒘 𝑛 of the same structure. It enables the receiver to learn the point 𝒒 ∈ 𝑄 for which there exists some 𝒘 ∈ 𝑊 satisfying dist(𝒒, 𝒘) ≤ 𝛿 under a given distance metric. Although several fuzzy PSI protocols for 𝐿 𝑝 ∈ [1,∞] distance are proposed, there are significant efficiency issues, mainly because they (1) heavily rely on expensive cryptographic primitives, e.g., homomorphic encryption or garble circuits, and/or (2) incur undesirable asymptotic communication and computation complexity. In this paper, we present scalable fuzzy PSI protocols for general 𝐿 𝑝 ∈ [1,∞] distance, supporting both low-and high-dimensional sets. The core technique is two efficient fuzzy matching protocols that securely evaluate dist(𝒒, 𝒘) ≤ 𝛿. The first is built from a role-reversed oblivious PRF (OPRF) and realizes 𝑂 (𝑑 log 𝛿) overhead, compared to 𝑂 ((log 𝛿) 𝑑 ) in previous works. The second leverages customized oblivious transfer (OT) with 𝑂 (𝑑ℓ) overhead, where ℓ is the bit length of inputs, which is particularly suitable for short inputs. With these new techniques, we further propose a new dual-layer hashing framework for fuzzy PSI over low-dimensional sets, instantiated with our OT-based fuzzy matching and enhanced with a domain reduction optimization. The protocols achieve an overhead linear with 𝑛, 𝑚, log 𝛿, 2 𝑑 , without the 𝑂 ((log 𝛿) 𝑑 ) or 𝑂 (𝛿) factors present in prior works. For high-dimensional sets, we construct fuzzy PSI protocols based on our OPRF-and OT-based fuzzy matching, which achieve an asymptotic overhead linear with 𝑛, 𝑚, 𝑑, and log 𝛿 but rely on the strong globally disjoint assumption.