Efficient Fuzzy PSI under One-Sided Assumptions

• URL: http://arxiv.org/abs/2608.17770v1
• Date: Tue, 18 Aug 2026 13:32:33 GMT
• Title: Efficient Fuzzy PSI under One-Sided Assumptions
• Abstract summary: 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.
• Score: 22.833285264459548
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Fuzzy private set intersection (PSI) enables two parties to identify approximately matching elements between their input sets, where two elements are considered a match if their distance is at most a threshold $δ$ under a given metric. Although substantial progress has been made, existing constructions for general Minkowski distances either rely on strong two-sided geometric separation assumptions or incur substantial overhead under one-sided assumptions. In this work, we present the first concretely efficient fuzzy PSI protocols for general $L_{p\in[1,\infty]}$ distances under one-sided assumptions, relying solely on lightweight symmetric-key primitives. Our constructions support both sender-sided and receiver-sided settings. We further study sparser input distributions and present more efficient protocols tailored to this case. To reduce the overhead scaling with $δ$, we non-trivially incorporate prefix trie techniques into our protocols, achieving $O(\logδ)$ complexity for general $L_{p\in[1,\infty]}$ distances for the first time, improving upon $O((\logδ)^d)$ or $O(δ)$ complexities of prior works. Extensive experiments, across a wide range of parameter settings, show that our protocols significantly outperform prior works under the same assumptions. Specifically, against van Baarsen and Pu (EUROCRYPT'24), our protocols achieve up to $239\times$ faster computation and up to $20\times$ lower communication. Against Dang et al. (CCS'25), we achieve up to $518\times$ speedup and up to $63\times$ communication reduction. Against Bui et al. (ASIACRYPT'25), we achieve up to $4818\times$ faster computation and up to $282\times$ lower communication.

Related papers

• 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)
• 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)
• Optimizing Explicit Unit-Distance Lower-Bound Certificates [0.0]
  The 2026 disproof of Erds's unit-distance conjecture and Sawin's quantitative refinement show that the maximum number $u(n)$ of unit distances among $n$ planar points can exceed $n1+varepsilon$ for a fixed positive $varepsilon$.<n>This report treats Sawin's parameter selection as a nonlinear integer optimization problem and develops an open-source Python pipeline for certificates involving prime sets $T$ and $S_Q$.
  arXiv  Detail & Related papers  (2026-06-02T10:05:23Z)
• 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)
• Reinforcement Learning from Adversarial Preferences in Tabular MDPs [62.73758165845971]
  We introduce a new framework of episodic Markov decision processes (MDPs) with adversarial preferences.<n>Unlike standard episodic MDPs with adversarial losses, in PbMDPs the learner instead observes preferences between two candidate arms.<n>We develop algorithms that achieve a regret bound of order $T2/3$ under known transitions.
  arXiv  Detail & Related papers  (2025-07-15T20:19:32Z)
• 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)
• Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
  We revisit the input perturbations framework for differential privacy where noise is added to the input $Ain mathcalS$. We first design novel efficient algorithms to privately release pair-wise cosine similarities. We derive a novel algorithm to compute $k$-way marginal queries over $n$ features.
  arXiv  Detail & Related papers  (2024-06-07T12:07:16Z)
• The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning [34.630300910399036]
  We characterize the fundamental communication cost required to obtain the best accuracy under $varepsilon$ central DP. Our results show that $tildeOleft( min(n2varepsilon2, d) right)$ bits per client are both sufficient and necessary. This provides a significant improvement relative to state-of-the-art SecAgg distributed DP schemes.
  arXiv  Detail & Related papers  (2022-03-07T22:56:09Z)
• 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)
• Under-bagging Nearest Neighbors for Imbalanced Classification [63.026765294759876]
  We propose an ensemble learning algorithm called textitunder-bagging $k$-NN (textitunder-bagging $k$-NN) for imbalanced classification problems.
  arXiv  Detail & Related papers  (2021-09-01T14:10:38Z)
• 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.