Paper 2022/334

Improved Private Set Intersection for Sets with Small Entries

Dung Bui, IRIF, Université Paris Cité
Geoffroy Couteau, CNRS, IRIF, Université Paris Cité

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.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in PKC 2023
private set intersectionpseudorandom correlation generatorssubfield vector OLEsubfield-ring OLE
Contact author(s)
bui @ irif fr
couteau @ irif fr
2023-02-03: last of 3 revisions
2022-03-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dung Bui and Geoffroy Couteau},
      title = {Improved Private Set Intersection for Sets with Small Entries},
      howpublished = {Cryptology ePrint Archive, Paper 2022/334},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.