Security and Privacy in Communication Networks. 6th Iternational ICST Conference, SecureComm 2010, Singapore, September 7-9, 2010. Proceedings

Research Article

CED: Communication Efficient Disjointness Decision

Download74 downloads
  • @INPROCEEDINGS{10.1007/978-3-642-16161-2_17,
        author={Luciana Marconi and Mauro Conti and Roberto Pietro},
        title={CED: Communication Efficient Disjointness Decision},
        proceedings={Security and Privacy in Communication Networks. 6th Iternational ICST Conference, SecureComm 2010, Singapore, September 7-9, 2010. Proceedings},
        proceedings_a={SECURECOMM},
        year={2012},
        month={5},
        keywords={sets disjointness test communication complexity privacy security probabilistic algorithms},
        doi={10.1007/978-3-642-16161-2_17}
    }
    
  • Luciana Marconi
    Mauro Conti
    Roberto Pietro
    Year: 2012
    CED: Communication Efficient Disjointness Decision
    SECURECOMM
    Springer
    DOI: 10.1007/978-3-642-16161-2_17
Luciana Marconi1,*, Mauro Conti2,*, Roberto Pietro3,*
  • 1: “Sapienza” Università di Roma
  • 2: Vrije Universiteit Amsterdam
  • 3: Università di Roma Tre
*Contact email: marconi@di.uniroma1.it, mconti@few.vu.nl, dipietro@mat.uniroma3.it

Abstract

Enforcing security often requires the two legitimate parties of a communication to determine whether they share a secret, without disclosing information (e.g. the shared secret itself, or just the existence of such a secret) to third parties—or even to the other party, if it is not the legitimate party but an adversary pretending to impersonate the legitimate one. In this paper, we propose CED (Communication Efficient Disjointness Decision), a probabilistic and distributed protocol that allows two parties—each one having a finite set of elements—to decide about the disjointness of their sets. CED is particularly suitable for devices having constraints on energy, communication, storage, and bandwidth. Examples of these devices are satellite phones, or nodes of wireless sensor networks. We show that CED significantly improves the communication cost compared to the state of the art, while providing the same degree of privacy and security. Analysis and simulations support the findings.