Graph-theoretic design and analysis of key predistribution schemes. / Kendall, Michelle; Martin, Keith.

In: Designs, Codes and Cryptography, Vol. 81, No. 1, 10.2016, p. 11-34.

Research output: Contribution to journalArticle

Published

Standard

Graph-theoretic design and analysis of key predistribution schemes. / Kendall, Michelle; Martin, Keith.

In: Designs, Codes and Cryptography, Vol. 81, No. 1, 10.2016, p. 11-34.

Research output: Contribution to journalArticle

Harvard

APA

Vancouver

Author

Kendall, Michelle ; Martin, Keith. / Graph-theoretic design and analysis of key predistribution schemes. In: Designs, Codes and Cryptography. 2016 ; Vol. 81, No. 1. pp. 11-34.

BibTeX

@article{7a3f217fc38b46ca863c494b21b4402c,
title = "Graph-theoretic design and analysis of key predistribution schemes",
abstract = "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 twofold. 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.",
author = "Michelle Kendall and Keith Martin",
year = "2016",
month = oct
doi = "10.1007/s10623-015-0124-0",
language = "English",
volume = "81",
pages = "11--34",
journal = "Designs, Codes and Cryptography",
issn = "0925-1022",
publisher = "Springer Netherlands",
number = "1",

}

RIS

TY - JOUR

T1 - Graph-theoretic design and analysis of key predistribution schemes

AU - Kendall, Michelle

AU - Martin, Keith

PY - 2016/10

Y1 - 2016/10

N2 - 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 twofold. 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.

AB - 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 twofold. 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.

U2 - 10.1007/s10623-015-0124-0

DO - 10.1007/s10623-015-0124-0

M3 - Article

VL - 81

SP - 11

EP - 34

JO - Designs, Codes and Cryptography

JF - Designs, Codes and Cryptography

SN - 0925-1022

IS - 1

ER -