路径洗牌算法：安全组播中一种高效的组密钥更新算法

PSA:An Efficient Group Key Updating Algorithm in Secure Multicast

安全组播通信使用组内所有成员共享的组密钥来加密通信内容。为了保障安全,密钥服务器需要在组成员关系改变时进行组密钥更新(rekey)。由于组内成员关系的动态性和加解密操作的高代价,组密钥更新性能成为衡量组密钥管理性能的主要指标。基于密钥树(key tree)的组密钥更新方法已经被广泛地使用,并达到了对数级的组密钥更新代价。密钥树的结构需要保证平衡,否则最坏情况下组密钥更新的通信代价会达到O(n)。该文提出了一种新的基于密钥树的路径洗牌算法PSA(Path Shuffling Algorithm),该算法能够将密钥树的平衡操作分散到一般的更新密钥操作中,减少了结构调整代价,从而提高了算法的性能。理论分析给出了该算法更新组密钥的平均通信代价,模拟实验也验证了这种算法更新组密钥的平均性能要优于其它同类算法。

Secure multicast uses a group key shared by all group members to encrypt group communication. To ensure security, key server should update the group key （rekey） when an existing member leaves the group or a new member joins the group. Key tree approach is widely used to achieve logarithmic rekeying cost, but the key tree structure has to be kept balanced, otherwise the communication cost in the worst cast will be O（n）. In this article a new algorithm named PSA （Path Shuffling Algorithm） is proposed based on key tree. PSA can scatter the balanced operations in normal rekeying operations, so it reduces the restructuring cost and thus improves the performance. Theoretical analysis gives the average updating cost, and experiments show that PSA algorithm has better average-case rekeying performance than other group key updating algorithms.