Secure communication over networks, especially the internet, is a central question facing the global community. In light of widespread state-surveillance, cybercrime and severe bugs like “Heartbleed”, one can not trust that the nodes in a network are secure from eavesdroppers. However, diversity of software and control can act as a barrier for exploiting security vulnerabilities. To securely communicate, we can divide the message and transmit it along different paths so that no single version or owning entity is used in the transmission of the entire message. With this heuristic, secure communication is achievable even if there are no trusted nodes.

To determine when secure communication is possible, we consider a network in which each node is assigned a color. The color represents an adversary which can eavesdrop on a given node–whether due to bugs affecting a given version or due to the adversary controlling the node. We assume that the adversaries (colors) eavesdrop on their nodes but do not share the acquired information. Because the insecurity is disjoint, even if all of the nodes are compromised, secure communication is possible.

Here, we develop a new percolation theory with which we can determine the size of the largest set of nodes that can communicate securely via multiple paths in the presence of disjoint insecurity. We present an algorithm for measuring color-avoiding connectability for general topologies and color distributions. We use our new framework to analyze the possibilities for secure communication on the AS-level internet, in which every country is assumed to eavesdrop on its internet traffic but does not share it with any other countries. With this analysis, we uncover a hidden structure in communication networks that can allow for secure communication even when no nodes are trusted.

Note: Michael M. Danziger is pursuing a PhD at Bar Ilan University under the guidance of Prof. Shlomo Havlin.