Paper 2026/166

Fuzzy Enhanced Private Set Union in Hamming and Minkowski Spaces

Abstract

Private Set Union (PSU) enables two parties holding private sets $X$ and $Y$ to compute their union $X\cup Y$ without revealing anything else. Enhanced PSU (ePSU) further eliminates during-execution leakage, but existing constructions are limited to exact matching. This restriction is inadequate for many real-world applications involving noisy data, approximate representations, or feature embeddings, where similarity is naturally defined via distance metric rather than strict equality. In this work, we introduce fuzzy ePSU, a new cryptographic primitive that supports distance-based union while preserving the no during-execution leakage guarantee of ePSU. Given a distance metric $\mathsf{dist}(\cdot,\cdot)$ and a threshold $\delta$, fuzzy ePSU allows the receiver to learn exactly those sender items whose distance to all receiver items exceeds $\delta$, thereby computing a fuzzy union of the two sets. We present two concrete fuzzy ePSU constructions instantiated over different metric spaces. For the Hamming space, we design a protocol based on a new primitive called Fuzzy Oblivious Non-Membership Conditional Randomness Generation (FOnMCRG), achieving linear complexity in the input set sizes and $\delta$. For the Minkowski space, we introduce Fuzzy Permuted Non-Membership Conditional Randomness Generation (FpnMCRG), which combines fuzzy mapping with hashing-to-bin techniques and achieves (quasi-)linear complexity in the input sizes and dimension. We implement our protocols and evaluate their performance in both metric spaces. For input sets of size $2^{12}$, our Hamming-space protocol incurs about 79.990~MB of communication and 70.686~s of runtime with $\delta=4$. In the Minkowski space with $\{1,2,\infty\}$-norm, dimension $d=10$, and $\delta=30$, it incurs 388.137--689.889~MB of communication and 347.082--483.328~s of runtime.