防竊聽(tīng)的安全網(wǎng)絡(luò)編碼

1、防竊聽(tīng)的安全網(wǎng)絡(luò)編碼網(wǎng)絡(luò)編碼的思想在1999年，由RWYeung和ZZhang在文獻(xiàn)1中明確提出，其主要思想是改變傳統(tǒng)網(wǎng)絡(luò)中節(jié)點(diǎn)對(duì)收到的信息只能進(jìn)行單一的存儲(chǔ)-轉(zhuǎn)發(fā)的路由功能，使之能夠?qū)κ盏降膩?lái)自不同鏈路的信息進(jìn)行處理（編碼），使其既能實(shí)現(xiàn)傳統(tǒng)路由的存儲(chǔ)-轉(zhuǎn)發(fā)功能，又能實(shí)現(xiàn)對(duì)信息的處理，從而提高傳輸信息量，最后仍然使目的節(jié)點(diǎn)成功接收到所需信息。而2003年，RudolfAhlswede、蔡寧、李碩彥和楊偉豪等在文獻(xiàn)2中對(duì)網(wǎng)絡(luò)編碼的理論意義和應(yīng)用價(jià)值進(jìn)行了影響深遠(yuǎn)的論述，通過(guò)基于網(wǎng)絡(luò)信息流的概念，證明了用網(wǎng)絡(luò)編碼的方法，能夠使網(wǎng)絡(luò)的傳輸容量達(dá)到網(wǎng)絡(luò)多播的最大流限，即證明了多播容量等于從信源到信宿

2、節(jié)點(diǎn)的最大流的最小值。突破了傳統(tǒng)路由傳輸?shù)摹捌款i”問(wèn)題。網(wǎng)絡(luò)編碼概念的提出是通信領(lǐng)域的一項(xiàng)重大突破1-2，它融合了路由和傳統(tǒng)編碼，以一定的編碼能力換取了傳輸?shù)娜萘浚沟镁W(wǎng)絡(luò)的傳輸容量得到突破，達(dá)到了理論上的最大傳輸容量的上限。自網(wǎng)絡(luò)編碼的概念提出后，李碩彥、楊偉豪和蔡寧在文獻(xiàn)3中證明了通過(guò)線性網(wǎng)絡(luò)編碼就可以達(dá)到網(wǎng)絡(luò)多播的最大流限，而線性方法的編碼和解碼都相對(duì)簡(jiǎn)單，所以這就為網(wǎng)絡(luò)編碼的思想“以節(jié)點(diǎn)的計(jì)算能力來(lái)?yè)Q取網(wǎng)絡(luò)的信息傳輸容量”奠定了基礎(chǔ)，而且文獻(xiàn)3為網(wǎng)絡(luò)編碼的應(yīng)用奠定了堅(jiān)實(shí)的基礎(chǔ)；RKoetterandMMedard在文獻(xiàn)4中提出了網(wǎng)絡(luò)編碼的代數(shù)框架，并證明了存在滿(mǎn)足多播容量的線性時(shí)不變編

3、碼；SJaggi等在文獻(xiàn)5中給出了構(gòu)造線性網(wǎng)絡(luò)多播的多項(xiàng)式時(shí)間算法；THo、RKoetter、MMedard、DRKargerandMEros在文獻(xiàn)6中提出了隨機(jī)網(wǎng)絡(luò)編碼，并證明了通過(guò)隨機(jī)線性網(wǎng)絡(luò)編碼，能以極大概率達(dá)到網(wǎng)絡(luò)多播的最大流限，隨機(jī)網(wǎng)絡(luò)編碼的提出拓寬了網(wǎng)絡(luò)編碼的適用范圍，使得網(wǎng)絡(luò)編碼不再局限于確定的網(wǎng)絡(luò)拓?fù)浜图惺降乃惴?。近幾年，研究者們已將上面的結(jié)果拓寬到多個(gè)應(yīng)用領(lǐng)域，其中，蔡寧和楊偉豪在文獻(xiàn)7中利用分布式網(wǎng)絡(luò)編碼來(lái)糾正整個(gè)網(wǎng)絡(luò)中的差錯(cuò)，并在文獻(xiàn)8中論述了網(wǎng)絡(luò)編碼在安全方面的應(yīng)用，為網(wǎng)絡(luò)編碼增加了新的應(yīng)用領(lǐng)域。如果網(wǎng)絡(luò)中所有節(jié)點(diǎn)對(duì)其輸入信息進(jìn)行線性編碼，則稱(chēng)為線性網(wǎng)絡(luò)編碼，否則稱(chēng)為

