防窃听的安全网络编码

基金项目：国家自然科学基金委员会与香港研究资助局联合科研基金(60731160626)

    网络编码的思想在1999年，由R W Yeung和Z Zhang在文献[1]中明确提出，其主要思想是改变传统网络中节点对收到的信息只能进行单一的存储-转发的路由功能，使之能够对收到的来自不同链路的信息进行处理(编码)，使其既能实现传统路由的存储-转发功能，又能实现对信息的处理，从而提高传输信息量，最后仍然使目的节点成功接收到所需信息。而2003年，Rudolf　Ahlswede、蔡宁、李硕彦和杨伟豪等在文献[2]中对网络编码的理论意义和应用价值进行了影响深远的论述，通过基于网络信息流的概念，证明了用网络编码的方法，能够使网络的传输容量达到网络多播的最大流限，即证明了多播容量等于从信源到信宿节点的最大流的最小值。突破了传统路由传输的“瓶颈”问题。

    网络编码概念的提出是通信领域的一项重大突破[1-2]，它融合了路由和传统编码，以一定的编码能力换取了传输的容量，使得网络的传输容量得到突破，达到了理论上的最大传输容量的上限。

    自网络编码的概念提出后，李硕彦、杨伟豪和蔡宁在文献[3]中证明了通过线性网络编码就可以达到网络多播的最大流限，而线性方法的编码和解码都相对简单，所以这就为网络编码的思想“以节点的计算能力来换取网络的信息传输容量”奠定了基础，而且文献[3]为网络编码的应用奠定了坚实的基础；R Koetter and M Medard在文献[4]中提出了网络编码的代数框架，并证明了存在满足多播容量的线性时不变编码；S Jaggi等在文献[5]中给出了构造线性网络多播的多项式时间算法；T Ho、R Koetter、M Medard、D R Karger and M Eros在文献[6]中提出了随机网络编码，并证明了通过随机线性网络编码，能以极大概率达到网络多播的最大流限，随机网络编码的提出拓宽了网络编码的适用范围，使得网络编码不再局限于确定的网络拓扑和集中式的算法。

    近几年，研究者们已将上面的结果拓宽到多个应用领域，其中，蔡宁和杨伟豪在文献[7]中利用分布式网络编码来纠正整个网络中的差错，并在文献[8]中论述了网络编码在安全方面的应用，为网络编码增加了新的应用领域。

    如果网络中所有节点对其输入信息进行线性编码，则称为线性网络编码，否则称为非线性网络编码；如果网络节点对信息进行编码的系数(局部编码核和全局编码核)是根据网络拓扑的特点事先给定的，则称为确定性网络编码。而随机网络编码则没有事先给定全局编码核，而是让网络中的中间节点随机选取局部编码核对信息进行编码，由此局部编码核计算出相应的全局编码核，然后把此全局编码核作为报头的一部分发送给收点，以此解出原始信息。

    图1所示的蝶型网络是通过网络编码实现多播最大容量的经典例子。

1 安全网络编码
    随着网络通信越来越广泛，对信息安全传输的要求越来越迫切，也越来越高。

    网络编码作为一种特殊的信息传输方式，它在很多方面可以达到一定的安全要求。

    网络通信中，按照攻击者的攻击方式，攻击主要分为以下两种：搭线窃听(被动攻击)和Byzantine攻击(主动攻击)。
密码技术是信息安全的核心技术，在网络编码出现以前，主要利用密码学领域中的诸如数据加密，哈希函数和消息认证等方式来确保数据的安全传输，如文献[9-10]中所述等。然而传统的密码学方法存在一定的局限性，如计算复杂度较大，数据传输速率较低，消息冗余较大等，因此需要寻找一些安全、高效的数据传输方式。虽然网络编码的初衷在于提高网络的吞吐量，然而随着进一步研究发现它也是一种构造安全网络传输的好方式。

    下面将介绍网络编码在数据安全传输中的应用。网络编码在安全中的应用主要包括两方面：抗搭线窃听和抗Byzantine攻击。本文主要关注抗搭线窃听的安全网络编码。

