Welcome to the resource topic for 2024/330
Title:
Fuzzy Private Set Intersection with Large Hyperballs
Authors: Aron van Baarsen, Sihang Pu
Abstract: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.
ePrint: https://eprint.iacr.org/2024/330
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .