Paper 2023/1670

Unbalanced Private Set Intersection from Homomorphic Encryption and Nested Cuckoo Hashing

Jörn Kußmaul
Matthew Akram
Anselme Tueno
Abstract

Private Set Intersection (PSI) is a well-studied secure two-party computation problem in which a client and a server want to compute the intersection of their input sets without revealing additional information to the other party. With this work, we present nested Cuckoo hashing, a novel hashing approach that can be combined with additively homomorphic encryption (AHE) to construct an efficient PSI protocol for unbalanced input sets. We formally prove the security of our protocol against semi-honest adversaries in the standard model. Our protocol yields client computation and communication complexity that is sublinear in the server’s set size and is thus of interest to clients with limited resources. The implementation and empirical evaluation of our protocol using the exponential ElGamal and BGV/BFV encryption schemes attests to state-of-the-art practical performance.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
PSISecure 2-PCHomomorphic encryptionCuckoo hashingPrivacy-enhancing technologiesExponential ElGamalBGV/BFV
Contact author(s)
joern kussmaul @ gmail com
matthew akram zaher farid @ sap com
anselme tueno @ sap com
History
2023-10-30: approved
2023-10-27: received
See all versions
Short URL
https://ia.cr/2023/1670
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1670,
      author = {Jörn Kußmaul and Matthew Akram and Anselme Tueno},
      title = {Unbalanced Private Set Intersection from Homomorphic Encryption and Nested Cuckoo Hashing},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1670},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1670}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.