On the Rekeying Load in Group Key Distributions Using Cover-Free Families

Key distributions based on cover-free families have been recently proposed for secure rekeying in group communication systems after multiple simultaneous user ejections. Existing literature has not quantified how difficult this rekeying operation might be. This study provides upper bounds on the number messages necessary to rekey a key distribution based on symmetric combinatorial designs after one or two simultaneous user ejections. Connections are made to results from finite geometry to show that these bounds are tight for certain key distributions. It is shown that in general determining the minimal number of messages necessary to rekey a group communication system based on a cover-free family is NP-hard.