IACR News item: 22 May 2014
Michelle Kendall, Keith M. Martin
ePrint ReportIt 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.
Additional news items may be found on the IACR news page.