| 密钥覆盖问题的NP完全性证明 |
| |
| 引用本文： | 陆正福,洪孙焱.密钥覆盖问题的NP完全性证明[J].云南大学学报(自然科学版),2006,28(3):201-205. |
| |
| 作者姓名： | 陆正福 洪孙焱 |
| |
| 作者单位： | 云南大学,数学系,云南,昆明,650091 |
| |
| 基金项目： | 国家自然科学基金资助项目(10561009)，云南省自然科学基金资助项目(2002F0012M)，云南大学理(工)科校级重点科研项目资助(2003Z010C) |
| |
| 摘 要： | 给出了密钥覆盖问题的模型建立过程,并从顶点覆盖问题的判定形式出发,证明了密钥覆盖问题的判定形式是NP完全问题,为组通信安全的研究,尤其是多播安全的研究奠定了更为坚实的基础.
|
| 关 键 词： | 组密钥管理 组合优化 计算复杂性 顶点覆盖问题 密钥覆盖问题 |
| 文章编号： | 0258-7971(2006)03-0201-05 |
| 修稿时间： | 2005年4月4日 |
On the proof of the NP-completeness of key covering problem in the group rekeying |
| |
| LU Zheng-fu,HONG Sun-yan.On the proof of the NP-completeness of key covering problem in the group rekeying[J].Journal of Yunnan University(Natural Sciences),2006,28(3):201-205. |
| |
| Authors: | LU Zheng-fu HONG Sun-yan |
| |
| Institution: | Department of Mathematics, Yunnan University, Kunming 650091, China |
| |
| Abstract: | 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. |
| |
| Keywords: | group key management combinatorial optimization computational complexity vertex covering problem key covering problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《云南大学学报(自然科学版)》浏览原始摘要信息 |
| 点击此处可从《云南大学学报(自然科学版)》下载免费的PDF全文 |
