Paper 2024/1642 Original: eprint.iacr.org/2024/1642 ↗
Fuzzy PSI via Oblivious Protocol Routing
Abstract
In private set intersection (PSI), two parties who each hold sets of items can learn their intersection without revealing anything about their other items. Fuzzy PSI corresponds to a relaxed variant that reveals pairs of items which are ``close enough,'' with respect to some distance metric. In this paper we propose a new protocol framework for fuzzy PSI, compatible with arbitrary distance metrics. We then show how to efficiently instantiate our framework for $\ell_1$, $\ell_2$, and $\ell_\infty$ metrics, in a way that uses exclusively cheap symmetric-key operations. One notable feature of our protocol is that it has only logarithmic dependency on the distance threshold, whereas most other protocols have linear (or higher) dependency. For many reasonable combinations of parameters, our protocol has the lowest communication cost of existing fuzzy PSI protocols.
Metadata
- Available format(s)
PDF- Category
- Cryptographic protocols
- Publication info
- Preprint.
- History
- 2024-10-12: last updated
- 2024-10-12: published
- Short URL
- https://ia.cr/2024/1642
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2024/1642,
author = {David Richardson and Mike Rosulek and Jiayu Xu},
title = {Fuzzy PSI via Oblivious Protocol Routing},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/1642},
year = {2024},
url = {https://eprint.iacr.org/2024/1642}
}