Paper 2024/330

Fuzzy Private Set Intersection with Large Hyperballs

Aron van Baarsen, Centrum Wiskunde & Informatica, Leiden University
Sihang Pu, Helmholtz Center for Information Security

Traditional private set intersection (PSI) involves a receiver and a sender holding sets $X$ and $Y$, respectively, with the receiver learning only the intersection $X\cap Y$. We turn our attention to its fuzzy variant, where the receiver holds \(|X|\) hyperballs of radius \(\delta\) in a metric space and the sender has $|Y|$ points. Representing the hyperballs by their center, the receiver learns the points $x\in X$ for which there exists $y\in Y$ such that $\mathsf{dist}(x,y)\leq \delta$ with respect to some distance metric. Previous approaches either require general-purpose multi-party computation (MPC) techniques like garbled circuits or fully homomorphic encryption (FHE), leak details about the sender’s precise inputs, support limited distance metrics, or scale poorly with the hyperballs' volume. This work presents the first black-box construction for fuzzy PSI (including other variants such as PSI cardinality, labeled PSI, and circuit PSI), which can handle polynomially large radius and dimension (i.e., a potentially exponentially large volume) in two interaction messages, supporting general \(L_{p\in[1,\infty]}\) distance, without relying on garbled circuits or FHE. The protocol excels in both asymptotic and concrete efficiency compared to existing works. For security, we solely rely on the assumption that the Decisional Diffie-Hellman (DDH) holds in the random oracle model.

Note: Updated the Lemma 1 with an additional restriction to exclude corner cases; Corrected some numbers appearing in theorems and lemmas.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in EUROCRYPT 2024
MPCPrivate Set IntersectionFuzzy PSIFuzzy Matching
Contact author(s)
aronvanbaarsen @ gmail com
sihang pu @ gmail com
2024-05-20: revised
2024-02-26: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aron van Baarsen and Sihang Pu},
      title = {Fuzzy Private Set Intersection with Large Hyperballs},
      howpublished = {Cryptology ePrint Archive, Paper 2024/330},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.