【摘要】 本发明涉及一种基于AVL树的分布式组密钥更新方法，属于计算机网络安全领域。该 方法除了包括子密钥树形成阶段、子密钥树合并阶段两个常规阶段外，还包括AVL旋转阶 段：即若形成的新的密钥树失去平衡，则对该新的密钥树进行AVL旋转，直到它重新恢复 平衡为止；选择该新密钥树的所有的叶子节点全为新加入节点的子树的最左叶子节点作为 触发节点；开始发起整个密钥树的密钥更新过程。本发明基于AVL树优良的平衡性能，有 效地克服了已有的完全基于单向函数树的密钥管理方案中密钥树的结构失衡问题，减少了 用户的存储开销。 【专利类型】发明授权 【申请人】清华大学 【申请人类型】学校 【申请人地址】100084北京市海淀区清华园 【申请人地区】中国 【申请人城市】北京市 【申请人区县】海淀区 【申请号】CN200810102884.6 【申请日】2008-03-28 【申请年份】2008 【公开公告号】CN100586062C 【公开公告日】2010-01-27 【公开公告年份】2010 【授权公告号】CN100586062C 【授权公告日】2010-01-27 【授权公告年份】2010.0 【IPC分类号】H04L9/08; H04L12/18 【发明人】戴琼海; 尔桂花; 邓独 【主权项内容】1、一种基于AVL树的分布式组密钥更新方法，包括子密钥树形成阶段、子密钥树与 原密钥树合并阶段，其特征在于，还包括AVL旋转阶段； 所述子密钥树形成阶段，包括以下步骤： 1)对要加入组播系统的用户节点，如果不存在子密钥树，则创建一棵该用户节点的子 密钥树；如果已经存在子密钥树，则将该用户节点加入到该子密钥树中最浅的节点； 2)对要离开的用户节点，将它标记到离开用户节点集合； 所述子密钥树与原密钥树合并阶段，包括以下步骤： 3)若离开用户节点集合中没有要离开的节点，且该子密钥树与原密钥树的高度差不超 过2，则直接增加新的根节点，该子密钥树和原密钥树分别作为该根节点的左、右子树， 形成新的密钥树；若该子密钥树与原密钥树的高度差大于2，则将该子密钥树直接插入到 最浅的节点处，形成新的密钥树； 4)如果离开用户节点集合中有要离开的节点，则先将该子密钥树插入到原密钥树最浅 的节点处，然后，将要离开的节点从原密钥树中移除，形成新的密钥树； 5)选择以离开节点的兄弟节点作为根节点的子树的最左叶子节点为触发节点，由该节 点发起新的密钥树的密钥更新； 所述AVL旋转阶段包括以下步骤： 6)如果形成的新的密钥树失去平衡，则对该新的密钥树进行AVL旋转，直到它重新恢 复平衡为止； 7)选择该新密钥树的所有的叶子节点全为新加入节点的子树的最左叶子节点作为触 发节点； 8)由步骤5)和7)中的触发节点开始发起整个密钥树的密钥更新过程； 其中，所述最浅的节点是指到根节点距离最短的叶子节点。 【当前权利人】清华大学 【当前专利权人地址】北京市海淀区清华园 【专利权人类型】公立 【统一社会信用代码】12100000400000624D 【引证次数】2.0 【他引次数】2.0 【家族引证次数】2.0 【家族被引证次数】11
