密钥覆盖问题的NP完全性证明  

On the proof of the NP-completeness of key covering problem in the group rekeying

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

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

出　　处：《云南大学学报（自然科学版）》2006年第3期201-205,共5页Journal of Yunnan University(Natural Sciences Edition)

基　　金：国家自然科学基金资助项目(10561009);云南省自然科学基金资助项目(2002F0012M);云南大学理(工)科校级重点科研项目资助(2003Z010C)

摘　　要：给出了密钥覆盖问题的模型建立过程,并从顶点覆盖问题的判定形式出发,证明了密钥覆盖问题的判定形式是NP完全问题,为组通信安全的研究,尤其是多播安全的研究奠定了更为坚实的基础.The process of modeling the key covering problem is preserted. And the NP-completeness of the decision version for the key covering problem is proved as well. Our proof is given based on the decision version of the vetex covering problem. Therefore, the further research on group security, especially for the multicast security, can have much solod foundation.

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

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