4、非線性網(wǎng)絡(luò)編碼；如果網(wǎng)絡(luò)節(jié)點(diǎn)對(duì)信息進(jìn)行編碼的系數(shù)（局部編碼核和全局編碼核）是根據(jù)網(wǎng)絡(luò)拓?fù)涞奶攸c(diǎn)事先給定的，則稱(chēng)為確定性網(wǎng)絡(luò)編碼。而隨機(jī)網(wǎng)絡(luò)編碼則沒(méi)有事先給定全局編碼核，而是讓網(wǎng)絡(luò)中的中間節(jié)點(diǎn)隨機(jī)選取局部編碼核對(duì)信息進(jìn)行編碼，由此局部編碼核計(jì)算出相應(yīng)的全局編碼核，然后把此全局編碼核作為報(bào)頭的一部分發(fā)送給收點(diǎn)，以此解出原始信息。1所示的蝶型網(wǎng)絡(luò)是通過(guò)網(wǎng)絡(luò)編碼實(shí)現(xiàn)多播最大容量的經(jīng)典例子。1 安全網(wǎng)絡(luò)編碼隨著網(wǎng)絡(luò)通信越來(lái)越廣泛，對(duì)信息安全傳輸?shù)囊笤絹?lái)越迫切，也越來(lái)越高。網(wǎng)絡(luò)編碼作為一種特殊的信息傳輸方式，它在很多方面可以達(dá)到一定的安全要求。網(wǎng)絡(luò)通信中，按照攻擊者的攻擊方式，攻擊主要分為以下兩種：搭線

5、竊聽(tīng)（被動(dòng)攻擊）和Byzantine攻擊（主動(dòng)攻擊）。密碼技術(shù)是信息安全的核心技術(shù)，在網(wǎng)絡(luò)編碼出現(xiàn)以前，主要利用密碼學(xué)領(lǐng)域中的諸如數(shù)據(jù)加密，哈希函數(shù)和消息認(rèn)證等方式來(lái)確保數(shù)據(jù)的安全傳輸，如文獻(xiàn)9-10中所述等。然而傳統(tǒng)的密碼學(xué)方法存在一定的局限性，如計(jì)算復(fù)雜度較大，數(shù)據(jù)傳輸速率較低，消息冗余較大等，因此需要尋找一些安全、高效的數(shù)據(jù)傳輸方式。雖然網(wǎng)絡(luò)編碼的初衷在于提高網(wǎng)絡(luò)的吞吐量，然而隨著進(jìn)一步研究發(fā)現(xiàn)它也是一種構(gòu)造安全網(wǎng)絡(luò)傳輸?shù)暮梅绞?。下面將介紹網(wǎng)絡(luò)編碼在數(shù)據(jù)安全傳輸中的應(yīng)用。網(wǎng)絡(luò)編碼在安全中的應(yīng)用主要包括兩方面：抗搭線竊聽(tīng)和抗Byzantine攻擊。本文主要關(guān)注抗搭線竊聽(tīng)的安全網(wǎng)絡(luò)編碼。2

