Paper 2022/1137

Private Computation On Set Intersection With Sublinear Communication

Jonas Janneck, SAP
Anselme Tueno, SAP
Jörn Kußmaul
Matthew Akram, SAP

In this paper, we propose a new protocol for private computation on set intersection (PCI) which is an extension of private set intersection (PSI). In PSI, each party has a private set and both want to securely compute the intersection of their sets such that only the result is revealed and nothing else. In PCI, we want to additionally apply a private computation on the result. The goal is to reveal only the result of such a secure evaluation on the intersection and nothing else. We particularly focus on a client-server setting where the server's set is significantly larger than the client's set and the result of the computation should be revealed only to the client. The protocol aims at a low communication overhead which is sublinear in the server's set size. Such PSI protocols have already been realized using fully homomorphic encryption (FHE). However, they do not allow for private post-processing to enable PCI. There are also protocols enabling PCI which are in addition very fast with respect to the computational overhead. Their drawback is that they have a communication overhead which is at least linear in the larger set. We present a PSI protocol which can be used for arbitrary post-processing without creating a new protocol for every special-purpose PCI functionality. Our construction relies on the evaluation of a branching program using an FHE scheme. Using the properties of an FHE scheme, we build a non-interactive protocol with extendable functionalities. That means, we can not only securely compute the intersection but use the encrypted result to apply further computations without revealing the intersection itself. To the best of our knowledge, this results in the first PCI protocol with communication cost sublinear in the larger set. Compared to previous work, we can reduce the communication by factor 47.

Available format(s)
Cryptographic protocols
Publication info
Private Set Intersection Homomorphic Encryption Multiparty Computation Branching Program
Contact author(s)
jonas janneck @ sap com
anselme tueno @ sap com
j kussmaul @ sap com
matthew akram @ sap com
2022-09-05: revised
2022-08-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jonas Janneck and Anselme Tueno and Jörn Kußmaul and Matthew Akram},
      title = {Private Computation On Set Intersection With Sublinear Communication},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1137},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.