It has been suggested that a large edge-expansion coefficient in the key graph is desirable for efficient key predistribution schemes. However, attempts to create key predistribution schemes from known expander graph constructions have only provided an extreme in the trade-off between connectivity and resilience: namely, they provide perfect resilience at the expense of substantially lower connectivity than can be achieved with the same key storage.
Our contribution is two-fold. First, we prove that many existing key predistribution schemes produce key graphs with good expansion. This provides further support and justification for their use, and confirms the validity of expansion as a sound design principle. Second, we propose the use of incidence graphs and concurrence graphs as tools to represent, design and analyse key predistribution schemes. We show that these tools can lead to helpful insights and new constructions.Category / Keywords: Key predistribution schemes, network security, combinatorial designs, graphs, expansion, hypergraphs Date: received 20 May 2014 Contact author: m kendall at imperial ac uk Available format(s): PDF | BibTeX Citation Version: 20140522:071512 (All versions of this report) Short URL: ia.cr/2014/355 Discussion forum: Show discussion | Start new discussion