Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold

• URL: http://arxiv.org/abs/2606.15093v1
• Date: Sat, 13 Jun 2026 03:59:35 GMT
• Title: Fuzzy PSI from Symmetric Primitives with Exact Logarithmic Dependence on Distance Threshold
• Abstract summary: 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.
• Score: 14.99063187700722
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Previous FPSI works have demonstrated a linear scaling with the distance threshold $δ$, while some recent works have achieved a poly-logarithmic dependence on $δ$. 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 $δ$ for general $L_{p\in[1,\infty]}$ distances without relying on costly AHE would constitute a theoretical breakthrough in optimal threshold scaling and a practical advance toward scalable FPSI applications. In this work, we present new FPSI protocols for $L_{p\in[1,\infty]}$ distances that are entirely built from oblivious transfer (OT) and symmetric-key primitives. We propose FPSI protocols based on both the apart and the separate assumptions, which are applicable to low- and high-dimensional settings, respectively. Our constructions achieve strictly logarithmic complexity in $δ$, which is optimal in the sense that distinguishing all values in an interval of length $O(δ)$ necessarily requires $Ω(\log δ)$ bits of information. Our core idea is to perform fuzzy matching via prefix representation and interactively determine the correct prefix using equality conditions. To this end, we propose a suite of new components that can be implemented efficiently using only OT and symmetric-key operations. We implement our FPSI protocols and compare them with the state-of-the-art FPSI protocols for $L_{p\in[1,\infty]}$ distance. Experiments show that our protocols outperform the prior state-of-the-art by up to $43.7\times$ in runtime and $31.3\times$ in communication.

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)
• 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)
• 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)
• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  We introduce a new family of distances, relative-translation invariant Wasserstein distances ($RW_p$) We show that $RW_p distances are also real distance metrics defined on the quotient set $mathcalP_p(mathbbRn)/sim$ invariant to distribution translations.
  arXiv  Detail & Related papers  (2024-09-04T03:41:44Z)
• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  We give a conceptually simple quantum linear system solvers (QLSS) that does not use complex or difficult-to-analyze techniques. If the solution norm $lVertboldsymbolxrVert$ is known exactly, our QLSS requires only a single application of kernel. Alternatively, by reintroducing a concept from the adiabatic path-following technique, we show that $O(kappa)$ complexity can be achieved for norm estimation.
  arXiv  Detail & Related papers  (2024-06-17T20:54:11Z)
• 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)
• Policy Zooming: Adaptive Discretization-based Infinite-Horizon Average-Reward Reinforcement Learning [2.2984209387877628]
  We study Lipschitz MDPs in the infinite-horizon average-reward reinforcement learning (RL) setup.<n>We upper bound their regret as $tildemathcalObig(T1 - d_texteff.-1big)$, where $d_texteff. = dPhi_z+2$ for model-free algorithmtextitPZRL-MF and $d_texteff. = 2d_mathcalS + dPhi_z + 3$ for
  arXiv  Detail & Related papers  (2024-05-29T06:18:09Z)
• Spacetime-Efficient Low-Depth Quantum State Preparation with Applications [93.56766264306764]
  We show that a novel deterministic method for preparing arbitrary quantum states requires fewer quantum resources than previous methods. We highlight several applications where this ability would be useful, including quantum machine learning, Hamiltonian simulation, and solving linear systems of equations.
  arXiv  Detail & Related papers  (2023-03-03T18:23:20Z)
• 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)
• 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)
• 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)
• Improved Sample Complexity for Incremental Autonomous Exploration in MDPs [132.88757893161699]
  We learn the set of $epsilon$-optimal goal-conditioned policies attaining all states that are incrementally reachable within $L$ steps. DisCo is the first algorithm that can return an $epsilon/c_min$-optimal policy for any cost-sensitive shortest-path problem.
  arXiv  Detail & Related papers  (2020-12-29T14:06:09Z)
• 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.