2 抗搭线窃听的安全网络编码
    多播是通信中应用较广的一种情形，蔡宁和杨伟豪首先在文献[8]中论述了网络编码在安全方面的应用，最先研究了单源无圈网络中数据的安全多播问题，给出了搭线窃听的网络通信模型。并且构造了窃听者无论窃听给定的窃听集集合中的哪个窃听集都无法恢复出原始信息，在信息论意义下安全的网络编码。

2.1 搭线窃听网络的通信模型
    网络模型：通信网络抽象为一个有限有向图G =(V, E )，其中V表示节点集，E 是通信链接的集合。有向图模型对有线网络和无线网络都适用。对于有线网络，有向边是简单的端对端的链接；对于无线网络，有向边由即时的信道实现(数据包可能由于衰退和碰撞而丢失)决定，连接着发送节点(信源)、中间节点和接收节点(信宿)。

    搭线窃听网络(CSWN)的模型包含5个组成部分：
    (1)有限有向无圈图G =(V, E )，其中V 是节点集，E 是边集，两节点间可以有多条有向边。

    (2)信源节点集S ：每个信源节点s以一定的速率随机生成取值于字母表M 的随机信息m s。

    (3)信宿节点集T：每个信宿节点t是可以无差错地恢复出某些信源发出的随机信息m s的合法用户。

    (4)搭线窃听集的集合?撰，?撰为边集E 的子集的集合；?撰中每个元素称为搭线窃听集合，每个搭线窃听的集合中的边可以被窃听者窃取到所传输的所有信息，但是窃听者所能窃听的所有边不能同时在多于一个窃听集合中。

    (5)边的容量R =[R(a,b )：(a ,b)∈E ]，R(a,b )表示 (a ,b)边上可传输的最大平均速率。

    五元组(G、S、T、?撰、R)为一个搭线窃听网络(CSWN)。对于一个CSWN，通信者知道窃听者的窃听集合?撰，但不知道?撰中的哪一个元素是搭线窃听集合。通信者的目的是以尽可能大的速率将信息从信源节点集S 传输到信宿节点集T，而且使得窃听者从搭线窃听集?撰中得不到任何信息m s，s∈S。在一个CSWN中，我们一般还假设窃听者知道通信者的编码策略，而且还可以尽可能地根据自己的知识和经验来选择搭线窃听集。要想达到上面的安全传输信息的目的，一般而言，通信者必须将要传输的信息m s随机化。令W 为独立随机变量集，其中的随机变量在指标集w 中一致分布。

    图2从信源发出的信息中，ｍ是消息本身，而k 是为了达到安全的随机数。图中红线是窃听集，但是一个时间内只允许敌手窃听其中的一条，这样接收节点T和T'能够安全接收到信源传来的消息ｍ。

2.2 抗搭线窃听的安全网络编码
    CSWN(G、S、T、?撰、R )的码{Ф(a,b)：(a ,b )∈E }称为可容许码，容量条件对于所有的(a ,b )∈E，n-1log|?字(a,b)| ≤R(a,b)；可解码条件)对于所有的t∈T，和所有的x, x '∈S, x≠x '，都有Фt(x,r )≠Фt(x ',r ')，对于?坌r≠r ', r、r '
∈W；安全条件?坌A∈?撰，H(S |X(A ))=H(S )其中X(A )={X(a,b),(a,b)∈A}，X(a,b)是对应于边(a,b)输出的随机变量。即S 和X(A )相互独立。

    蝶形图2中的编码就是CSWN上可容许码，任意3个红色信道之一可以被搭线窃听，m是安全消息，k是随机数。此例虽然简单，却说明了利用网络编码可达到安全通信，但没有考虑网络最大容量的问题。

    图3给出了一种CSWN上可达到最大容量的可容许码，其中f 是单向函数，此例中的网络编码不仅在任一红色信道，甚至在任一信道都被搭线窃听的情形下都是安全的，更重要的是它同时达到了网络的最大容量。

    蔡宁和杨伟豪在文献[8]中定义了一类线性CSWN码，给出了该线性CSWN码是可容许码的充分条件，并给出在满足充分条件的情况下如何构造可容许码，但是该充分条件的验证比较困难。

    文献[8]进而又给出了另一个容易验证的图论充分条件，并得到以下相应结果。

    (1)构造

