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.

Marconi L, Conti M, & Di Pietro R (2011). CASSANDRA: a probabilistic, efficient, and privacy-preserving solution to compute set intersection. INTERNATIONAL JOURNAL OF INFORMATION SECURITY, 10(5), 301-319 [10.1007/s10207-011-0133-6].

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

DI PIETRO, ROBERTO
2011

Abstract

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.
Marconi L, Conti M, & Di Pietro R (2011). CASSANDRA: a probabilistic, efficient, and privacy-preserving solution to compute set intersection. INTERNATIONAL JOURNAL OF INFORMATION SECURITY, 10(5), 301-319 [10.1007/s10207-011-0133-6].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11590/137121
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? 3
social impact