Unbalanced Private Set Intersection from Homomorphic Encryption and Nested Cuckoo Hashing

Geb. 50.34, SR 252 und online: https://i62bbb.tm.kit.edu/b/mic-7xx-rfr

2023-01-24

11:30

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 set sizes.
We formally prove the security of our protocol against semi-honest adversaries in the standard model.
Our protocol yields a sublinear client computation and communication complexity in the larger 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 attest to state-of-the-art performance and usability in practice.