Paper 2016/108

An Efficient Toolkit for Computing Private Set Operations

Alex Davidson and Carlos Cid


Private set operation (PSO) protocols provide a natural way of securely performing operations on data sets, such that crucial details of the input sets are not revealed. Such protocols have an ever-increasing number of practical applications, particularly when implementing privacy-preserving data mining schemes. Protocols for computing private set operations have been prevalent in multi-party computation literature over the past decade, and in the case of private set intersection (PSI), have become practically feasible to run in real applications. In contrast, other set operations such as union have received less attention from the research community, and the few existing designs are often limited in their feasibility. In this work we aim to fill this gap, and present a new technique using Bloom filter data structures and additive homomorphic encryption to develop the first private set union protocol with both linear computation and communication complexities. Moreover, we show how to adapt this protocol to give novel ways of computing PSI and private set intersection/union cardinality with only minor changes to the protocol computation. Our work resembles therefore a toolkit for scalable private set computation with linear complexities, and we provide a thorough experimental analysis that shows that the online phase of our designs is practical up to large set sizes.

Note: Change of title, formerly known as "Computing Private Set Operations with Linear Complexities"

Available format(s)
Publication info
Published elsewhere. ACISP 2017
Private set operationsBloom filtersadditively homomorphic encryptionsecure computationdata mining.
Contact author(s)
alex davidson 2014 @ rhul ac uk
2017-05-10: last of 2 revisions
2016-02-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alex Davidson and Carlos Cid},
      title = {An Efficient Toolkit for Computing Private Set Operations},
      howpublished = {Cryptology ePrint Archive, Paper 2016/108},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.