The development and deployment of advanced metering infrastructure (AMI) as part of the smart grid has the potential to significantly increase both network efficiency and quality of service. The extent to which AMI will be acceptable to consumers is directly tied to the protection of consumers’ consumption data and other personal information. Cryptography is the obvious solution, but there are inherent difficulties in distributing cryptographic keys in this and related communication systems. These difficulties are compounded by the fluid nature of the community of users and the potential for hacking. We have developed key distribution schemes that allow for secure re-keying after the simultaneous ejection of multiple users and complete mesh network connectivity. We have shown how to construct minimal collections of keys necessary to re-secure these key distributions after one or two simultaneous user ejections. We have proven that this problem is NP-Hard for arbitrary key distributions. We draw mathematical connections between r-cover-free families, combinatorial designs and hitting sets to prove these results.