CASSANDRA: a probabilistic, efficient, and privacy preserving solution to compute set intersection

Enforcing security often requires the two legitimate parties of a communication to determine if they share a secret, without disclosing information (e.g., the shared secret itself, or just the existence of such a secret) to third parties. In this paper, we propose CASSANDRA, a toolbox composed of three probabilistic protocols that allows two parties, each one having a subset of elements drawn by a pre-determined set, to compute information about the intersection of such two sets. In particular, C-void decides whether the two sets are disjoint; C-size allows to compute how many elements the intersection is composed of; and, C-set returns the identity of the elements of the intersection (if any). These protocols differ, other than in functionality, also in the degree of assurance they can provide and the degree of interactions required by the two parties. The communication cost also differs, but in any case, it is below the cost of competing solution representing the state of the art. These protocols also share some common features: that is, they are completely tunable and specifically suited for devices having constraints on energy, communication, storage, and bandwidth. Examples of these devices are portable devices (e.g., phones) handling satellite communications, or nodes of wireless sensor networks. Thorough analysis and extensive simulations support our findings.