Biblio

We consider a graph property known as r-robustness of the random K-out graphs. Random K-out graphs, denoted as \$\textbackslashtextbackslashmathbbH(n;K)\$, are constructed as follows. Each of the n nodes select K distinct nodes uniformly at random, and then an edge is formed between these nodes. The orientation of the edges is ignored, resulting in an undirected graph. Random K-out graphs have been used in many applications including random (pairwise) key predistribution in wireless sensor networks, anonymous message routing in crypto-currency networks, and differentially-private federated averaging. r-robustness is an important metric in many applications where robustness of networks to disruptions is of practical interest, and r-robustness is especially useful in analyzing consensus dynamics. It was previously shown that consensus can be reached in an r-robust network for sufficiently large r even in the presence of some adversarial nodes. r-robustness is also useful for resilience against adversarial attacks or node failures since it is a stronger property than r-connectivity and thus can provide guarantees on the connectivity of the graph when up to r – 1 nodes in the graph are removed. In this paper, we provide a set of conditions for Kn and n that ensure, with high probability (whp), the r-robustness of the random K-out graph.

We investigate the resiliency of wireless sensor networks against sensor capture attacks when the network uses the random pairwise key distribution scheme of Chan et al. We present conditions on the model parameters so that the network is: 1 unassailable and 2 unsplittable, both with high probability, as the number \$n\$ of sensor nodes becomes large. Both notions are defined against an adversary who has unlimited computing resources and full knowledge of the network topology, but can only capture a negligible fraction \$on\$ of sensors. We also show that the number of cryptographic keys needed to ensure unassailability and unsplittability under the pairwise key predistribution scheme is an order of magnitude smaller than it is under the key predistribution scheme of Eschenauer and Gligor.