Abstract
This paper brings up a new concern regarding efficient re-keying of large groups with dynamic membership: minimizing the overall time it takes for the key server and the group members to process the re-keying message. Specifically, we concentrate on re-keying algorithms based on the Logical Key Hierarchy (LKH), and minimize the longest sequence of encryptions and decryptions that need to be done in a re-keying operation. We first prove a lower bound on the time required to perform a re-keying operation in this model, then we provide an optimal schedule of re-keying messages matching the above lower bound. In particular, we show that the optimal schedule can be found only when the ariety of the LKH key graph is chosen according to the available communication bandwidth and the users processing power. Our results show that key trees of ariety 3, commonly assumed to be optimal, are not optimal when used in high bandwidth networks, or networks of devices with low computational power like sensor networks.