Paper 2022/334

Improved Private Set Intersection for Sets with Small Entries

Abstract

We introduce new protocols for private set intersection (PSI), building upon recent constructions of pseudorandom correlation generators, such as vector-OLE and ring-OLE. Our new constructions improve over the state of the art on several aspects, and perform especially well in the setting where the parties have databases with small entries. We obtain three main contributions: 1. We introduce a new semi-honest PSI protocol that combines subfield vector-OLE with hash-based PSI. Our protocol is the first PSI protocol to achieve communication complexity independent of the computational security parameter κ, and has communication lower than all previous known protocols for input sizes ℓ below 70 bits. 2. We enhance the security of our protocol to the malicious setting, using two different approaches. In particular, we show that applying the dual execution technique yields a malicious PSI whose communication remains independent of κ, and improves over all known PSI protocols for small values of ℓ. 3. As most previous protocols, our above protocols are in the random oracle model. We introduce a third protocol which relies on subfield ring-OLE to achieve maliciously secure PSI in the standard model, under the ring-LPN assumption. Our protocol enjoys extremely low communication, reasonable computation, and standard model security. Furthermore, it is batchable: the message of a client can be reused to compute the intersection of their set with that of multiple servers, yielding further reduction in the overall amortized communication.

Note: Significant changes compared to first version, update table 1.