Paper 2022/721

Fast Multi-party Private Set Operations in the Star Topology from Secure ANDs and ORs

Jelle Vos, Delft University of Technology
Mauro Conti, University of Padua, Delft University of Technology
Zekeriya Erkin, Delft University of Technology

Today, our society produces massive amounts of data, part of which are strictly private. So, a long line of research has worked to design protocols that perform functions on such private data without revealing them. One function that has attracted significant interest is a multi-party private set operation, where each party's input is a set. The parties commonly intend to compute these sets' collective intersection (MPSI) or union (MPSU), which finds uses in various applications, including private scheduling and threat intelligence. Most current protocols use integer-based homomorphic encryption, with large elements and expensive operations, or oblivious transfers, which require communicationally-expensive pairwise interactions between all parties. Thus, existing solutions introduce significant overhead that hinders practical use. This paper considers a certain class of previously-proposed MPSI and MPSU protocols. We propose to express them in terms of new private AND or OR operations among all parties and use elliptic curves to realize these operations efficiently. We achieve a significant performance gain: Firstly, our protocols take only three rounds of communication. Secondly, our constant-time open-source implementation is two orders of magnitude faster than the state-of-the-art MPSI for small universes and outperforms the state-of-the-art MPSI for large universes for three parties or more.

Available format(s)
Cryptographic protocols
Publication info
private set operations multi-party computation homomorphic encryption
Contact author(s)
J V Vos @ tudelft nl
mauro conti @ unipd it
Z Erkin @ tudelft nl
2022-06-06: approved
2022-06-06: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-NoDerivs


      author = {Jelle Vos and Mauro Conti and Zekeriya Erkin},
      title = {Fast Multi-party Private Set Operations in the Star Topology from Secure ANDs and ORs},
      howpublished = {Cryptology ePrint Archive, Paper 2022/721},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.