admin 由于数字化信息极易被复制、修改和传播，盗版现象日益严重，给相关权利人造成巨大的经济损失。广播加密技术解决版权保护问题并能有效地管理密钥。但用户量巨大的时候，通信量和用户端密钥存储量都急剧增加，为了解决这一问题，本文提出一个允许免费接收者的完全子树广播加密方案，当撤销用户很多的时候，显著降低了系统的通信量。
一、允许免费接收者的完全子树方案
1、 概念与定义
定义U是系统中所有用户集合， |U|=n；R是撤销用户集合，|R|=r；F是免费接收者集合，表示那些没有付费订阅服务却能解密广播消息的用户，|F|=f。
因子
，表示系统可忍受免费接收者的程度。
当FRratio=1时，系统完全开放广播，所有用户u∈U都能正确解密广播消息；当FRratio=0时，系统禁止免费接收者，只有授权用户u∈P能够正确解密广播消息，用于版权管理时，系统根据数字内容的受欢迎程度、订阅者数量、价格等参数确定某个合适的FRratio。
在满树中，v表示一个节点，T（v）表示以节点v为根节点的子树，L（v）、R（v）分别表示以节点v的左孩子和右孩子为根节点的子树。使用节点的序号表示某个节点，节点序号的标记方法是按层次从左到右序号依次增大，满二叉树的根节点序号为1，如图1：
2、方案描述
我们提出的完全子树广播加密方案是子集覆盖模型下的一个实例，在该方案中用户被组织成一个满二叉树的叶子节点，以某个节点vi为根的子树T（vi)中包含的用户集合为子集，给定撤销用户集合R，在Steiner树（R）中寻找U\R的一个覆盖。我们在完全子树方案的基础上，引入可控数量的免费接收者，减少覆盖集合的大小，从而减少通信量。
令fr=FRratio×|R|是系统允许的免费接收者数量，F是免费接收者集合，满足|F|=f≤fr。定义V={Vi1，Vi2，...Vit}是二叉树节点的集合，且满足：
当|V|=t取最小的时候，F为最优。
从上面的定义可以看出，集合V就是允许免费接收者条件下，在完全子树方案中的一个覆盖，集合V的大小决定了广播消息的长度。用户仍然同完全子树方案一样，存储自己到根节点路径上的密钥，大小为O（log（n））。
使集合V的大小尽可能小是一个最优化问题。定义OPT（i，T（v）），i=0，1...fr为在节点v的子树T（v）引入最多i个免费接收者，集合V大小最小。当i≥|T（v）∩R|时，允许的免费接收者数量已经超过了T（v）下的撤销用户，如果T（v）的所有用户都是撤销用户，OPT（i，T（v））=0，因为在增加这些撤销用户并不能带来益处，如果T（v）下并不都是撤销用
户，OPT（i，T（v））=1，因为可以使用一个密钥，使T（v）下的所有用户都能正确解密广播消息；如果节点v满足，L（v）∩R=_且R（v）∩R=_，那么OPT（i，T（v））=1，因为可以仅仅使用单个密钥，就使T（v）下的所有用户都能正确解密广播消息；否则对每个i（0≤i≤fr）0，有：
根据上述的最优化函数，可以使用动态规划计算出OPT（i，T（root））,，0≤i≤fr的值，并取最小值。方案的通信量低于完全子树方案，而且通信量的大小可以通过参数fr调节。但可以看出，尽管得到了最优的结果（不超过给定的免费接收者数量，通信量最小）使用动态规划求最优值非常耗时Onf2，当用户数量n很大的时候无法实用。为此，这里采用贪婪算法，以减少计算量。
方案将系统中的用户被组织为满二叉树的叶结点，为（R）（Steiner树）的每个节点vi增加2个标记，标记fvi=|T（v）∩R|，即在节点vi下撤销用户的数量，标记cvi等于T（vi）中包含的只有一个儿子节点的数量（即完全子树方法覆盖的数量），如图2所示。方案采用贪婪算法寻找免费接收者，并使用完全子树方案广播消息。
在（R）中，如果某个节点的f较小，而c较大，那么我们就可以在引入较少的免费接收者的同时降低较多的通信量。并且注意到当某个节点vi的标记c≤1，且其父节点有两个孩子，那么将该节点下的撤销用户作为免费接收者不会降低通信量。如图2，在节点A引入3个免费接收者不能降低通信量，节点B则可以。方案使用算法1标记免费接收者。首先，计算_（R）各个节点的标记c和f，然后选择f/c最小的节点，如果该节点的c≤1且其父节点有两个孩子，则将以该节点为根的子树从（R）中删除，否则，标记该节点下的撤销用户为免费接收者，然后将以该节点为根的子树从（R）中删除，并累计免费接收者数量f。持续上述操作，直至免费接收者数量达到fr=FRratio*|R|。
允许免费接收者的完全子树方案的初始化和解密算法与完全子树方案完全相同。广播算法，增加了若干步骤，具体描述如下：
广播算法：给定撤销用户集合R，广播中心设置FRratio，运行算法1产生免费接收者集合F，将F中的用户标记为授权用户，即R←R\F。随后的步骤，与完全子树方法完全相同。
3、存储和通信代价分析
方案基于完全子树方法，用户端的密钥量为O（log（n））。方案的通信量低于完全子树方案，因为算法1保证引入新的免费接收者一定能降低通信量，实际效果见实验评估。通信量的大小可以通过参数FRratio调节。
4、安全性分析
本方案可以暂时视那些免费接收者为授权用户，所以本方案的安全性可以等同于完全子树方案的安全，即完全抗串谋，且是信息论安全的。
方案中免费接收者并不是随机选择的（尽管在算法1的步骤5，当有若干个节点同时取得最小值时，可以引入随机化），在撤销用户集合R相对固定的情况下，某些用户可能总能成为免费接收者，他们就会倾向于不付费，而带来损失。当撤销用户集合R剧烈变化时，用户难以预测自己是否为免费接收者，所以方案更适合撤销用户集合R剧烈变化的应用，比如视频点播服务。
5、实验评估
图3显示了当系统用户总数n=65536，不同撤销用户数量，完全子树方案和本方案通信量的比较。随着撤销用户数量的逐渐增加，完全子树方案的通信量迅速增加。在FRratio=0.05的条件下，本方案通信量明显低于完全子树方案，且随着撤销用户数量的增加，这种优势就越明显。
图4 显示了当系统总人数n=65536，撤销用户数量r=3276时，允许不同数量免费接收者通信量的比较。随着FRratio的逐渐增大，系统地通信量明显降低。
由实验结果可以看出，允许免费接收者的完全子树方案在撤销用户数量较大时（撤消用户数量占系统总人数20%-50%）有较大的优势，因此适用于撤销用户集合较大的应用。
二、 结论
本文给出了一个有效的广播加密方案，并能够在允许的免费接收者数量和通信量等其他性能参数之间做出平衡。本方案适用无状态接收者，并且在撤销用户较大时，在通信量上比完全子树方案有显著优势。
小知识之Steiner树
Steiner树是总代价最小的分布树，它使连接特定图（graph）中的特定组成员所需的链路数最少。若考虑资源总量被大量的组使用的情况，那么使用资源较少最终就会减少产生拥塞的风险。Steiner树相当不稳定，树的形状随组中成员关系的改变而改变，且对大型网络缺少通用的解决方案。所以Steiner树只是一种理论模型，而非实用工具。目前，出现了许多Steiner树的次优启发式生成算法。
