{"id":{"repo_id":"cornell","oai_identifier":"oai:ecommons.cornell.edu:1813/30700"},"canonical_url":"https://search.ndltd.org/etd/cornell/oai:ecommons.cornell.edu:1813/30700","repository":{"repo_id":"cornell","name":"Cornell University","base_url":"https://ecommons.cornell.edu/server/oai/request"},"display":{"title":"Combinatorial Designs For Key Distribution And Secure Re-Keying In Group Communication Systems","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.","abstract_html":"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.","abstract_has_math":false,"creators":["Karst, Nathaniel"],"institution":"Cornell University","degree_name":"Ph. D., Applied Mathematics","degree_level":"Doctor of Philosophy","degree_discipline":"Applied Mathematics","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":["Wicker, Stephen B."],"committee_members":["Brown, Kenneth Stephen","Bojanczyk, Adam Wojciech"],"year":2011,"date_issued":"2011-08-31","date_published":"2011-08-31","updated_at":"2026-11-19T03:15:03Z","subjects":["combinatorial designs","wireless sensor networks","cover-free family"],"languages":["en_US"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["7955512"],"render_values":[{"text":"7955512","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/1813/30700","outbound_label":"Handle","outbound_source":"dc:identifier.uri","record_url":"https://hdl.handle.net/1813/30700","record_label":"Repository record","record_kind":"handle","record_source":"dc:identifier.uri","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://ecommons.cornell.edu/server/oai/request?verb=GetRecord&metadataPrefix=dim&identifier=oai%3Aecommons.cornell.edu%3A1813%2F30700","prefix":"dim"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.chair","label":"Chair","values":["Wicker, Stephen B."]},{"key":"dc:contributor.committeemember","label":"Committee Member","values":["Brown, Kenneth Stephen","Bojanczyk, Adam Wojciech"]},{"key":"dc:creator","label":"Author","values":["Karst, Nathaniel"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2012-12-17T13:50:58Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2016-12-30T06:46:57Z"]},{"key":"dc:date.issued","label":"Date","values":["2011-08-31"]},{"key":"dc:type","label":"Dc Type","values":["dissertation or thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Applied Mathematics"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Doctor of Philosophy"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph. D., Applied Mathematics"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Cornell University"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["combinatorial designs","wireless sensor networks","cover-free family"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.bibid","label":"Dc Identifier Bibid","values":["7955512"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/1813/30700"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"cerif:openaire","label":"Cerif Openaire","values":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"bbc0a443-1778-4d10-bc44-63402c2d592c\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Combinatorial Designs For Key Distribution And Secure Re-Keying In Group Communication Systems</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2011-08-31</PublicationDate> <Authors> <Author> <DisplayName>Karst, Nathaniel</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>combinatorial designs</Keyword> <Keyword>wireless sensor networks</Keyword> <Keyword>cover-free family</Keyword> <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.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"]},{"key":"cris:virtual.author","label":"Cris Virtual Author","values":["Karst, Nathaniel"]},{"key":"cris:virtualsource.collection","label":"Cris Virtualsource Collection","values":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:description.collection","label":"Dc Description Collection","values":["Cornell Theses and Dissertations"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["Combinatorial Designs For Key Distribution And Secure Re-Keying In Group Communication Systems"]},{"key":"dspace:entity.type","label":"Dspace Entity Type","values":["Publication"]},{"key":"others:access_status","label":"Others Access Status","values":["open.access"]}]}],"canonical_facts":{"cerif:openaire":["<Publication xmlns=\"https://www.openaire.eu/cerif-profile/1.1/\" id=\"bbc0a443-1778-4d10-bc44-63402c2d592c\"> <Type xmlns=\"https://www.openaire.eu/cerif-profile/vocab/COAR_Publication_Types\">http://purl.org/coar/resource_type/c_1843</Type> <Language>en_US</Language> <Title>Combinatorial Designs For Key Distribution And Secure Re-Keying In Group Communication Systems</Title> <PublishedIn> <Publication> </Publication> </PublishedIn> <PublicationDate>2011-08-31</PublicationDate> <Authors> <Author> <DisplayName>Karst, Nathaniel</DisplayName> <Affiliation> <OrgUnit> </OrgUnit> </Affiliation> </Author> </Authors> <Editors> </Editors> <Publishers> <Publisher> <OrgUnit /> </Publisher> </Publishers> <Keyword>combinatorial designs</Keyword> <Keyword>wireless sensor networks</Keyword> <Keyword>cover-free family</Keyword> <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.</Abstract> <Access xmlns=\"http://purl.org/coar/access_right\" > </Access> </Publication>"],"cris:virtual.author":["Karst, Nathaniel"],"cris:virtualsource.collection":["5893a6ea-7af3-41d7-abc6-04bcd26ab5df"],"dc:contributor.chair":["Wicker, Stephen B."],"dc:contributor.committeemember":["Brown, Kenneth Stephen","Bojanczyk, Adam Wojciech"],"dc:creator":["Karst, Nathaniel"],"dc:date.accessioned":["2012-12-17T13:50:58Z"],"dc:date.available":["2016-12-30T06:46:57Z"],"dc:date.issued":["2011-08-31"],"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."],"dc:description.collection":["Cornell Theses and Dissertations"],"dc:format.mimetype":["application/pdf"],"dc:identifier.bibid":["7955512"],"dc:identifier.uri":["https://hdl.handle.net/1813/30700"],"dc:language.iso":["en_US"],"dc:subject":["combinatorial designs","wireless sensor networks","cover-free family"],"dc:title":["Combinatorial Designs For Key Distribution And Secure Re-Keying In Group Communication Systems"],"dc:type":["dissertation or thesis"],"dspace:entity.type":["Publication"],"others:access_status":["open.access"],"thesis:degree_discipline":["Applied Mathematics"],"thesis:degree_level":["Doctor of Philosophy"],"thesis:degree_name":["Ph. D., Applied Mathematics"],"thesis:institution_name":["Cornell University"]},"updated_at":"2026-11-19T03:15:03Z"}