6、抗搭線竊聽(tīng)的安全網(wǎng)絡(luò)編碼多播是通信中應(yīng)用較廣的一種情形，蔡寧和楊偉豪首先在文獻(xiàn)8中論述了網(wǎng)絡(luò)編碼在安全方面的應(yīng)用，最先研究了單源無(wú)圈網(wǎng)絡(luò)中數(shù)據(jù)的安全多播問(wèn)題，給出了搭線竊聽(tīng)的網(wǎng)絡(luò)通信模型。并且構(gòu)造了竊聽(tīng)者無(wú)論竊聽(tīng)給定的竊聽(tīng)集集合中的哪個(gè)竊聽(tīng)集都無(wú)法恢復(fù)出原始信息，在信息論意義下安全的網(wǎng)絡(luò)編碼。2.1 搭線竊聽(tīng)網(wǎng)絡(luò)的通信模型網(wǎng)絡(luò)模型：通信網(wǎng)絡(luò)抽象為一個(gè)有限有向圖G=(V,E)，其中V表示節(jié)點(diǎn)集，E是通信鏈接的集合。有向圖模型對(duì)有線網(wǎng)絡(luò)和無(wú)線網(wǎng)絡(luò)都適用。對(duì)于有線網(wǎng)絡(luò)，有向邊是簡(jiǎn)單的端對(duì)端的鏈接；對(duì)于無(wú)線網(wǎng)絡(luò)，有向邊由即時(shí)的信道實(shí)現(xiàn)(數(shù)據(jù)包可能由于衰退和碰撞而丟失)決定，連接著發(fā)送節(jié)點(diǎn)(信源)、中間

7、節(jié)點(diǎn)和接收節(jié)點(diǎn)(信宿)。搭線竊聽(tīng)網(wǎng)絡(luò)(CSWN的模型包含5個(gè)組成部分：(1) 有限有向無(wú)圈圖G=(V,E)，其中V是節(jié)點(diǎn)集，E是邊集，兩節(jié)點(diǎn)間可以有多條有向邊。(2) 信源節(jié)點(diǎn)集S：每個(gè)信源節(jié)點(diǎn)s以一定的速率隨機(jī)生成取值于字母表M的隨機(jī)信息ms。(3)借宿節(jié)點(diǎn)集T:每個(gè)信宿節(jié)點(diǎn)t是可以無(wú)差錯(cuò)地恢復(fù)出某些信源發(fā)出的隨機(jī)信息ms的合法用戶(hù)。(4) 搭線竊聽(tīng)集的集合?撰，?撰為邊集E的子集的集合；?撰中每個(gè)元素稱(chēng)為搭線竊聽(tīng)集合，每個(gè)搭線竊聽(tīng)的集合中的邊可以被竊聽(tīng)者竊取到所傳輸?shù)乃行畔?，但是竊聽(tīng)者所能竊聽(tīng)的所有邊不能同時(shí)在多于一個(gè)竊聽(tīng)集合中。(5)邊的容量R=R(a,b):(a,b)GE,R(a,b

8、)表示(a,b)邊上可傳輸?shù)淖畲笃骄俾?。五元組(G、S、T?撰、R)為一個(gè)搭線竊聽(tīng)網(wǎng)絡(luò)(CSWN)對(duì)于一個(gè)CSWN通信者知道竊聽(tīng)者的竊聽(tīng)集合？撰，但不知道？撰中的哪一個(gè)元素是搭線竊聽(tīng)集合。通信者的目的是以盡可能大的速率將信息從信源節(jié)點(diǎn)集S傳輸?shù)叫潘薰?jié)點(diǎn)集T，而且使得竊聽(tīng)者從搭線竊聽(tīng)集？撰中得不到任何信息ms,sGS。在一個(gè)CSWN中，我們一般還假設(shè)竊聽(tīng)者知道通信者的編碼策略，而且還可以盡可能地根據(jù)自己的知識(shí)和經(jīng)驗(yàn)來(lái)選擇搭線竊聽(tīng)集。要想達(dá)到上面的安全傳輸信息的目的，一般而言，通信者必須將要傳輸?shù)男畔s隨機(jī)化。令W為獨(dú)立隨機(jī)變量集，其中的隨機(jī)變量在指標(biāo)集w中一致分布。圖2從信源發(fā)出的信息中，m

