Efficient Fuzzy Private Set Intersection from Secret-shared OPRF

• URL: http://arxiv.org/abs/2604.14909v1
• Date: Thu, 16 Apr 2026 11:51:25 GMT
• Title: Efficient Fuzzy Private Set Intersection from Secret-shared OPRF
• Abstract summary: 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 $$.
• Score: 41.88845480337768
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Private set intersection (PSI) enables a sender holding a set $Q$ of size $m$ and a receiver holding a set $W$ of size $n$ to securely compute the intersection $Q \cap W$. Fuzzy PSI (FPSI) is a PSI variant where the receiver learns the items $q \in Q$ for which there exists some $w \in W$ satisfying $\mathsf{dist}(q, w) \le δ$ under a given distance metric. Although several FPSI works are proposed for $L_{p}$ distance metrics with $p \in [1, \infty]$, they either heavily rely on expensive homomorphic encryptions, or incur undesirable complexity, e.g., exponential to the element dimension, both of which lead to poor practical efficiency. In this work, we propose efficient FPSI protocols for $L_{p \in [1, \infty]}$ distance metrics, primarily leveraging significantly cheaper symmetric-key operations. Our protocols achieve linear communication and computation complexity in the set sizes $m,n$, the dimension $d$, and the distance threshold $δ$. Our core building block is an oblivious programmable PRF with secret-shared outputs, which may be of independent interest. Furthermore, we incorporate a prefix technique that reduces the dependence on the distance threshold $δ$ to logarithmic, which is particularly suitable for large $δ$. We implement our FPSI protocols and compare them with state-of-the-art constructions. Experimental results demonstrate that our protocols consistently and significantly outperform existing works across all settings. Specifically, our protocols achieve a speedup of $12{\sim}145\times$ in running time and a reduction of $3{\sim}8\times$ in communication cost compared to Gao et al.~(ASIACRYPT'24) and a speedup of $9{\sim}80\times$ in running time and a reduction of $5{\sim}19\times$ in communication cost compared to Dang 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)
• Towards Scalable Fuzzy PSI via Efficient Fuzzy Matching [43.14972106243527]
  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.
  arXiv  Detail & Related papers  (2026-08-12T00:30:53Z)
• 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)
• Scaling Federated Linear Contextual Bandits via Sketching [49.12000877146222]
  This paper proposes Federated Sketch Contextual Linear Bandits (FSCLB)<n>Experiments on both synthetic and real-world datasets show that FSCLB significantly reduces computational and communication costs by over 90 %.
  arXiv  Detail & Related papers  (2026-05-01T08:22:06Z)
• Fuzzy Private Set Union via Oblivious Key Homomorphic Encryption Retrieval [0.30586855806896035]
  Private Set Union (PSU), resp. Intersection (PSI), is a protocol that allows parties to compute the union, resp. the intersection, between their private sets.<n>We present in this paper, Fuzzy PSU protocols (FPSU), able to efficiently take into account approximations in the union.
  arXiv  Detail & Related papers  (2026-01-28T09:05:35Z)
• Efficient and High-Accuracy Secure Two-Party Protocols for a Class of Functions with Real-number Inputs [8.447031280935965]
  In two-party secret sharing scheme, values are encoded as unsigned integers $mathsfuint(x)$, whereas real-world applications often require computations on signed real numbers $mathsfReal(x)$.<n>In this work, we relax this constraint to $|x| B$ for any $B leq fracL2$, where $B = fracL2$ corresponding to the natural representable range in $x in mathbbZ_L$.
  arXiv  Detail & Related papers  (2025-09-01T06:56:29Z)
• 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)
• Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces [2.687607197645453]
  We show that even the special case of $k$-Center in dimension $Theta(log n)$ is $(sqrt3/2- o(1))$hard to approximate for FPT algorithms. We also show that even the special case of $k$-Center in dimension $Theta(log n)$ is $(sqrt3/2- o(1))$hard to approximate for FPT algorithms.
  arXiv  Detail & Related papers  (2023-05-12T08:43:28Z)
• Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP [58.13930707612128]
  This work considers the sample complexity of obtaining an $varepsilon$-optimal policy in an average reward Markov Decision Process (AMDP) We prove an upper bound of $widetilde O(H varepsilon-3 ln frac1delta)$ samples per state-action pair, where $H := sp(h*)$ is the span of bias of any optimal policy, $varepsilon$ is the accuracy and $delta$ is the failure probability.
  arXiv  Detail & Related papers  (2022-12-01T15:57:58Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  One of its most powerful and successful modalities approximates every distribution to an $ell$ distance essentially at most a constant times larger than its closest $t$-piece degree-$d_$. We provide a method that estimates this number near-optimally, hence helps approach the best possible approximation.
  arXiv  Detail & Related papers  (2022-02-15T03:49:28Z)
• Sampling from Log-Concave Distributions with Infinity-Distance Guarantees and Applications to Differentially Private Optimization [33.38289436686841]
  We present an algorithm that outputs a point from a distributionO(varepsilon)$close to $$ in infinity-distance. We also present a "soft-pi" version of the Dikin walk which may be independent interest.
  arXiv  Detail & Related papers  (2021-11-07T13:44:50Z)
• Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
  We study the reward-free reinforcement learning framework, which is particularly suitable for batch reinforcement learning and scenarios where one needs policies for multiple reward functions. We give a new efficient algorithm, textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname), which interacts with the environment at most $Oleft( fracS2Aepsilon2textpolylogleft(fracSAHepsilon2
  arXiv  Detail & Related papers  (2020-10-12T17:51:19Z)
• 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)
• Fixed-Support Wasserstein Barycenters: Computational Hardness and Fast Algorithm [100.11971836788437]
  We study the fixed-support Wasserstein barycenter problem (FS-WBP) We develop a provably fast textitdeterministic variant of the celebrated iterative Bregman projection (IBP) algorithm, named textscFastIBP.
  arXiv  Detail & Related papers  (2020-02-12T03:40:52Z)

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.