Paper 2018/105

Combining Private Set-Intersection with Secure Two-Party Computation

Michele Ciampi and Claudio Orlandi


Private Set-Intersection (PSI) is one of the most popular and practically relevant secure two-party computation (2PC) tasks. Therefore, designing special-purpose PSI protocols (which are more efficient than generic 2PC solutions) is a very active line of research. In particular, a recent line of work has proposed PSI protocols based on oblivious transfer (OT) which, thanks to recent advances in OT-extension techniques, is nowadays a very cheap cryptographic building block. Unfortunately, these protocols cannot be plugged into larger 2PC applications since in these protocols one party (by design) learns the output of the intersection. Therefore, it is not possible to perform secure post-processing of the output of the PSI protocol. In this paper we propose a novel and efficient OT-based PSI protocol that produces an "encrypted" output that can therefore be later used as an input to other 2PC protocols. In particular, the protocol can be used in combination with all common approaches to 2PC including garbled circuits, secret sharing and homomorphic encryption. Thus, our protocol can be combined with the right 2PC techniques to achieve more efficient protocols for computations of the form $z=f(X\cap Y)$ for arbitrary functions $f$.

Available format(s)
Publication info
Published elsewhere. MINOR revision.SCN 2018
Contact author(s)
micheleciampi1990 @ gmail com
2018-06-21: last of 3 revisions
2018-01-30: received
See all versions
Short URL
Creative Commons Attribution


      author = {Michele Ciampi and Claudio Orlandi},
      title = {Combining Private Set-Intersection with Secure Two-Party Computation},
      howpublished = {Cryptology ePrint Archive, Paper 2018/105},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.