论文部分内容阅读
摘要：本文基于HDPT给出组播逻辑密钥树的代价分析模型，提出一个改进的组播密钥管理方案L-R逻辑密钥树方案。本文给出了这个方案的设计思想和算法，并将这个方案用程序进行模拟实现。最后分析这个方案的代价，证明该方案是高效率，低代价的。
关键词：分层数据处理；组播；密钥更新代价；L-R逻辑密钥树
中图分类号：N37 文献标识码：A文章编号：1007-9599 (2010) 13-0000-01
A logical key tree management scheme Applying HDPT
Li Yan
(Liaoning College of Communications,Shenyang110122,China)
Abstract:The paper provides the cost analytical model of multicast logical key tree which applies HDPT. The author proposes an improved scheme termed as L-R logical key tree management scheme. The paper provides the design and calculation of the scheme, and realizes it in a simulation. Then the paper analyzes the cost of the scheme, and it shows clearly that the scheme proposed in the paper is high effect and low cost.
Keywords:Hierarchical Data Processing;Multicast;Re-key Cost; L-R Logical Key Tree
一、引言
随着流媒体在网络中广泛应用，对组播[1]技术研究越来越深入，组播有助于控制和减少网络流量。常见的密钥管理方案如GKMP[1]、Iolus[1]、LKH[2]等。如何使密钥更新的代价最小，何种结构才能实现系统性能最优，怎样根据动态的环境变化，得出一种适应性的密钥管理方案，是一个值得深入探讨的问题。
本文提出一种改进的组播密钥管理方案，并应用分层数据處理理论[3]进行了代价分析。应用分层数据处理可分析计算问题和设计有效数据结构。
二、组播逻辑密钥树代价分析模型
根据分层数据处理理论得出有向逻辑密钥树[4]的更新代价为： ，存储代价为： 。
对于有n个叶结点的d叉完全逻辑密钥树，则：
图1得出不同叉数不同节点总数密钥更新代价，密钥的更新代价受节点总数和树叉数影响。用相同的方法得到不同叉数不同节点数完全密钥树的存储代价比较图，存储代价随分支数增加而减少，在用户数相同情况下分支数越大，树的高度越小，存储代价越小。但当分支数大于等于4后，存储代价减小的趋势明显变弱。
当用户节点数分别为64~4096时，通过实验得到：星型结构和完全四叉树的更新代价在加入和离开概率p=q=0.17时交叉，当p=q<0.17时，完全4叉树更新代价优于星型结构，当p=q>0.17时，星型结构更新代价优于完全4叉树。
在源点数相同情况下，且源点的加入和离开概率无明显特征时，取叉数为4的完全逻辑密钥树最优。若源点的加入和离开概率有明显区别，则可根据源点的加入和离开概率构建相应的非平衡树，这样可以取得较好的更新代价。
三、L-R逻辑密钥树设计方案
根据用户的加入和离开概率对其分类，将加入和离开概率p<=0.17的用户在根节点的左侧构成完全4叉树，将它称为标准树子树，深度由符合条件的用户数量决定，将p>0.17的用户加入根节点右侧子树，这棵子树为星型结构。如图2所示。
将要加入和离开节点分类，p<=0.17在左侧子树采用完全4叉逻辑密钥树，对于加入和离开概率p>0.17在右侧采用GKMP密钥管理方案。
在非平衡逻辑密钥树上，若更新概率高的叶节点具有较小的更新路径，则密钥树的更新代价较小。
四、L-R逻辑密钥树方案代价分析
本文比较LKH与L-R方案的更新与存储代价。假设当前组播用户总数为n，L-R方案中成员总数为n，L-R逻辑密钥树方案左侧标准树成员数为n1，右侧星型子树成员数为n2，n=n1+n2则：L-R方案中 ， 。而LKH方案中 ， ，当 时，L-R方案更新代价优于LKH方案。
五、结论
本文将两种方案的更新代价和存储代价用Matlab计算后直观表示，可以明显看出L-R方案代价较低。综合上面的比较，L-R逻辑密钥树方案的存储代价明显优于LKH方案，并且当 时，L-R逻辑密钥树方案的更新代价优于LKH方案。所以总的来说本文提出的L-R逻辑密钥树方案性能较优。
参考文献：
[1]张斌,邬江兴.组播安全中的组密钥更新问题,计算机科学[J].2001,vol.28,45-48
[2]WONG C K,GOUDA M，LAM S.Secure group communication using key graphs[J].IEEE/ACM Trans on Networking,2000,8（1）:16-30
[3]Roberto Tamassia, Nikos Triandopoulos. Computational bounds on hierarchical data processing with applications to information security[A].Languages and Programming[C],Lisbon， Portugal,July 2005,153-165
[4]Zhou Fucai, Xu Jian， Cost of Multicast Logical Key Tree Based on Hierarchical Data Processing[J],Wuhan University Journal of Natural Sciences, 2006-11,11(5):1172－1176
关键词：分层数据处理；组播；密钥更新代价；L-R逻辑密钥树
中图分类号：N37 文献标识码：A文章编号：1007-9599 (2010) 13-0000-01
A logical key tree management scheme Applying HDPT
Li Yan
(Liaoning College of Communications,Shenyang110122,China)
Abstract:The paper provides the cost analytical model of multicast logical key tree which applies HDPT. The author proposes an improved scheme termed as L-R logical key tree management scheme. The paper provides the design and calculation of the scheme, and realizes it in a simulation. Then the paper analyzes the cost of the scheme, and it shows clearly that the scheme proposed in the paper is high effect and low cost.
Keywords:Hierarchical Data Processing;Multicast;Re-key Cost; L-R Logical Key Tree
一、引言
随着流媒体在网络中广泛应用，对组播[1]技术研究越来越深入，组播有助于控制和减少网络流量。常见的密钥管理方案如GKMP[1]、Iolus[1]、LKH[2]等。如何使密钥更新的代价最小，何种结构才能实现系统性能最优，怎样根据动态的环境变化，得出一种适应性的密钥管理方案，是一个值得深入探讨的问题。
本文提出一种改进的组播密钥管理方案，并应用分层数据處理理论[3]进行了代价分析。应用分层数据处理可分析计算问题和设计有效数据结构。
二、组播逻辑密钥树代价分析模型
根据分层数据处理理论得出有向逻辑密钥树[4]的更新代价为： ，存储代价为： 。
对于有n个叶结点的d叉完全逻辑密钥树，则：
图1得出不同叉数不同节点总数密钥更新代价，密钥的更新代价受节点总数和树叉数影响。用相同的方法得到不同叉数不同节点数完全密钥树的存储代价比较图，存储代价随分支数增加而减少，在用户数相同情况下分支数越大，树的高度越小，存储代价越小。但当分支数大于等于4后，存储代价减小的趋势明显变弱。
当用户节点数分别为64~4096时，通过实验得到：星型结构和完全四叉树的更新代价在加入和离开概率p=q=0.17时交叉，当p=q<0.17时，完全4叉树更新代价优于星型结构，当p=q>0.17时，星型结构更新代价优于完全4叉树。
在源点数相同情况下，且源点的加入和离开概率无明显特征时，取叉数为4的完全逻辑密钥树最优。若源点的加入和离开概率有明显区别，则可根据源点的加入和离开概率构建相应的非平衡树，这样可以取得较好的更新代价。
三、L-R逻辑密钥树设计方案
根据用户的加入和离开概率对其分类，将加入和离开概率p<=0.17的用户在根节点的左侧构成完全4叉树，将它称为标准树子树，深度由符合条件的用户数量决定，将p>0.17的用户加入根节点右侧子树，这棵子树为星型结构。如图2所示。
将要加入和离开节点分类，p<=0.17在左侧子树采用完全4叉逻辑密钥树，对于加入和离开概率p>0.17在右侧采用GKMP密钥管理方案。
在非平衡逻辑密钥树上，若更新概率高的叶节点具有较小的更新路径，则密钥树的更新代价较小。
四、L-R逻辑密钥树方案代价分析
本文比较LKH与L-R方案的更新与存储代价。假设当前组播用户总数为n，L-R方案中成员总数为n，L-R逻辑密钥树方案左侧标准树成员数为n1，右侧星型子树成员数为n2，n=n1+n2则：L-R方案中 ， 。而LKH方案中 ， ，当 时，L-R方案更新代价优于LKH方案。
五、结论
本文将两种方案的更新代价和存储代价用Matlab计算后直观表示，可以明显看出L-R方案代价较低。综合上面的比较，L-R逻辑密钥树方案的存储代价明显优于LKH方案，并且当 时，L-R逻辑密钥树方案的更新代价优于LKH方案。所以总的来说本文提出的L-R逻辑密钥树方案性能较优。
参考文献：
[1]张斌,邬江兴.组播安全中的组密钥更新问题,计算机科学[J].2001,vol.28,45-48
[2]WONG C K,GOUDA M，LAM S.Secure group communication using key graphs[J].IEEE/ACM Trans on Networking,2000,8（1）:16-30
[3]Roberto Tamassia, Nikos Triandopoulos. Computational bounds on hierarchical data processing with applications to information security[A].Languages and Programming[C],Lisbon， Portugal,July 2005,153-165
[4]Zhou Fucai, Xu Jian， Cost of Multicast Logical Key Tree Based on Hierarchical Data Processing[J],Wuhan University Journal of Natural Sciences, 2006-11,11(5):1172－1176