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

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

摘要: 给出了密钥覆盖问题的模型建立过程,并从顶点覆盖问题的判定形式出发,证明了密钥覆盖问题的判定形式是NP完全问题,为组通信安全的研究,尤其是多播安全的研究奠定了更为坚实的基础.

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.