Fuzzy Private Set Intersection under Density-Bounded Assumptions

본문 미리보기

This paper presents a new fuzzy private set intersection (FPSI) protocol, a two-party protocol to securely identify similar items across private sets. Our design departs from the prevailing separation-based paradigm---e.g., ``apart by $2\delta$'' or the disjoint projection assumption---which either incurs exponential overhead in dimensionality or requires high dimensionality to justify the assumption. Instead, we address this tension by explicitly allowing collisions within $\delta$-balls, but r