Projet de recherche doctoral numero :4702


Date depot: 1 janvier 1900
Titre: Tractable Reliable Communication in Dynamic Compromised Networks
Directeur de thèse: Sébastien TIXEUIL (LIP6)
Encadrante : Silvia BONOMI (Univ. Roma)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini

Resumé: Recent years proved the opportunistic use of available networks extremely useful to offload trafic in a cost efficient manner while preserving quality of service. Such networks are typically highly dynamic as their participants move and opportunistically reconnect as new neighbors are discovered. However, exchanging information across multiple hops in such (uncontrolled) networks poses a serious security challenge: potential attackers are now insiders. In a recent paper [1], Maurer et al. considered the following problem: two nodes want to reliably communicate in a dynamic multi-hop network where a subset of the nodes have been compromised (and may have a totally arbitrary and unpredictable behavior, that is, they are Byzantine). They focused on cryptography-free solutions, as the network compromission could imply that the cryptographic infrastructure itself is compromised. In static networks, a necessary and sufficient condition for reliable multi-hop communication with k Byzantine nodes is the existence of 2k+1 disjoint paths between the source and the destination. However, this result is based on Menger's theorem (that relates the minimal node cut to network connectivity), which becomes incorrect in the case of dynamic networks. Maurer et al. proved a necessary and sufficient condition (in other words, the weakest possible condition) for enabling reliable communication in a dynamic multi-hop network where a subset of the nodes are Byzantine. Their proof is constructive, as they provide a Byzantine-resilient algorithm for reliable communication that is optimal with respect to their impossibility result.

Doctorant.e: Farina Giovanni