Paper 2025/217

Assumption-Free Fuzzy PSI via Predicate Encryption

Erik-Oliver Blass, Airbus
Guevara Noubir, Northeastern University
Abstract

We present the first protocol for efficient Fuzzy Private Set Intersection (PSI) that achieves linear communication complexity, does not depend on restrictive assumptions on the distribution of party inputs, and abstains from inefficient fully homomorphic encryption. Specifically, our protocol enables two parties to compute all pairs of elements from their respective sets that are within a given Hamming distance, without constraints on how these sets are structured. Our key insight is that securely computing the (threshold) Hamming distance between two inputs can be reduced to securely computing their inner product. Leveraging this reduction, we construct a Fuzzy PSI protocol using recent techniques for inner-product predicate encryption. To enable the use of predicate encryption in our setting, we establish that these predicate encryption schemes satisfy a weak notion of simulation security and demonstrate how their internal key derivation can be efficiently distributed without a trusted third party. As a result, our Fuzzy PSI on top of predicate encryption features not only asymptotically optimal linear communication complexity but is also concretely practical.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Contact author(s)
erik-oliver blass @ airbus com
g Noubir @ northeastern edu
History
2025-02-14: revised
2025-02-12: received
See all versions
Short URL
https://ia.cr/2025/217
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/217,
      author = {Erik-Oliver Blass and Guevara Noubir},
      title = {Assumption-Free Fuzzy {PSI} via Predicate Encryption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/217},
      year = {2025},
      url = {https://eprint.iacr.org/2025/217}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.