Fuzzy Private Set Intersection (FPSI) is a cryptographic protocol that extends traditional PSI to enable privacy-preserving similarity matching, allowing the receiver to learn elements from the sender’s set with "δ − close" of the receiver’s elements, computing {yj| dist(xi, yj) ≤ δ, xi∈ X, yj∈ Y } where δ is predefined threshold. However, the current state-of-the-art integer-based approach by Chakraborti et al. (USENIX’23) suffers from excessive computation overhead, large communication costs, and limited scalability, hindering practical deployment.We construct two semi-honest $\Pi _{{\text{FPSI}}}^{{\text{int}}}$ for different scenarios. Along with compact Prefix Trie preprocessing, for the balanced settings, we propose $\Pi _{{\text{FPSI}}}^{{\text{OKVS}}}$ leveraging OKVS and subVOLE. For unbalanced scenarios, we introduce $\Pi _{{\text{FPSI}}}^{{\text{HE}}}$ protocol combining optimization techniques including Paterson-Stockmeyer algorithms and multiple algorithmic improvements.We implement our protocols in C++ using 32-bit IPv4 and 128-bit IPv6 addresses across balanced and unbalanced scenarios under single-threaded LAN environment. our balanced $\Pi _{{\text{FPSI}}}^{{\text{OKVS}}}$ protocol achieves 24.7-58.4× computational speedup across all scales and 9.9× communication reduction compared to Chakraborti et al. (USENIX'23) for datasets up to 1 million addresses. For unbalanced scenarios, our $\Pi _{{\text{FPSI}}}^{{\text{HE}}}$ protocol demonstrates superior scalability, enabling mobile devices with only 4K datasets against 16 million server elements in 56.74 seconds with 22.8 MB communication, achieving 2.8-38.5× speedup over the (USENIX'23).

Permutations with low multiplication depth over prime fields are highly valuable in the design of symmetric ciphers that are compatible with fully homomorphic encryption (FHE). Quadratic permutations, which have the lowest depth, have been widely used in prior designs. In this paper, we propose a construction method that can give new quadratic permutations over Fpm, and cryptographic properties such as differential uniformity and Walsh spectrum of these permutations are also characterized. We give sufficient conditions for permutations over Fpnto attain a differential uniformity ofpn−1forn≥ 3. Furthermore, it is proven that for these permutations, the maximal 2-norm of Walsh coefficients remains bounded bypn−1, provided either the lastn− 1 entries of the input mask or the lastn− 1 entries of the output mask form a nonzero vector. As an application, we design a new FHE-friendly stream cipher named YuS based on a new quadratic permutation over Fp3and a fixed linear mapping. According to our implementation, achieves YuS faster evaluation times and higher throughput compared to Masta, Pasta, Pastav2and HERA in almost all instances for both BGV and BFV schemes at 80-bit and 128-bit security levels.