Optimizing the Batch Mode of Group Rekeying: Lower Bound and New Protocols

In group communications, an efficient rekeying scheme plays a key role in providing access control when a membership change happens. For reducing the communication cost in the rekeying operation, one proposed model is to rekey upon individual membership change. It is theoretically proved that given the forward secrecy requirement, the optimal amortized communication cost is at least O(log n) (n is the group size) for an Individual Rekeying (IR). Another model is to rekey upon a batch of multiple membership changes: Batch Rekeying (BR), which largely reduces the rekeying communication cost, and relieves implementation difficulties in the IR model (e.g., extremely intensive rekey messages and key arriving disorders in large-size and highly dynamic groups). Unlike IR, however, the communication lower bound in BR is not yet explicitly stated. This paper first extends the communication lower bound for IR to the BR model. Specifically, we prove that given the batch level forward secrecy, the communication costs for updating the whole group subset by subset in a sequence of b batch rekeyings are at least O(b · (log₂ b - 1)) + O(n). This bound, as a superset, inclusively explains the IR bound as a special case of b = n. Second, for achieving the found bound, we provide a departing-time related key topology that works optimally under the bound. Third, to further implement the proposed optimal topology, we propose two novel BR protocols, one with support of forward secrecies and the other with support of two-way secrecies. Through extensive analyses and simulations, the proposed protocols are shown to achieve notable upgrades in major performance metrics: 60% ~ 70% reduction in communication overheads, 50% ~ 60% reduction in key storage overheads, and elimination of key tree unbalance.