• 选择合适的正整数n和r，其中r <n，信息M 从域F n-r q中随机选取(不一定是均匀分布)，独立的随机密钥K在域F rq上均匀分布，多播的信息是(m,k )，其中m是要保密的信息，k∈K是密钥，m和k都在源节点处生成，且令X =(M,K )。
• 选择域F nq上合适的n 维线性网络编码。
• 在每条信道e上将传输的信息X编码为Xfe，其中fe是信道e上的全局编码核。
  

    (2)充分条件(定理1)
    若存在域Fq上的n 维线性网络编码，满足?坌t∈T,dim(Vt )=n，对于任意的搭线窃听集合A∈?撰，dim(VA)≤r，则根据构造，对于q >|?撰 |，存在G上的可容许码。

    (3)图论充分条件(定理2)
    若存在G的一个子图G *=(V,E *)，其中E *?奂E，满足?坌t∈T,G *都存在从s到t的n条互不相交的路，?坌A∈?撰，E *中至多有r 条从s到的A的互不相交的路，则根据构造，对于q >max{|?撰|,|T |}，存在域Fq上G 的可容许码。

    (4)情形1
    根据安全网络编码的构造思想，若已经存在多播n个符号(m,k )(其中
|m |=n -r，|k |=r )的线性网络编码，?坌A∈?撰，令fA ={fe∈A}，若对所有的A∈?撰，都有dim(span(fA))≤r，则当基域Fq充分大时，可以找到b 1, b 2……bn -r∈F nq，使得对所有的A∈?撰，b 1, b 2……bn -r和fA的极大线性无关组都是线性独立的。将b 1, b 2……bn -r扩充为F nq的一组基b 1, b 2……bn -r，bn -r +1……bn ，令M =[b 1, b 2……bn]，显然M 可逆，对给定的线性网络编码做线性变换M -1就可得到安全的网络编码。

    (5)情形2
    对于一种重要的特殊情形，?撰包含E中的所有r 子集，(r <n，n =mintmaxflow(t))，则构造安全网络编码的充分条件也是必要的。因为对于接收节点t，若网络中有r 条信道被搭线窃听，从信源s到t 的安全路径数目仍然至少是n -r，故n -r 个符号可以安全地传输，且此情形下，构造算法就信息量最大使用的密钥最小而言是最优的。

    上面的密钥(或随机信号)都是在信源节点上产生，实际上是将密钥(或随机信号)也当作要传输的信息，对之进行编码。这个思想在文献[11]中继续进行了研究，Feldman等在文献[11]中，在文献[8]的基础上证明了将线性网络编码变为安全的网络编码等价于找到满足一定广义距离性质的线性码，并证明了如果放弃少量的整体容量，就可以在较小的基域上构造出安全的网络编码。而在文献[12]中，蔡宁和杨伟豪又推广到一种更一般的模型，即密钥(或随机信号)可以在节点集合V 的任何一个子集U 中产生，进而，他们得到了一个多源线性安全网络编码的充要条件。这儿，他们假设是在一个无圈的通信网络上进行的。

3 其他安全网络编码模型
    K Jain等在文献[13]中得到了单源网络中(可以有环)以单位速率安全单播的充要条件。在假定窃听者具有有限计算能力的情形下，利用哈希函数和网络编码相结合的方法，使得网络可以以更高的速率安全传输数据，而搭线窃听者得不到信源的任何有用信息。其本质上要求信源和信宿之间至少有一条安全信道，从而通过拓展此安全信道来构造安全网络编码。K Bhattad等在文献[14]中针对无圈网络多播问题，提出了窃听者不能得到任何有意义信息的弱安全网络编码模型。其体系较简单，虽不是信息论意义上的信息安全，但有广泛的适用范围(它与文献[4]中一般的信息论意义下的安全性的差别在于：前者是指窃听者不能得到有关一个信源发出的任何部分消息，而后者的安全指的是不能得到由任何信源发出的所有消息，其本质的差别就在于整体相互独立强于部分相互独立)。Chan等在文献[15]中讨论了多源网络的安全通信问题，在一定的窃听范围的限制下，利用随机网络编码的方法，给出了多源安全网络编码容量的内界、外界和线性规划界。这些界是Yeung得到的界的推广。

