A Novel Dynamic Batch Rekeying Algorithm
Han Ming-kui · Xi'an Jiaotong Daxue xuebao · 2009
Aiming at the problems that the traditional individual rekeying approach is inefficient,waste of resources,and out-of-sync between keys and data,a novel batch algorithm for renewing keys is proposed based on a key tree.In the new algorithm,the key tree is kept balanced by two methods: departed nodes are replaced by joining nodes to keep the structure of the tree unchanged;the node with the smallest height in the tree is searched,and then a proper number of joining nodes are added to the node place based on the type of the node and the number of the remaining nodes to be joined.The cost of renewing servers' keys is analyzed theoretically,and accurate mathematical models are established to calculate the cost.Simulation results and comparison with the individual rekeying approach show that the proposed algorithm decreases the rekeying cost by 74.6% and improves the efficiency of rekeying significantly,and that the algorithm is suitable for large dynamic groups.