Paper 2014/355

Graph-theoretic design and analysis of key predistribution schemes

Michelle Kendall and Keith M. Martin


Key predistribution schemes for resource-constrained networks are methods for allocating symmetric keys to devices in such a way as to provide an efficient trade-off between key storage, connectivity and resilience. While there have been many suggested constructions for key predistribution schemes, a general understanding of the design principles on which to base such constructions is somewhat lacking. Indeed even the tools from which to develop such an understanding are currently limited, which results in many relatively ad hoc proposals in the research literature. 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.

Available format(s)
Publication info
Preprint. MINOR revision.
Key predistribution schemesnetwork securitycombinatorial designsgraphsexpansionhypergraphs
Contact author(s)
m kendall @ imperial ac uk
2014-05-22: received
Short URL
Creative Commons Attribution


      author = {Michelle Kendall and Keith M.  Martin},
      title = {Graph-theoretic design and analysis of key predistribution schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2014/355},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.