Secure message passing in networks with communities


  Louis Shekhtman [1]  ,  Michael M Danziger [1]  ,  Ivan Bonamassa [1]  ,  Sergey Buldyrev [2]  ,  Vinko Zlatic [3,4]  ,  Shlomo Havlin [1]  
[1] [1] Bar Ilan University
[2] [2] Yeshiva University
[3] [3] Institute Ruder Boskovic
[4] [4] Sapienza University

In many networks it is desirable to pass information securely between different nodes each with specific security risks. By splitting up the message and finding distinct paths between nodes such that each risk is avoided by at least one path,  it is possible to increase robustness and security. A primary example is cybersecurity where each AS router belongs to a specific country and splitting up the information to send along separate paths can prevent any country from decoding it. A similar situation can arise when nodes run different software versions with unique security. 

Here we consider color-avoiding percolation on modular networks formed of distinct communities with  an average degree of $k_{intra}$ within the communities and $k_{inter}$ between the communities. Since modules usually arise due to commonalities among nodes, we assume that a fraction $q$ of each module is dominated by one or more particular colors (security risks) with only small fractions of the other colors. We solve this problem both analytically and through simulations. 
Previous work (Krause et al. 2016) analyzing when these paths exist in networks developed a new method,   called ``color-avoiding percolation'' since each security risk is associated with a particular color and found a percolation transition in random graphs.

In the case where two or more colors co-dominate a module, we find that the system undergoes higher order percolation transitions. This allows us to define critical exponents associated with higher order transitions and demonstrate the scaling relations between them.
We find surprisingly, that only when $k_{inter}=0$ does the system experience a phase transition in $q$. This is because the interconnected nodes (those possessing a link to the other modules) are always able to communicate with one another securely since they can send part of their message through their own module and part through the module to which they are linked. We map this situation to the addition of a magnetic field in the Ising model and define equivalent critical field exponents.  

Overall, this work provides an exciting physical parallel to the real-world problem of secure message passing and suggests that increasing connections between systems with distinct security can actually improve security.