4 参考文献
[1] YEUNG R W, ZHANG Z. Distributed source coding for satellite communications[J]. IEEE Transactions on Information Theory, 1999,45(4):1111-1120.
[2] AHLSWEDE R, CAI N, LI S Y R, et al. Network information flow[J]. IEEE Transactions on Information Theory, 2000,46(4): 1204-1216.
[3] LI S Y R, YEUNG R W, CAI N. Linear network coding[J]. IEEE Transactions on Information Theory, 2003,49(2): 371-381.
[4] KOETTER R, MEDARD M. An algebraic approach to network coding[J]. IEEE/ACM Transactions on Network,2003, 11(5):782-795.
[5] JAGGI S, SANDRS P, CHOU P A, et al. Polynomial time algorithms for multicast network code construction[J]. IEEE Transactions on Information Theory, 2005, 51(6):1973-1982.
[6] HO T, KOETTER R, MEDARD M, et al. The benefits of coding over routing in a randomized setting[C]//2003 IEEE International Symposium on Information Theory(ISIT’03), Jun 29-Jul 4, 2003,Yokohama, Japan.2003: 442-445.
[7] CAI N, YEUNG R W. Network coding and error correction[C]//Proceedings of IEEE Information Theory Workshop (ITW’02), Oct 20-25,2002, Bangalore, India. 2002:119-122.
[8] CAI N, YEUNG R W. Secure network coding[C]//Proceedings of 2002 IEEE International Symposium on Information Theory (ISIT 2002), Jun 30-Jul 5, 2002, Lausanne, Switzerland. Los Alamitis, CA,USA: IEEE Computer Society, 2002: 323.
[9] CASTRO M, LISKOV B. Practical byzantine fault tolerance[C]//Proceedings of. 3rd USENIX Symposium on Operating Systems Design and Implementation (OSDI’99), Feb 22-25, 1999, New Orleans, LA, SA.
[10] KIHLSTROM K P, MOSER L E, MELLIAR-SMITH P M. The secure ring protocols for securing group communication[C]//Proceedings of the 31st Annual Hawaii International Conference on System Sciences (HICSS’98): Vol. 3, IEEE Computer Society Press, 1998:317-326.
[11] FELDMAN J, MALKIN T, STEIN C, et al. On the capacity of secure network coding[C]//Proceedings of 42nd Annual Allerton Conference on Communication, Control and Computing, Sep 29-Oct 1, 2004, Monticello, IL,USA 2004.
[12] CAI N, YEUNG R W. A security condition for multi-source linear network coding[C]//Proceedings of 2007 IEEE International Symposium on Information Theory (ISIT 2007), Jul 24-29, 2007, Nice, France. Los Alamitis, CA,USA: IEEE Computer Society, 2007: 561-565.
[13] JAIN K. Security based on network topology against the wiretapping attack[J]. IEEE Wireless Communications, 004,11(1):68-71.
[14] BHATTAD K, NARAYANAN K R. Weakly secure network coding[C]//Proceedings of First Workshop on Network Coding, Theory, and Applications(NETCOD’05). Apr 2005, Riva del Garda, Italy. 2005.
[15] CHAN T, GTANT A. Capacity bounds for secure network coding[C]//Proceedings of Australian Communications Theory Workshop(AusCTW 2008), Jan 30-Feb 1, 2008, Christchurch, New. Zealand. Piscataway, NJ,USA:IEEE,2008: 95-100.

收稿日期：2008-11-05

[摘要] 网络编码的思想得到了广泛的关注，网络编码的各种应用问题相继提出，其中网络编码中的安全是网络编码的重要应用领域。安全网络编码大体上分为两方面，反篡改数据和反窃听数据。反篡改数据也就是网络纠错，反窃听数据就是防搭线窃听的安全网络编码。文章论述了防窃听的安全网络编码的模型、理论、构造、发展，对抗搭线窃听的安全网络编码进行了重点分析。

[关键词] 安全网络编码；窃听；容量

[Abstract] Network coding is a breakthrough in the field of communication. As soon as the concept of network coding appeared, it attracted great attention, and its applications were researched one after the other, the Secure Network Coding also appeared and was made a research topic. Now, Secure Network Coding has two models: network error correction problem on network coding, against the wiretapping attack on network coding. The former model is an extending of classical error correction theory, and it is widely researched in many papers. In this paper, the model, the theorem, the construction, and the development of Secure Network Coding against the wiretapping attack will be introduced.

[Keywords] secure network coding; eavesdrop; capacity