Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold (opens in new tab)

Previous FPSI works have demonstrated a linear scaling with the distance threshold $\delta$, while some recent works have achieved a poly-logarithmic dependence on $\delta$. However, these protocols either support only the $L_\infty$ distance, or they support general $L_{p\in[1,\infty]}$ distances but rely on expensive additive homomorphic encryption (AHE). Achieving exact logarithmic dependence on $\delta$ for general $L_{p\in[1,\infty]}$ dista...