Back to search

Cornell University

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

Abstract

dc:description.abstract

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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Applied Mathematics
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Applied Mathematics
Grantor
Cornell University
Year dc:date.issued
2011

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Karst, Nathaniel
Chair dc:contributor.chair
  • Wicker, Stephen B.
Committee members dc:contributor.committeemember
  • Brown, Kenneth Stephen
  • Bojanczyk, Adam Wojciech

Subjects

dc:subject × 3

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
7955512

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Karst, Nathaniel. Combinatorial Designs For Key Distribution And Secure Re-Keying In Group Communication Systems. Doctor of Philosophy thesis, Cornell University, 2011. https://hdl.handle.net/1813/30700