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

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

作　　者：陆正福[1] 洪孙焱[1] 

机构地区：[1]云南大学数学系,云南昆明650091

出　　处：《小型微型计算机系统》2007年第7期1189-1194,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(10561009)资助;云南省自然科学基金项目(2002F0012M)资助;云南大学中青年骨干教师培养计划专项经费资助项目;云南大学理(工)科校级科研重点项目(2003Z010C)资助

摘　　要：组密钥管理是组安全、多播安全中的核心问题.本文给出了密钥覆盖问题模型的建立过程,首次给出密钥覆盖问题(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.

关 键 词：组密钥管理 组合优化 计算复杂性 顶点覆盖问题 密钥覆盖问题 密钥图 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]