In less than a century, the Internet has morphed from being a communication channel to a medium of existence for people. Meanwhile, attacks over the Internet have been growing both qualitatively and quantitatively, with losses transcending the financial kind and threatening the well-being of human lives. This trend fuels the need for Cyber Threat Intelligence (CTI), to change our reactive nature and start pro-actively tackling the online threats. This necessity has engendered the establishment of a number of CTI service providers. To ensure optimum expenditure, an organization would be best served by only procure intel on threats relevant to it. Hence, a scheme enabling organizations to choose the right subset of CTI service providers, to obtain the maximum amount of intel relevant to them, is needed. This scheme, however, is obliged to maintain the privacy of the inputs of all parties involved, lest the intel is leaked to the adversaries. Privacy-Preserving Set Operations offers the necessary properties and primitives to devise such a scheme. However, constructing protocols from existing solutions is infeasible, due to the exponential dependence, of their asymptotic complexities, on the number of participants in the protocol. This dissertation aims to devise protocols to enable the discussed scheme, in a feasible and privacy-preserving manner.

In this thesis, we introduce a type of composite set operations which we denote as combinatorial set operations. We construct four efficient, privacy-preserving protocols to compute the set union-combinatorial intersection cardinalities between multiple mistrusting parties, in honest-but-curious and covert adversaries models, to solve our research goal. The protocols compute the intersection cardinality between a set and all union combinations of a number of other sets, while maintaining the privacy of the set elements. All the protocols proposed in this thesis claim asymptotic complexities quadratically dependent on the number of parties involved in the protocol, while the best current alternative is constrained by an exponential dependence on the same. A comparative implementation of our principal protocol in the covert adversaries model boasts an overall computation time of 1 minute, for 15 parties with 5 elements in each party’s set. The best current alternative requires 56.5 minutes under the same initial conditions. Moreover, even after increasing the number of participants and elements to 50 and 100, respectively, our protocols outperformed the best current alternative subject to the previous initial constraints (15 parties with 5 elements). We hope that the promising results obtained in this work pave the way to help organizations in navigating the increasingly complex threat environment, allowing them to pro-actively combat the rising wave of cybercrime.