Paper 2021/243

Private Set Operations from Oblivious Switching

Gayathri Garimella, Payman Mohassel, Mike Rosulek, Saeed Sadeghian, and Jaspal Singh


Private set intersection reveals the intersection of two private sets, but many real-world applications require the parties to learn $\textit{only}$ partial information about the intersection. In this paper we introduce a new approach for computing arbitrary functions of the intersection, provided that it is safe to also reveal the cardinality of the intersection. In the most general case, our new protocol provides the participants with secret shares of the intersection, which can be fed into any generic 2PC protocol. Certain computations on the intersection can also be done even more directly and efficiently, avoiding this secret-sharing step. These cases include computing only the cardinality of intersection, or the ``cardinality-sum'' application proposed in Ion et al. (ePrint 2017). Compared to the state-of-the-art protocol for computing on intersection (Pinkas et al., Eurocrypt 2019), our protocol has about $2.5-3\times$ less communication, and has faster running time on slower (50Mbps) networks. Our new techniques can also be used to privately compute the {\em union} of two sets as easily as computing the intersection. Our protocol concretely improves the leading private set union protocol (Kolesnikov et al., Asiacrypt 2020) by a factor of $2-2.5\times$, depending on the network speed. We then show how private set union can be used in a simple way to realize the ``Private-ID'' functionality suggested by Buddhavarapu et al.~(ePrint 2020). Our protocol is significantly faster than the prior Private-ID protocol, especially on fast networks. All of our protocols are in the two-party setting and are secure against semi-honest adversaries.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in PKC 2021
Private Set IntersectionOblivious Switching networkMulti-party ComputationPrivate Set Operations
Contact author(s)
garimelg @ oregonstate edu
payman mohassel @ gmail com
rosulekm @ engr orst edu
singjasp @ oregonstate edu
2021-03-02: received
Short URL
Creative Commons Attribution


      author = {Gayathri Garimella and Payman Mohassel and Mike Rosulek and Saeed Sadeghian and Jaspal Singh},
      title = {Private Set Operations from Oblivious Switching},
      howpublished = {Cryptology ePrint Archive, Paper 2021/243},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.