Fuzzy Private Set Union via Oblivious Key Homomorphic Encryption Retrieval

• URL: http://arxiv.org/abs/2601.20400v1
• Date: Wed, 28 Jan 2026 09:05:35 GMT
• Title: Fuzzy Private Set Union via Oblivious Key Homomorphic Encryption Retrieval
• Abstract summary: 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.
• Score: 0.30586855806896035
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Private Set Multi-Party Computations are protocols that allow parties to jointly and securely compute functions: apart from what is deducible from the output of the function, the input sets are kept private. Then, a Private Set Union (PSU), resp. Intersection (PSI), is a protocol that allows parties to jointly compute the union, resp. the intersection, between their private sets. Now a structured PSI, is a PSI where some structure of the sets can allow for more efficient protocols. For instance in Fuzzy PSI, elements only need to be close enough, instead of equal, to be part of the intersection. We present in this paper, Fuzzy PSU protocols (FPSU), able to efficiently take into account approximations in the union. For this, we introduce a new efficient sub-protocol, called Oblivious Key Homomorphic Encryption Retrieval (OKHER), improving on Oblivious Key-Value Retrieval (OKVR) techniques in our setting. In the fuzzy context, the receiver set $X=\{x_i\}_{1..n}$ is replaced by ${\mathcal B}_δ(X)$, the union of $n$ balls of dimension $d$ with radius $δ$, centered at the $x_i$. The sender set is just its $m$ points of dimension $d$. Then the FPSU functionality corresponds to $X \sqcup \{y \in Y, y \notin {\mathcal B}_δ(X)\}$. Thus, we formally define the FPSU functionality and security properties, and propose several protocols tuned to the patterns of the balls using the $l_\infty$ distance. Using our OKHER routine and homomorphic encryption, we are for instance able to obtain a FPSU protocols with an asymptotic communication volume bound ranging from $O(dm\log(δ{n}))$ to $O(d^2m\log(δ^2n))$, depending on the receiver data set structure.

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)
• 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)
• DP-CSGP: Differentially Private Stochastic Gradient Push with Compressed Communication [71.60998478544028]
  We propose Differentially Private Gradient Push with Compressed communication (termedfrac-CSGP) for decentralized learning graphs.<n>For general non-math and smooth objective functions, we show that our algorithm is designed to maintain high accuracy and efficient communication.
  arXiv  Detail & Related papers  (2025-12-15T17:37:02Z)
• 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)
• Private Synthetic Data Generation in Small Memory [16.298974544454754]
  $mathttPrivHP$ is a lightweight synthetic data generator with textitdifferential privacy guarantees.<n>It balances hierarchy depth, noise addition, and pruning of low-frequency while preserving frequent ones.
  arXiv  Detail & Related papers  (2024-12-12T23:24:05Z)
• Dictionary-based Block Encoding of Sparse Matrices with Low Subnormalization and Circuit Depth [2.4487770108795393]
  We propose an efficient block-encoding protocol for sparse matrices based on a novel data structure.<n>Non-zero elements with the same values belong to the same classification in our block-encoding protocol's dictionary.<n>Our protocol connects to linear combinations of unitaries (LCU) and the sparse access input model (SAIM)
  arXiv  Detail & Related papers  (2024-05-28T09:49:58Z)
• Private Vector Mean Estimation in the Shuffle Model: Optimal Rates Require Many Messages [63.366380571397]
  We study the problem of private vector mean estimation in the shuffle model of privacy where $n$ users each have a unit vector $v(i) inmathbbRd$. We propose a new multi-message protocol that achieves the optimal error using $tildemathcalOleft(min(nvarepsilon2,d)right)$ messages per user.
  arXiv  Detail & Related papers  (2024-04-16T00:56:36Z)
• Distributed Optimization with Feasible Set Privacy [35.16231062731263]
  Two agents learn the optimal solution set while keeping their feasible sets $mathcalP1$ and $mathcalP1$ private from each other. We adopt a sequential private information retrieval (SPIR) framework where one of the agents privately checks in $mathcalP$. We show that, compared to privately acquiring the feasible set $mathcalP1$ using an SPIR-based private set intersection (PSI) protocol, and finding the optimum, our scheme is better as it incurs less information leakage and less download
  arXiv  Detail & Related papers  (2023-12-04T18:45:04Z)
• Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation [20.909302074826666]
  Privacy and communication constraints are two major bottlenecks in federated learning (FL) and analytics (FA) We show that in order to achieve the optimal error under $(varepsilon, delta)$-DP, it is sufficient for each client to send $Thetaleft( n minleft(varepsilon, varepsilon2right)$ bits for FL and $Thetaleft(logleft(minleft(varepsilon, varepsilon2right)$)$ bits for FA
  arXiv  Detail & Related papers  (2023-04-04T05:37:17Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  For every $delta>0,$ we construct CNF and formulas of size with approximate degree $Omega(n1-delta),$ essentially matching the trivial upper bound of $n. We show that for every $delta>0$, these models require $Omega(n1-delta)$, $Omega(n/4kk2)1-delta$, and $Omega(n/4kk2)1-delta$, respectively.
  arXiv  Detail & Related papers  (2022-09-04T10:01:39Z)
• Reward-Free Model-Based Reinforcement Learning with Linear Function Approximation [92.99933928528797]
  We study the model-based reward-free reinforcement learning with linear function approximation for episodic Markov decision processes (MDPs) In the planning phase, the agent is given a specific reward function and uses samples collected from the exploration phase to learn a good policy. We show that to obtain an $epsilon$-optimal policy for arbitrary reward function, UCRL-RFE needs to sample at most $tilde O(H4d(H + d)epsilon-2)$ episodes.
  arXiv  Detail & Related papers  (2021-10-12T23:03:58Z)
• Distributed Saddle-Point Problems Under Similarity [173.19083235638104]
  We show that a given suboptimality $epsilon0$ is achieved master/workers networks in $Omegabig. We then propose algorithms matching the lower bounds either types of networks (up to log-overs) We assess effectiveness of the proposed algorithms on a robust logistic regression problem.
  arXiv  Detail & Related papers  (2021-07-22T14:25:16Z)
• The Curse of Passive Data Collection in Batch Reinforcement Learning [82.6026077420886]
  In high stake applications, active experimentation may be considered too risky and thus data are often collected passively. While in simple cases, such as in bandits, passive and active data collection are similarly effective, the price of passive sampling can be much higher when collecting data from a system with controlled states.
  arXiv  Detail & Related papers  (2021-06-18T07:54:23Z)
• 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.