Berlin 2015 – scientific programme
Parts | Days | Selection | Search | Updates | Downloads | Help
SOE: Fachverband Physik sozio-ökonomischer Systeme
SOE 8: Poster
SOE 8.6: Poster
Monday, March 16, 2015, 18:00–20:00, Poster E
Secure message passing on networks with insecure classes of nodes — •Sebastian M. Krause1, Michael M. Danziger2, and Vinco Zlatic1 — 1Rudjer Boskovic Institute, Zagreb, Croatia — 2Bar Ilan University, Ramat Gan, Israel
Nodes in a network such as the Internet may be able to communicate even if many connecting nodes fail. If instead of failing, the nodes manipulate or intercept messages silently, such nodes have to be avoided in advance. This is possible if the message is split into parts which are only useful together, and the parts are sent over independent paths. It is an open question, if this is possible on realistic large scale networks, where whole classes of nodes need to be avoided at the same time due to software bugs.
Here we consider the case of a network partitioned into sets of nodes (each labeled with one color) with the assumption that no single subset can be trusted. This corresponds, for example, to routers running different software versions or controlled by different entities. For transmitting the parts of a message, we ask whether sufficient paths exist, such that no color of nodes is needed to transmit all message parts. We develop a new mathematical framework based on percolation theory. With analytic solutions for Poisson and scale-free graph ensembles, we discuss a new kind of critical phenomena in which the critical exponent is determined by the number of colors. We also present a numerical algorithm which is suitable for analyzing real world networks. Applied to the Internet on the level of autonomous systems, we find that a large fraction of servers would be able to securely communicate.