9、是消息本身，而k是為了達(dá)到安全的隨機(jī)數(shù)。圖中紅線是竊聽(tīng)集，但是一個(gè)時(shí)間內(nèi)只允許敵手竊聽(tīng)其中的一條，這樣接收節(jié)點(diǎn)T和T能夠安全接收到信源傳來(lái)的消息m。2.2 抗搭線竊聽(tīng)的安全網(wǎng)絡(luò)編碼CSWN(GS、T、R)的碼(a,b):(a,b)GE稱(chēng)為可容許碼，容量條件對(duì)于所有的(a,b)GE,n-1log|(a,b)|max|?撰|,|T|,存在域Fq上G的可容許碼。(4) 情形1根據(jù)安全網(wǎng)絡(luò)編碼的構(gòu)造思想，若已經(jīng)存在多播n個(gè)符號(hào)(m,k)(其中|m|=n-r,|k|二r)的線性網(wǎng)絡(luò)編碼，？全AG?撰，令fA=feGA,若對(duì)所有的AG?撰，都有dim(span(fA)Wr,則當(dāng)基域Fq充分大時(shí)，可以找到b

10、1,b2bn-rFnq,使得對(duì)所有的AG?撰，b1,b2bn-r和fA的極大線性無(wú)關(guān)組都是線性獨(dú)立的。將b1,b2bn-r擴(kuò)充為Fnq的一組基b1,b2bn-r,bn-r+1bn,令M=b1,b2bn,顯然M可逆，對(duì)給定的線性網(wǎng)絡(luò)編碼做線性變換M-1就可得到安全的網(wǎng)絡(luò)編碼。(5) 情形2對(duì)于一種重要的特殊情形，?撰包含E中的所有r子集，(r8 CAIN,YEUNGRW.SecurenetworkcodingC/Proceedingsof2002IEEEInternationalSymposiumonInformationTheory(ISIT2002),Jun30-Jul5,2002,Laus

11、anne,Switzerland.LosAlamitis,CA,USA:IEEEComputerSociety,2002:323.9 CASTROM,LISKOVB.PracticalbyzantinefaulttoleranceC/Proceedingsof.3rdUSENIXSymposiumonOperatingSystemsDesignandImplementation(OSDI99),Feb22-25,1999,NewOrleans,LA,SA.10 KIHLSTROMKP,MOSERLE,MELLIAR-SMITHPM.Thesecureringprotocolsforsecuri

12、nggroupcommunicationC/Proceedingsofthe31stAnnualHawaiiInternationalConferenceonSystemSciences(HICSS98):Vol.3,IEEEComputerSocietyPress,1998:317-326.11 FELDMANJ,MALKINT,STEINC,etal.OnthecapacityofsecurenetworkcodingC/Proceedingsof42ndAnnualAllertonConferenceonCommunication,ControlandComputing,Sep29-Oc

13、t1,2004,Monticello,IL,USA2004.12 CAIN,YEUNGRW.Asecurityconditionformulti-sourcelinearnetworkcodingC/Proceedingsof2007IEEEInternationalSymposiumonInformationTheory(ISIT2007),Jul24-29,2007,Nice,France.LosAlamitis,CA,USA:IEEEComputerSociety,2007:561-565.13 JAINK.Securitybasedonnetworktopologyagainstthe

14、wiretappingattackJ.IEEEWirelessCommunications,004,11(1):68-71.14 BHATTADK,NARAYANANKR.WeaklysecurenetworkcodingC/ProceedingsofFirstWorkshoponNetworkCoding,Theory,andApplications(NETCOD05).Apr2005,RivadelGarda,Italy.2005.15 CHANT,GTANTA.CapacityboundsforsecurenetworkcodingC/ProceedingsofAustralianCommunicationsTheoryWorkshop(AusCTW