Combinatorial Designs For Key Distribution And Secure Re-Keying In Group Communication Systems

Other Titles


Combinatorial t-designs are a class of highly regular set systems subject to interesting incidence conditions. These objects have been found to be very useful in applications ranging from tournament scheduling to traffic routing in communication networks. In the work presented here, we use a particularly nicely-structured class of combinatorial designs, known as symmetric 2-designs, to solve a problem concerning secure re-keying in a wireless communication system after the ejection of one or more users from the network. We show that employing a symmetric 2-design as a key distribution in this type of system provides a number of benefits, including collusion prevention and provably light loads for the base station to execute necessary secure re-keying operations. We show that a class of symmetric 2-design key distribution allows for minimal re-keying procedures after multiple simultaneous user ejections and that this problem is NP-hard for arbitrary key distributions. For cases where the structure of symmetric 2-designs is insufficient to make these strong claims, we present a novel algorithm for identifying a collection of keys sufficient to re-key a network after any number of ejections. We provide simulation results to show that for symmetric 2-design key distributions this algorithm performs significantly better than existing solutions. To make these guarantees, we draw connections between combinatorial designs, cover-free families and various key distribution methodologies. We conclude by presenting a sample application of this machinery, namely the advanced metering infrastructure being deployed to monitor end-user electricity consumption as part of the smart grid. The wireless sensors employed in this scheme have tight constraints on memory, computation and power, and so symmetric encryption is a natural choice for data security. The distribution of the cryptographic keys necessary for these operations is difficult, and fluid group membership further complicates the problem. The widespread adoption of AMI has the potential to significantly increase the efficiency of the power distribution network. The acceptability of AMI to consumers is directly tied to their perceived security; a robust infrastructure is necessary to assure consumers of the protection of their personal information.

Journal / Series

Volume & Issue



Date Issued




combinatorial designs; wireless sensor networks; cover-free family


Effective Date

Expiration Date




Union Local


Number of Workers

Committee Chair

Wicker, Stephen B.

Committee Co-Chair

Committee Member

Brown, Kenneth Stephen
Bojanczyk, Adam Wojciech

Degree Discipline

Applied Mathematics

Degree Name

Ph. D., Applied Mathematics

Degree Level

Doctor of Philosophy

Related Version

Related DOI

Related To

Related Part

Based on Related Item

Has Other Format(s)

Part of Related Item

Related To

Related Publication(s)

Link(s) to Related Publication(s)


Link(s) to Reference(s)

Previously Published As

Government Document




Other Identifiers


Rights URI


dissertation or thesis

Accessibility Feature

Accessibility Hazard

Accessibility Summary

Link(s) to Catalog Record