Paper 2023/1670
Unbalanced Private Set Intersection from Homomorphic Encryption and Nested Cuckoo Hashing
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
-
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},
note = {\url{https://eprint.iacr.org/2023/1670}},
url = {https://eprint.iacr.org/2023/1670}
}
