Paper 2018/105

Combining Private Set-Intersection with Secure Two-Party Computation

Michele Ciampi and Claudio Orlandi

Abstract

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$.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. SCN 2018
Keywords
PSIPSMset-intersection
Contact author(s)
micheleciampi1990 @ gmail com
History
2018-06-21: last of 3 revisions
2018-01-30: received
See all versions
Short URL
https://ia.cr/2018/105
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/105,
      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{https://eprint.iacr.org/2018/105}},
      url = {https://eprint.iacr.org/2018/105}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.