（应用数学专业论文）网络编码与密钥共享体制.pdf

马听宁：网络编码与密钥共享体制 中文摘要中又捅姜 网络编码是信息论领域中信息处理和传输理论研究的一个重大突破。与传统网络的中 间节点只复制和传输数据包不一样，利用网络编码，中间节点可以对数据包进行编码，从 而能够提升网络吞吐量，均衡网络负载和提高带宽利用率等。如今，有关网络编码的研究 已经引起了学术界的高度重视，网络编码已经成为网络信息领域最受瞩目的热点之一。密 钥共享的概念和密钥共享体制是针对密钥管理中密钥的泄露问题和遗失问题提出的。自从 b l a k l e y 和s h a m i r 于1 9 7 9 年分别独立提出了密钥共享的概念以来，人们在密钥共享理论 和信息安全理论与技术与应用方面取得了丰硕的成果。而且，密钥共享理论与技术在密码 学和信息安全理论与技术中已占有重要的地位。 本文结合密钥共享思想，给出了单信源单层多样网络的线性网络编码构造，并且说明 了通过该构造，可以很好的提高网络拓扑结构的鲁棒性。其主要安排如下： 第一部分，介绍网络编码。包括网络编码的基本原理，网络编码的优缺点，现有的一 些网络编码的构造方法以及网络编码的主要应用。 第二部分，相关知识的介绍。与本文相关的密钥共享体制的一些概念，包括门限共享 体制，存取结构，单调张成方案等概念。 第三部分，结合密钥共享思想给出单信源单层多样网络的一种线性网络编码构造。本 文证明了一个单信源单层多样系统，线性网络编码机制一定存在，并确定了这个系统 中通过密钥共享得到的线性网络编码的编码次数范围；利用单调张成方案来构造网络 编码，并推广到带权重的网络系统中，根据对偶线性密钥共享体制，提出了对偶的单 信源单层多样网络的概念；利用基于二次剩余的一类非线性密钥共享体制来构造特殊 网络的一类非线性网络编码。 关键词：网络编码密钥共享体制单调张成方案 扬州大学硕士学位论文 a b s t r a c t 2 一 n e t w o r kc o d i n g ，k n o w na so n eo ft h em o s ti m p o r t a n tb r e a k t h r o u g h so nt h et h e o r yo fi n f o r m a t i o n p r o c e s s i n ga n dt r a n s m i s s i o n w i t hn e t w o r kc o d i n g ，i n s t e a do fs i m p l yr e p l i c a t i n ga n df o r w a r d i n g d a t a ，i n t e r m e d i a t en o d e sm a ys e n do u tp a c k e t st h a ta r ec o d e so fp r e v i o u s l yr e c e i v e di n f o r m a t i o n n e t w o r kc o d i n gh a sm a n ya d v a n t a g e s ，s u c ha sp r o v i d i n gh i g h e rn e t w o r kt h r o u g h p u t ，b a l a n c i n g t h et r a f f i ca n di m p r o v i n gb a n d w i d t he f f i c i e n t l y , e t c n o w , t h er e s e a r c ho fn e t w o r kc o d i n gh a s r e c e i v e dg r e a ti n t e r e s t sa n dh a sb e c o m eo n eo ft h em o s ta t t r a c t i v ef i e l d si nn e t w o r ki n f o r m a t i o n t h e o r y t h ec o n c e p to fs e c r e ts h a r i n ga n ds e c r e ts h a r i n gs y s t e mi sr a i s e df o r t h e d i s c l o s u r eo fk e y s i n c eb l a k l e ya n ds h a m i rb r o u g h tf o r w a r dt h ec o n c e p to fs e c r e ts h a r i n gi n19 7 9 ，w eh a v em a d e g r e a ta c h i e v e m e n t si ns e c r e ts h a r i n gs y s t e ma n di n f o r m a t i o ns e c u r i t yt h e o r y m o r e o v e r , t h e s e c r e ts h a r i n gt h e o r yh a sp l a y e da ni m p o r t a n tr o l ei nc r y p t o g r a p h ya n di n f o r m a t i o ns e c u r i t y t h e o r y i nt h ef i r s tp a r t ，t h eb a c k g r o u n do fn e t w o r kc o d i n gi se x p o u n d e d i n c l u d i n gt h eb a s i c p r i n c i p l e so f n e t w o r kc o d i n g ，t h ea d v a n t a g e sa n dd i s a d v a n t a g e so fn e t w o r kc o d i n g ，s o m eo ft h e e x i s t i n gm e t h o d so f n e t w o r kc o d i n g sc o n s t r u c t i o na n dt h em a i na p p l i c a t i o no f n e t w o r kc o d i n g i nt h es e c o n dp a r t ，w eg i v et h ei n t e r r e l a t e dk n o w l e d g e an u m b e ro fs e c r e ts h a r i n gs y s t e m c o n c e p t sa s s o c i a t e dw i t ht h i sa r t i c l e ，i n c l u d i n gt h et h r e s h o l ds h a r i n gs y s t e m ，t h ec o n c e p to f m o n o t o n es p a np r o g r a m s ，e t c i nt h et h i r dp a r t ，t h i sa r t i c l eg i v eal i n e a rn e t w o r kc o d i n g ss t r u c t u r eo fs i n g l e s o u r c e s i n g l e l a y e rd i v e r s i t yn e t w o r ks y s t e mw h i c hc o m b i n ew i t ht h ei d e a so fs e c r e ts h a r i n gs y s t e m i n t h i sp a p e r , w eh a v ep r o v e dt h a ti fas i n g l e - s o u r c es i n g l e l a y e rd i v e r s i t ys y s t e me x i s t s ，t h el i n e a r n e t w o r kc o d i n gm e c h a n i s m sm u s te x i s t ，a n dw eg a v et h ec e r t a i nr a n g eo ft h a tc o d ef r e q u e n c y ； w eu s et h ei d e ao fm o n o t o n es p a np r o g r a m si nn e t w o r kc o d i n g ，a n de x t e n di tt ot h en e t w o r k s y s t e mw i t ht h ew e i g h t ；w eg i v et h ec o n c e p to fac o u p l es i n g l e - - l a y e rs i n g l e s o u r c ed i v e r s i t y n e t w o r k sb a s e do nt h ec o u p l el i n e a rs e c r e ts h a r i n gs y s t e m ；a n du s i n gt h en o n l i n e a rs e c r e t s h a r i n gs y s t e mw h i c hi sb a s e do nq u a d r a t i cr e s i d u e ，w ec o n s t r u c tt h en o n l i n e a rn e t w o r kc o d i n g o fas p e c i a ln e t w o r ks y s t e m k e y w o r d s ：n e t w o r kc o d i n g s e c r e ts h a r i n gs y s t e mm o n o t o n es p a np r o g r a m s 扬州大学硕士学位论文 扬州大学学位论文原创性声明和版权使用授权书 学位论文原创性声明 本人声明：所呈交的学位论文是在导师指导下独立进行研究工作所取得的研究成果 论文中已经标明引用的内容外，本论文不包含其他个人或集体已经发表的研究成果对本文 的研究做出贡献的个人和集体，均己在文中以明确方式标明本声明的法律结果由本人承担 学位论文储签名：乃b 巧寄 签字日期：矽，7 年多月4 日 学位论文版权使用授权书 本人完全了解学校有关保留、使用学位论文的规定，即：学校有权保留并向国家有关 部门或机构送交学位论文的复印件和电子文档，允许论文被查阅和借阅本人授权扬州大学 呵以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存、汇编学位论文同时授权中国科学技术信息研究所将本学位论文收录到中 国学位论文全文数据库，并通过网络向社会公众提供信息服务 学位论文作者签名： 弓黟悖 签字日期：z 矿刁年z 月牛日 导师签名： 魂乞也 签字日期：1 钆月中日 马昕宁：网络编码与密钥共享体制 1 、引言 2 l 世纪，网络编码( n e t w o r kc o d i n g ) 的出现绝对是信息论领域的一个重大突破。2 0 0 0 年，香港中文大学的r u d o l f a h l s w e d e ，r a y m o n dw y e u n g 等人在i e e e 信息论会刊上发表的 文章【1 1 ，首次提出了网络编码的概念，并且从理论上证明了该结论。他们从蝶状拓扑( 图1 ) 为例证明该理论可以达到网络的最大容量：考虑具有单位容量、无时延无环有向图中，信宿 x 和y 能否同时收到2b i t 信息。在图1 ( a ) 由于链路船的瓶颈只能传送1b i t ，从而y 可以达到2 b i t ，而x 只能收到1b i t ，平均吞吐量为1 5b i t ；( b ) 中采用网络编码后，w z 可传送a 与b 的编码 ( 此处为异或) ，两个信宿通过解码可以同时收到2b i t 信息，达到该网络的最大容量。此理论一 经提出立即引起了学术界的广泛重视，其研究和应用已成为信息论领域的一个新热点。 l 鞋ll 秘 图1 ：图1 ( a ) 路由方法；图1 ( b ) 网络编码方法 网络编码彻底改变了通信网络中信息处理和传输的方式，国际许多著名大学和研究机 构，国外许多著名大学，如普林斯顿大掣2 1 、麻省理工大学【3 1 、瑞z t z e p f l 学院4 1 等以及多家 i t 公司的研究中心，包括微软研究院【5 1 、贝尔实验室【6 1 、at & t 的香农信息实验室【7 1 等都在 积极开展对网络编码理论和应用的研究；网络编码也逐渐引起了国内学术界的关注和重视 我国的清华大学【8 1 、南京大学【9 1 、西安电子科技大学【1 0 】等对网络编码进行了探索。 扬州大学硕+ 学位论文 2 、网络编码介绍 4 2 1 网络编码的基本原理 _ 在组播通信网络中，可以在网络的中继节点上对接收到的信息进行一定形式的编码 处理，然后再传输出去，而不是像传统网络中那样在中继节点上只是进行存储转发； 一在信宿节点上，通过一定的处理方式，译出信源节点所发的信息； 一根据图论中的“最小割最大流定理”可知，一个网络可以传输的最大流量等于其最小 割： _ 传统的存储转发式路由方式，并不能实现网络的最大流传输，所以不是最佳的； 在中继节点上对接收信息进行编码，然后再传输出去，接收端根据自己的要求译出 所需信息，则可以大大提高网络的传输速率，充分利用网络中的链路资源，从而实 现最小割最大流定理所给定的可传输信息的上限； 一传统的路由方式可以看成是网络编码的一种特殊形式。 2 2网络编码的主要优缺点 网络编码提出的初衷是为使多播传输达到理论上的最大传输容量，从而能取得较路由 多播更好的网络吞吐量。但随着研究的深入，网络编码其它方面的优点也体现出来，如均 衡网络负载、提升带宽利用率等。如果将网络编码与其它应用相结合，则能提升该应用系 统的相关性能。 1 提升网络吞吐量 提升吞吐量是网络编码最主要的优点。无论是均匀链路还是非均匀链路，网络编码均 能够获得更高的多播容量，而且对于节点平均度数越大，网络编码在网络吞吐量上的优势 越明显【1 1 1 。从理论上可证明：如果q 为信源节点的符号空间，m 为通信网络中的节点数 目，则对于每条链路都是单位容量的通信网络，基于网络编码的多播的吞吐量是路由多播 的q ( 1 0 9 帅掣2 1 。 2 均衡网络负载 网络编码多播可有效利用除多播树路径外其它的网络链路，可将网络流量分布于更广 泛的网络上，从而均衡网络负载。图2 ( a ) 所示的通信网络，其各链路容量为2 。图2 ( b ) 表示 的是基于多播树的路由多播，为使各个信宿节点达到最大传输容量，该多播共使用s u 、u x 、 u y 、s w i , w z 等共5 条链路，且每条链路上传输的可行流为2 ；图2 ( c ) 表示的是基于网络编 码的多播，假定信源节点s 对发送至链路s v 的信息进行模二加操作，则链路s v 、v x 和v z 马听宁：网络编码与密钥共享体制 上传输的信息均为a 0 6 ， 最终信宿x ，y 和z 均能同时收到a 和b 。容易看出，图2 ( c ) 所示 的网络编码多播所用的传输链路为9 条，比图2 ( b ) 的多播树传输要多4 条链路，即利用了更 广泛的通信链路，因此均衡了网络负载。网络编码的这种特性，有助于解决网络拥塞等问 题。 旌i ba , b l , b l 复)( b 0 图2 ：单信源三信宿网络 3 提高带宽利用率 提高网络带宽利用率是网络编码的另一个显著的优点。在图2 ( b ) 中的路由多播中，为 了使得信宿x ，y 和z 能够同时收n 2 个单位的信息，共使用了5 条通信链路，每条链路传输 可行流为2 ，因此其消耗的总带宽为：5 2 = 1 0 。在图3 ( c ) 表示的网络编码多播中，共使用 了9 条链路，每条链路传输可行流为1 ，其消耗总带宽为：9 x l = 9 ，因此带宽消耗节省了1 0 ， 提高了网络带宽利用率。 4 提高网络鲁棒性 网络编码可以对相关信源的数据进行压缩，减少网络中传输的信息量，从而减少节点 能量消耗，延长网络的生存周期。通过网络编码可以抵抗网络中的链路和节点的非各态历 经失败对网络链接的影响，提高网络链接的鲁棒性，减少网络管理的开销。 网络编码机制使信息更加分散，等同于将信息进行了隐藏，更难窃听，提高了信息安 全性。节点需要具有译码功能，同时要求得到足够的数据l 能正确解码，信息很难被窃听， 同时网络编码还可以防止拥塞方面的侵害。网络编码在信息安全领域的应用产生了一种基 于数据包的随机网络编码检测策略，对原数据进行的简单多项式函数哈希变换，然后把得 到的结果添加到原始数据包中。接收节点通过比较解码后的数据和哈希值就可以判断数据 包是否被修改过，这样就可以防止中间人攻击，提高数据的安全系数。 虽然网络编码优点突出，但运用网络编码增加了计算的复杂性，而且网路节点需要缓 存足够的输入信息，因此编码操作增加了传输时延和节点的额外的i o 、c p u 消耗。一些 学者对网络编码的综合性能进行了初步的研究和探讨1 1 3 1 4 】。统计数据表明，即使应用最有 扬州大学硕士学位论文 6 一 效的随机网络编码，其编码和译码的时间也不容忽视【1 4 】。此外，应用网络编码还存在同步 问题，这主要是由于信宿节点必须等待收到足够的编码信息，才能开始译码。同步问题给 在实时系统中应用网络编码提出了挑战。 2 3 网络编码的构造 网络编码根据节点的输入和输出关系可分为线性网络编码和非线性网络编码，根据编 码系数生成的随机性可分为随机网络编码和确定网络编码。下面介绍的是目前比较成熟的 单源无环组播网络的网络编码构造方法，其分为集中式和分布式两类。 1 集中式网络编码 ( 1 ) 代数法 代数法的本质是通过对矩阵行列式的研究，来判定网络编码的存在性，并构造网络编 码。代数法将构建网络编码问题归结为求解系统转移矩阵的问题，通过寻找一组使行列式 不为0 的参数来求解网络编码。k o e t t e r 等人在文献 1 6 ，1 7 】中给出了网络编码构造的代数框 架，将系统转移矩阵m 分解为i 丁1 个子矩m 。，m 2 ，m i 州，通过构造一组参数使得每个子矩 阵的行列式非o ，从而得到网络编码解。基于代数法的构造算法的优点在于可借助成熟的 矩阵理论分析各类拓扑结构的网络编码问题，其缺点是可扩展性差，计算量大。 ( 2 ) 信息流法 信息流法利用解耦技术，将网络编码问题分解为确定编码子图和给子图分配码字两个 子问题分别求解。j a g g i 等人【1 8 】给出了一个多项式l f j - b j 复杂度的网络编码构造算法，分为两 个步骤：首先采用流算法为每个信宿找到从信源到信宿的聆条边不重叠的路径集合，然后 采用贪心策略对已知路径的边按拓扑顺序分配线性码，并保证任意信宿的n 条入边上的全 局编码向量线性独立，且能扩张成有限域，从而获得网络编码解。信息流法的优点在于解 耦合的两个子问题可结合成熟的优化理论采用分布式算法分别求解，难点在于保证所有信 宿的入边上的编码向量均线性独立。 ( 3 ) 其他方法 除了以上两类构造方法外，还有冲突图法、矩阵满秩法、图染色法等几种构造方法。 s u n d a r a r a j a n 等人【1 9 】利用冲突图理论模型将网络编码问题转化为受约束的链路状态分配问 题，并通过在冲突图中寻找特殊稳定集的方法进行求解。该方法的一个缺点是随着字母表 的增大引起冲突图爆炸，导致求解困难。文献 2 0 从构造混合矩阵满秩的角度求解组播网 络编码，并给出一种多项式复杂度的确定性构造算法。f r a g o u l i - 等) k 2 u 利用解耦技术获得 网络的最小子树图，然后采用对图顶点染色的贪心策略给出单源组播网络的网络编码解。 马昕宁：网络编码与密钥共享体制 7 2 分布式编码方法 ( 1 ) 确定系数构造法 文献 1 5 】首次针对组播网络提出了确定系数的分布式网络编码算法，其核心思想是将 网络拓扑分解成多个子树，并保证每个子树的编码矢量属于其父树编码矢量的扩张空间， 且任意两个子树的共有信宿的编码矢量均线性无关。该方法具有良好的可扩展性，但只是 个次优的算法，所需的字母表空间随节点规模呈线性增长。 ( 2 ) 随机系数构造法 h o 等人【2 2 1 给出了一种随机系数的分布式网络编码算法，其编码系数从有限域中均匀随 机选取。该方法对线性相关的信源具有信息压缩作用，适用于链路动态变化的场景，当给 定的字母表足够大时能渐进达到最大组播速率，具有很强的实用性。 2 4网络编码的应用 网络编码起源于多播传输，主要是为解决多播传输中的最大流问题，但是随着研究的 不断深入，网络编码在其他地方的应用也越来越受到人们的关注。下面将以无线网络、应 用层多播和p 2 p 网络为例，总结网络编码的几种典型应用。 1 无线网络 由于无线链路的不可靠性和物理层广播特性，应用网络编码，可以解决传统路由、跨 层设计等技术无法解决的问题。具体来说，网络编码在无线网络中可以提高网络的吞吐量， 尤其是多播吞吐量；可以减少数据包的传播次数，降低无线发送能耗；采用随机网络编码， 即使网络部分节点或链路失效，最终在目的节点仍然能恢复原始数据，增强网络的容错性 和鲁棒性；不需要复杂的加密算法，采用网络编码就可以提高网络的安全性等。其中，网 络编码在无线自组织网络、无线传感器网络及无线网状网络中的应用较为突出。文献【2 3 、 【2 4 、 2 5 对这些应用分别有比较详细的介绍。 2 应用层多播 网络层多播技术( n e t w o r kl a y e rm u l t i c a s t ) 被认为是提供一到多或者多对多服务的最佳 方式，但是由于技术上和非技术上的原因导致网络层多播并没有在目前的i n t e r n e t 上得到广 泛的实现。因此，出现了一种替代的解决方案就是：把多播服务从网络层转移到应用层作 为应用层服务实现，即应用层多播( a p p l i c a t i o nl a y e rm u l t i c a s t ) 。网络层多播中的信息流由 路由器转发，而在应用层多播中则由端主机转发，端主机具有一定的计算能力，这为网络 编码提供了良好的应用环境。而且，应用层多播利用的覆盖网络的拓扑不如物理层那样固 定，可以按需变化，这也恰好可以利用网络编码对动态网络适应性强的优势。在文献 2 6 】 扬州大学硕十学位论文 中z h u y i n g 给出了网络编码在应用层多播应用。 3 p 2 p 网络 近年来，对等计算( p e e r t o p e e r ，p 2 p ) 迅速成为网络界关注的热门话题之一。p 2 p 已成 为宽带的杀手，目前p 2 p 应用占宽带流量5 0 一6 0 ( 白天) 直至9 0 ( 晚上) ，占企业用户 的4 0 。m p 3 和视频文件共享下载的p 2 p 流已成为宽带互联网业务的主流，基于p 2 p 的即时 通信，互联网电话和网络电视发展迅速，p 2 p 协同计算和网格方兴未艾。网络编码的出现， 有助于从内部机制上改善p 2 p 的传输效率，提升其性能，大大的节约了带宽资源。微软公 司开发的基于网络编码的p 2 p 文件共享系统“雪崩”( a v a l a n c h e ) 就是运用了其原理。 马昕宁：网络编码与密钥共享体制 3 、相关知识 3 1 门限密钥共享体制 9 一 密钥共享的概念和密钥共享体制是针对密钥管理中的密钥泄露问题和遗失问题提出 的。1 9 7 9 年，b l a k l e y j 羽有限几何方法设计了门限密钥共享体制，s h a m i r 厍j 多项式插值的算 法设计了门限密钥共享体制。 定义3 1 1 t 2 7 】： 设f ，n 为两个正整数，t n 。p = 只，l 是丹个共享密钥的参与者的集合， 也称为受托人集合。一个( f ，玎1 门限密钥共享体制是指：如果玎个参与者要共享密钥s ，通 常称s 为主密钥，则需要有一个密钥管理中心，用只表示，以及满足重构要求和安全性要 求的两个算法，通常称为分配算法和重构算法( 或恢复算法) 。密钥管理中心只利用分配算 法和主密钥s 生成刀个值墨，s 。，称为子密钥。然后，r 将子密钥墨( 1 f 刀) 秘密地发送 给参与者霉，只不得向外泄露s ，。这里，重构要求是指：集合p 中的任何f 个或者多余r 个 的参与者的子密钥放在一起，通过重构算法可以恢复出主密钥s 。由此推出，即使，l t 个 参与者遗失了自密钥，剩下的f 个参与者任然可以恢复出主密钥。安全性要求是指在已知 少于，个子密钥的信息时，不能恢复出主密钥s ，即少于t 个参与者即使合谋也得不到主密 钥。需要指出，上面提到的子密钥分配算法和主密钥重构算法都是公开的，而且主密钥重 构算法是由分配算法所决定的，或者说，当设计分配算法时，就蕴含着同时给出相应的重 构算法。密钥管理中心是可信的第三方，它不会泄露主密钥信息和欺骗参与者。 下面介绍s h a m i r 的( f ，n ) 门限密钥共享体制，它是最简单，最有效，也是最实用的一类 密钥共享体制。它的分配算法和重构算法如下： 分配算法：设为g 元有限域，q 是素数并且g 刀。为了使集合p = 墨，只) 中的n 个 参与者共享主密钥s ，s 只，密钥管理中心e o 按下面的步骤进行工作： 步骤1 ：昂秘密地在c 中一致地随机选取t - 1 个元素，记为a i ，a t - l 并且取x 为变元 t - 1 的多项式厂( x ) = s + 。 ，= l 步骤2 ：对于l i ，z ，昂计算f ( i ) ，记为y = s ( i ) 。 步骤3 ：对于1 i 以，r 秘密地将( f ，m ) 分配给露，这可通过一个秘密安全信道传输完 成，暑不得向任何人泄露 。至此，e o 的任务即告完成。 重构算法：不失一般性，设置，另是p 中任意选定，( ，) 个，这，个参与者掌握的全 扬州大学硕十学 i 7 ：论文 部子密钥集合为 ( 1 ，y ；) ，( 2 ，m ) ) 。考虑下面的方程组： 1 2 ： ， 皇， = ( 3 1 1 ) 。 l o 式( 3 1 1 ) 可以看做f 个变元的线性方程组，系数矩阵的秩是r ，这由l ，2 ，刀在只中两两不同 和范德蒙矩阵的性质保证。事实上，它的任何不同，行构成f x t 的范德蒙矩阵，所以是秩为 ，的可逆阵。因此当，t 时，s ，q ，a h 是它的唯一解，于是得到主密钥s 。 对于z c o 时成立) ，也就是( 3 ，4 ) 门限 密钥共享体制的极小存取结构： 么最= 彳尸l | 彳| - 3 ) - - i s ，e ，e ) ， e ，e ，只) ， e ，e ，只) ， 岛，e ，e ) ) 的情况。根据( f ，n ) f - 1 限密钥共享体制的分配算法，给出这个网络拓扑的种网络编码方式。 编码器在e ( 口，b ，c ) 中随机的选取2 个元素：_ = 2 b + c ，= a + 2 b + 3 c ，并取以x 为变 哥飞隧 扬州大学硕士学位论文 1 4 _ 一 2 元的多项式( x ) = j + x 7 = 口+ 6 + c + ( 2 6 + c ) x + ( 口+ 2 6 + 3 c ) x 2 为编码函数，计算厂( _ ) ， y j = 厂( _ ) 。s 取口+ 6 + c ，其中+ 运算是在有限域中进行的。 y l = f ( 1 ) = 口+ 6 + c + 2 6 + c + 口+ 2 6 + 3 c = 2 a ； 蜴= s ( 2 ) = a + b + c + 2 ( 2 b + c ) + 4 ( a + 2 b + 3 c ) = 3 6 ； 乃= f ( 3 ) = 口+ 6 + c + 3 ( 2 6 + c ) + 4 ( 口+ 2 6 + 3 c ) = c ； 儿= f ( 4 ) = 口+ 6 十c + 4 ( 2 6 + c ) + ( 口+ 2 6 + 3 c ) = 2 a + b + 3 c ； 那么可以在边只，i = 1 , 2 ，3 ，4 上分别传输符号2 口，3 b ，c ，2 a + b + 3 c 。 根据定义3 2 2 对应的全局编码核为： im = 2 a l此= 3 b 再e 考虑方程组：l乃= c ( 4 1 。1 ) ，显然方程组( 4 1 1 ) 中任意三个方程都能 【y 4 = 2 a + b + 3 c 解出口，b ，c ，也就是说互，五，互，正通过求解方程组( 4 1 1 ) 中任意三个方程来恢复出信源 信息x = ( c l , b ，c ) 。 这样我们就得到一种网络编码方案，而且显然这种方案是线性的，同时对于这个单信 源网络达到了网络的最大流。下面我们根据随机数的选取再获得另外一种方案。 方案2 ：同理，在e ( 口，b ，c ) 中再取一组互异随机元素：= a + 3 b + c ，r 2 = a + 2 b + 2 c ， 2 则编码函数为：( x ) = s + x = 口+ 6 + c + o + 3 6 + c ) x + ( a + 2 6 + 2 c ) x 2 ，显然，随机元素 f - l 一、j、一、j、，_、 2 o 0 o 3 o 0 o 2 1 3 ，。，、，。l，。，、，。，。一 = = = l l 厶 厶 厶 矗 马昕宁：网络编码与密钥共享体制 选取的不同，编码函数是有区别的，同样取s = 口+ 6 + c ，计算厂( _ ) ，记乃= 厂( _ ) 。 边只上传输：m = f ( 1 ) = 口+ 6 + c + 口+ 3 6 + c + 口+ 2 6 + 2 c = 3 a + b + 4 c ； 边上传输：y 2 = 厂( 2 ) = a + b + c + 2 ( a + 3 b + c ) + 4 ( a + 2 b + 2 c ) = 2 a + c ； 边e 上传输：y 3 = 厂( 3 ) = a + b + c + 3 ( a + 3 b + c ) + 4 ( a + 2 b + 2 c ) = 3 a + 3 b + 2 c ； 边只上传输：y 4 = f ( 4 ) = a + b + c + 4 ( a + 3 b + c ) + ( a + 2 b + 2 c ) = a + 2 c 。 根据定义3 2 2 对应的全局编码核为： i3 口+ b + 4 c = y l l2 a + c = y 2 考虑e 中的方程组l3 a + 3 b + 2 c = y 3 ( 4 1 2 ) ，n t 羊r , ，互，互，乃通过求解方 【a + 2 c = y 4 程组( 4 1 2 ) 中任意三个方程来恢复出信源信息x = ( 口，b ，c ) 。 两种方案的比较：上面的，是随机选取的，但是随机选取有一定限制，这种限制主 要是为了保证信宿节点能够恢复出信息消息，这一点下面本文将进行讨论。同时随机数选 取的不同则得到的方案是不一样的，不同方案的繁易程度不同。在网络编码中把一次+ ” 运算看成是一次编码，那么我们看到在方案1 中编码次数为2 ，而在方案2 中编码次数为6 ， 显然方案l 优于2 ，在下面我们在一般性中，将进一步讨论什么时候所决定的方案编码次数 最j 。 、，i，、，、，l、，、 1 4 2 o 1 3 3 2 l 0 2 ，。一，。，l，。l，。，。一 l l = i i = 厶 厶 厶 厶 扬州大学硕十学何论文 1 6 _ 一 4 2 一般的单信源单层多样系统 上面的简单例子可以看成一个简单的单信源单层多样系统可以看成一个门限密钥共 享体制，接下来我们讨论有n 个编码器即以个参与者的情况。为了作图和研究的方便这里 我们做2 点假设： ( 1 ) 每个信宿节点的最大流等于，； ( 2 ) 最大流等于t 的信宿节点都存在。 假设说明：( 1 ) 中要求每个信宿节点的最大流等于f ，这样如果某个信宿节点的最大 流大于f ，则该节点更能够恢复出信源信息。( 2 ) 中要求最大流等于r 的信宿节点都存在， 其实这样的假设要求是很高的，但是下面我们将证明对于这样高要求的网络同样可以根据 门限密钥共享体制得到对应的网络编码机制，那么对于简单的情况即只有部分最大流等于 t 的信宿节点存在的网络拓扑结构的也相应的解决了。 图6 是一个刀个编码器的单信源单层多样系统所对应的网络模型，这里可以把这个网络 编码模型看成为一个简单的门限密钥共享模型。其中信源s 相当于密钥管理中心，信息 x = ( q ，a ：，a t ) 相当于主密钥，边e ，e ，1 i n 可以看成刀个参与者丘，1 f 力，边 e 只，1 i ，z 上传输的信息相当于子密钥( 为了表达方便，就把边表示为只) 。信宿节点相 当于极小存取结构中的极小授权集合。下面我们先通过b l a k e y 几何方法证明网络编码存在， 接着用s h a m i r 4 l 数方法给出了具体的编码方案。 ：s ) t 1 ) ( t z ) - 1 ) ( 。t d ) 图6 定理4 1 ：一个单信源单层多样系统的线性网络编码机制一定存在。 证明：信源s 发出信息x = ( q ，嘭，a t ) ，其中a l , 口：，q 为，维向量，则信息x = ( q ，a 2 ，q ) 马昕宁：网络编码与密钥共享体制 1 7 对应为实数域上f 维实欧氏空间r7 或有限域上的f 维仿射空间a g ( t ，q ) 中的一个点q 。信 宿要恢复出信源信息，即为恢复出点o 。取，为过点q 的一条直线，h 是r 或爿g ( ，q ) 中 的一个超平面，i th 广、l = o ，则在日中选取不同于q 的玎个不同的点k ，圪，圪，使得 k ，匕，圪中的任意f 个点都能生成超平面，将k 分配给参与者，于是得到( f ，聆) 门限密钥 共享体制。即一个信息恢复的过程就是一个恢复出r 或a g ( t ，q ) 中一个点的过程。而我们 知道一个( f ，玎) 门限密钥共享体制一定能够应用到一个线性网络编码机制中。所以一个单信 源单层多样系统线性网络编码机制一定是存在的。 定理4 1 说明个单信源单层多样系统线性网络编码机制一定是存在的，而且可以根据门 限密钥共享体制给出方案，但是我们知道b l a k e y 几何方法给出的方案不易于具体操作，下 面本文根据s h a m i r 代数方法给出具体的网络编码机制。 我们取域，其中g 为大于，2 的素数。编码器在( q ，哆，q ) 中随机选取f 一1 个互 异元素： 巧= m l l a l + m 1 2 a 2 + + m l r a t ， 吒= m 2 l a l + m 2 2 a 2 + + f q ， ，；一15 珑，一i 。l a l + m t 一1 ，2 a 2 + + 聊，- 1 ，a ，。 并取以x 为变元的多项式厂( x ) ：j 十艺x r 为编码函数，同样计算厂( _ ) ，记乃= ( 。) ， s = a l + a 2 + + a t ，则编码器刀条输出边上就得到信息y l ，y ：，y 。，同时有刀个方程如下： y l = s + 一2 lm l i a i + 一2 lm 2 i a f + + _ l f 口f l = + f + + 乙，一l ，f 口f f - lf = l f = 1 fff y 2 = s + 2 聊l f 呸+ 2 2 聊2 f q + + 2 卜1 m t _ l f q f = lf = lf = l ： ( 4 1 3 ) ， 一，7 tff 虬= s + ，z 口f + 刀2 聊2 以+ + 行卜1 _ l ，以 f ；1f = lf = 1 这样就确定了一个编码方案。 下面讨论这种方案能够满足要求，即信宿节点能够恢复出信源的消息。我们可以看到 扬州大学硕十学位论文 信宿互，互，是否能完全恢复出信源信息归结到方程组( 4 1 3 ) 中任取f 个方程在乞是否 能够解出信息= ( q ，a 2 ，q ) 。 这个方程用矩阵表示为： 1 2 卜 咒f 一 1 聊1 2 m f - 1 2 的秩为f ，这是由1 ，2 ，刀在中两两不同和范德蒙矩阵的性质 保证。要使方程组( 4 1 3 ) 中任取f 个方程在有唯一解， i 1 1 i l 聊1 l m 1 2 = i l ： ： i 。 l 聊h ，l 聊f _ 1 ，2 在中可逆就可以，也就是说这个随机数矩阵r 的行列式不为o 。这也是我们选取随机数 i ，眨，：一l 必须满足的条件。那么满足随机数矩阵r 的行列式不为0 的随机数存在吗? 下面 这个定理说明这样的随机数一定存在。 定理4 2 ：满足随机数矩阵r 的行列式不为o 的随机数巧，吃，一l 存在。 1 2： 形 。上，h工 一 厂 朋 吩 ，。一 一、l，l一 1 卜 卜 2 彤 1 2： 咒 、，、 ；“ 2 聆 帆 ，= 靶 一、，0 h d 阵 m ； 睛 广1 瑞 鸭 马听宁：网络编码与密钥共享体制 证明：记m o = ( 1 1 ，1 ) ，m i = ( m 1 i ，m 1 2 ，m 1 ，) ，m ，1 = ( m 川 l ，掰，- l 2 ，m ，- l ，) 。 我们容易知道a = 扣i a = ( 口，a ：，a ，) ，a i c j 为一线性子空间。显然d i m ( a ) t ，同时 d i m ( a ) d i m ( ( 1 ，o ，o ) ，( o ，1 ，o ) ，( o ，o ，1 ) ) ) = t ，所以d i m ( a ) = t 。所以由线性代数知 识我们知道聊。必可以扩充为a 的一极大无关组，即存在m ，m ：，m h 使得m 。，掰，m ：，m 为子空问a 的一组基，所以矩阵只的秩为，所以矩阵r 的行列式不为0 。 随机数的选取： 通过定理4 2 我们知道m 。必可以扩充为a 的一极大无关组，即存在m ，m ：，所h 使得 m 。，m 。，聊：，m h 为子空间a 的一组基。实际上我们在随机选取的时候可以进行如下操作： ( 1 ) 固定m 。； ( 2 ) 在a 中选取随机向量珑，使得胧，( m 。 ) ，随机选取向量垅：使得 班：萑( 所。，m 。) ) ，随机选取聊h 诺( 伽。，朋。，m m ) ) ； ( 3 ) 确定，眨，；一l 。 操作说明： ( 1 ) 满