Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching

• URL: http://arxiv.org/abs/2608.11526v1
• Date: Wed, 12 Aug 2026 00:30:53 GMT
• Title: Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching
• Abstract summary: We present fuzzy PSI protocols for general $L_p in [1, infty]$ distance, supporting both low- and high-dimensional sets.<n>The first is built from a role-reversed oblivious PRF (OPRF) and realizes $O(dlog )$ overhead, compared to $O(log )d)$ in previous works.<n>The second leverages customized oblivious transfer (OT) with $O(dell)$ overhead, where $ell$ is the bit length of inputs.
• Score: 43.14972106243527
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we present scalable fuzzy PSI protocols for general $L_{p \in [1, \infty]}$ distance, supporting both low- and high-dimensional sets. The core technique is two efficient fuzzy matching protocols. The first is built from a role-reversed oblivious PRF (OPRF) and realizes $O(d\log δ)$ overhead, compared to $O((\log δ)^d)$ in previous works. The second leverages customized oblivious transfer (OT) with $O(d\ell)$ overhead, where $\ell$ 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 $n, m, \log δ, 2^d$, without the $O((\log δ)^d)$ or $O(δ)$ 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 $n, m, d$, and $\log δ$ but rely on the strong globally disjoint assumption.} Extensive evaluations demonstrate that our protocols achieve up to a $145\times$ speedup in running time and a $20\times$ reduction in communication cost compared to van Baarsen and Pu~(ASIACRYPT'25), and achieve up to a $25\times$ speedup in running time and up to a $17\times$ reduction in communication cost compared to Piske et al.~(CCS'25).

Related papers

• Efficient Fuzzy PSI under One-Sided Assumptions [22.833285264459548]
  Fuzzy private set intersection (PSI) enables two parties to identify approximately matching elements between their input sets.<n>We present the first concretely efficient fuzzy PSI protocols for general $L_pin[1,infty]$ distances under one-sided assumptions.<n>Our protocols achieve up to $239times$ faster computation and up to $20times$ lower communication.
  arXiv  Detail & Related papers  (2026-08-18T13:32:33Z)
• Computationally Efficient Collaborative Communication Via Regularity-Based Coarsening [26.60272178029048]
  We show a protocol achieving utility at least $- using only $2mathcal O(CC_(G))/2$ bits of communication.<n>We note that our results strictly weaken the assumptions required by prior work in the multi-agent information aggregation literature.
  arXiv  Detail & Related papers  (2026-08-05T18:34:19Z)
• Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold [14.99063187700722]
  We present new FPSI protocols for $L_pin[1,infty]$ distances that are entirely built from oblivious transfer (OT) and symmetric-key primitives.<n>Our protocols outperform the prior state-of-the-art by up to $43.7times$ in runtime and $31.3times$ in communication.
  arXiv  Detail & Related papers  (2026-06-13T03:59:35Z)
• Efficient Fuzzy Private Set Intersection from Secret-shared OPRF [41.88845480337768]
  Fuzzy PSI (FPSI) is a PSI variant where the receiver learns the items $q in Q$ for which there exists some $w in W$ under a given distance metric.<n>We propose efficient FPSI protocols for $L_p in [1, infty]$ distance metrics.<n>Our protocols achieve linear communication and computation complexity in the set sizes $m,n$, the dimension $d$, and the distance threshold $$.
  arXiv  Detail & Related papers  (2026-04-16T11:51:25Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  We consider a centralized distributed learning setup where all workers jointly find an unbiased bound LDeltaepsilon2,$ better poly-logarithmically in $n$, even in the homogeneous (i.i.d.) case, where all workers access the same distribution.
  arXiv  Detail & Related papers  (2025-06-30T13:27:39Z)
• Sign Operator for Coping with Heavy-Tailed Noise in Non-Convex Optimization: High Probability Bounds Under $(L_0, L_1)$-Smoothness [74.18546828528298]
  We show that SignSGD with Majority Voting can robustly work on the whole range of complexity with $kappakappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappakappakappa-1right, kappa
  arXiv  Detail & Related papers  (2025-02-11T19:54:11Z)
• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  We study multiclass PAC learning with bandit feedback, where inputs are classified into one of $K$ possible labels and feedback is limited to whether or not the predicted labels are correct. Our main contribution is in designing a novel learning algorithm for the agnostic $(varepsilon,delta)$PAC version of the problem.
  arXiv  Detail & Related papers  (2024-06-18T08:54:04Z)
• Transfer Q Star: Principled Decoding for LLM Alignment [105.89114186982972]
  Transfer $Q*$ estimates the optimal value function for a target reward $r$ through a baseline model. Our approach significantly reduces the sub-optimality gap observed in prior SoTA methods.
  arXiv  Detail & Related papers  (2024-05-30T21:36:12Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  We study the Shortest Path (SSP) problem with a linear mixture transition kernel. An agent repeatedly interacts with a environment and seeks to reach certain goal state while minimizing the cumulative cost. Existing works often assume a strictly positive lower bound of the iteration cost function or an upper bound of the expected length for the optimal policy.
  arXiv  Detail & Related papers  (2024-02-14T07:52:00Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• A general approximation lower bound in $L^p$ norm, with applications to feed-forward neural networks [0.0]
  We study the fundamental limits to the expressive power of neural networks. We first prove a general lower bound on how well functions in $F$ can be approximated in $Lp(mu)$ norm. We then instantiate this bound to the case where $G$ corresponds to a piecewise-polynomial feed-forward neural network.
  arXiv  Detail & Related papers  (2022-06-09T09:01:05Z)
• On Unbalanced Optimal Transport: Gradient Methods, Sparsity and Approximation Error [18.19398247972205]
  We study the Unbalanced Optimal Transport (UOT) between two measures of possibly different masses with at most $n$ components. We propose a novel algorithm based on Gradient Extrapolation Method (GEM-UOT) to find an $varepsilon$-approximate solution to the UOT problem.
  arXiv  Detail & Related papers  (2022-02-08T03:22:39Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  We study the setup where each of $n$ users holds an element from a discrete set. The goal is to count the number of distinct elements across all users.
  arXiv  Detail & Related papers  (2020-09-21T04:13:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.