Group key rekeying using the LKH technique and the Huffman algorithm

A secure and efficient scheme to rekey group keys is investigated. A group key is secret information which is owned by all users in a certain group. When a user newly joins the group, and when a user leaves the group, the group key must be updated, or rekeyed, to conform the security. Widely known LKH scheme works efficiently if its internal key-tree is well-balanced, though, the balance of the key-tree can be degraded if a group key is rekeyed many times. In this paper, the LKH scheme is modified so that the internal key-tree is kept optimized all the time. It is shown that there is strong relation between the cost for rekeying and the external path length of the key-tree. A new scheme is then investigated which makes use of the Huffman algorithm to keep the external path length of the key-tree minimized.