密钥覆盖问题的建模、变换及近似算法

On the Modeling Transformations and Approximation Algorithms of Key Covering Problem in the Group Rekeying

组密钥管理是组安全、多播安全中的核心问题.本文给出了密钥覆盖问题模型的建立过程,首次给出密钥覆盖问题(KCP)与顶点覆盖问题(VCP)的相互变换.基于从VCP到KCP的变换,证明了密钥覆盖问题是NP完全的;基于从KCP到VCP的变换,基于VCP的算法为KCP设计了一类近似算法并给出了模拟试验.本文的结果为组安全、多播安全研究提供了更为坚实的算法基础.

Group key management is essential for group security, especially for multieast security. This paper presents the modeling process of the key covering problem （KCP） in the group rekeying and the transformations between the KCP and the vertex covering problem（VCP） in the graph theory. Furthermore,based on the transformation from the VCP to the KCP,the NP- completeness of the decision version of the KCP is proved via the decision version of the VCP ;Based on the transformation from the KCP to the VCP,the approximation algorithms for the KCP is designed via the greedy approximation algorithms for the VCP and the simulation is also given. The results of this paper lay a more solid algorithmic foundation for the research of group security,especially of multieast security.