Huffman-based join-exit-tree scheme for contributory key management

Time efficiency in key establishment and rekeying is one of the major problems contributory key management schemes strive to address. Some schemes have been put forward to improve time efficiencies of key establishment and key update, yet they did not consider the scenario where users have varying costs and capabilities. Although conference key tree based on Huffman coding has been proposed to obtain minimum average cost on key establishment considering users' differences, it did not give the efficient key updating algorithm. We propose a Huffman-based join-exit-tree (HJET) scheme to minimizing the average key establishment time and reducing the key rekeying time for join/departure events. HJET scheme separates users into subgroups according to users' locations, designs the key tree of each subgroup using Huffman coding, and lets the combined weights locate in a higher place of the Huffman tree to minimize the key establishment time. To reduce the key rekeying cost, join tree and exit tree are adopted and served as the temporary buffers for joining and leaving users. Performance analysis and simulation results demonstrate that HJET is efficient in key establishment and update, and achieves the asymptotic time cost of O(1) for join event and nearly O(1)for leave events when group dynamics are known a priori.