米 波，周小艷，黃大榮

(重慶交通大學(xué) 信息科學(xué)與工程學(xué)院，重慶 400074)

基于不經(jīng)意傳輸?shù)耐負(fù)潆[藏廣播協(xié)議設(shè)計(jì)*

米 波，周小艷*，黃大榮

(重慶交通大學(xué) 信息科學(xué)與工程學(xué)院，重慶 400074)

為了保護(hù)消息廣播中節(jié)點(diǎn)關(guān)系、地理位置等敏感信息，將高效的NTRU(Number Theory Research Unit)公鑰加密算法與不經(jīng)意傳輸協(xié)議相結(jié)合，通過(guò)引入不可信的第三方以保證廣播的中間過(guò)程無(wú)法被任意節(jié)點(diǎn)所獲知，從而實(shí)現(xiàn)了隱藏網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的目標(biāo)。該協(xié)議可認(rèn)為是拓?fù)潆[藏廣播的具體實(shí)現(xiàn)，解決了現(xiàn)有概念性方案中尚未涉及的秘鑰重構(gòu)、相鄰節(jié)點(diǎn)身份隱藏及網(wǎng)絡(luò)動(dòng)態(tài)變化等問(wèn)題。安全性分析表明，在半誠(chéng)實(shí)攻擊模型下該方案能夠保證網(wǎng)絡(luò)中任何一部分節(jié)點(diǎn)被攻破均不會(huì)導(dǎo)致其他節(jié)點(diǎn)拓?fù)湫畔⑿孤?。此外，通過(guò)與相關(guān)概念性協(xié)議進(jìn)行實(shí)驗(yàn)對(duì)比分析，該方案除安全性外還可充分體現(xiàn)計(jì)算、通信開(kāi)銷與節(jié)點(diǎn)平均度數(shù)無(wú)關(guān)的優(yōu)勢(shì)。

多方安全計(jì)算；拓?fù)潆[藏；NTRU；不經(jīng)意傳輸；廣播協(xié)議設(shè)計(jì)

1 引 言

多方安全計(jì)算(Secure Multi-party Computation，SMC)自30多年前由圖靈獎(jiǎng)獲得者A.C.Yao首次提出[1]之后，無(wú)論是在理論研究[2-3]還是在實(shí)際應(yīng)用[4-6]等各方面均取得了很大的進(jìn)展。正如Goldwasser所預(yù)測(cè)的，多方計(jì)算的今天就像是10年前的公鑰密碼學(xué)一樣[7]，它在協(xié)作計(jì)算中所擁有的輸入隱藏能力使其成為現(xiàn)實(shí)應(yīng)用中一個(gè)強(qiáng)大的工具。多方安全計(jì)算通常是在計(jì)算機(jī)網(wǎng)絡(luò)上進(jìn)行的，但一個(gè)重要的問(wèn)題卻往往被忽略：多方安全計(jì)算協(xié)議所運(yùn)行的底層網(wǎng)絡(luò)通信結(jié)構(gòu)本身可能就是敏感信息。以社交網(wǎng)絡(luò)和車載網(wǎng)絡(luò)為例，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的暴露可能會(huì)嚴(yán)重危害節(jié)點(diǎn)間關(guān)系或位置信息等重要隱私。

目前，鮮有多方安全計(jì)算文獻(xiàn)將多方計(jì)算和網(wǎng)絡(luò)結(jié)構(gòu)之間的關(guān)系予以考慮。筆者所能找到的用于解決多方安全計(jì)算中拓?fù)潆[私保護(hù)問(wèn)題的唯一文獻(xiàn)，來(lái)自于Tal Moran于2015年初發(fā)表的開(kāi)創(chuàng)性論文[8]。他分別采用基于不可分辨性博弈和基于仿真的方法正式定義了拓?fù)潆[藏多方安全計(jì)算的概念，同時(shí)也從理論上提出了一種用于拓?fù)潆[私保護(hù)的安全廣播協(xié)議。該協(xié)議中只要攻擊者未能攻破任一節(jié)點(diǎn)的整個(gè)鄰域，那么它就是安全的。然而，Tal Moran只是假設(shè)了存在一種秘密共享方案可以用來(lái)在相鄰節(jié)點(diǎn)中將敏感信息進(jìn)行隱藏，卻沒(méi)有真正實(shí)現(xiàn)它。此外，我們僅在Hinkelmann和Jakoby的文獻(xiàn)[9]中發(fā)現(xiàn)涉及拓?fù)潆[藏多方安全計(jì)算的相關(guān)描述，其重點(diǎn)在于信息理論研究。他們觀察到，網(wǎng)絡(luò)中任意兩個(gè)不相鄰的節(jié)點(diǎn)vi和vj能夠進(jìn)行通信的前提條件是必須存在某些中間節(jié)點(diǎn)vz知道自己位于它們之間。這表明，基于信息理論，任何多方安全計(jì)算協(xié)議都不可避免地會(huì)將部分拓?fù)湫畔⑿孤┙o攻擊者。但幸運(yùn)的是，他們也得到了一個(gè)積極的結(jié)果：在多方安全計(jì)算協(xié)議的構(gòu)造過(guò)程中，理論上可避免泄露鄰域外的其他信息[9]。受Tal Moran拓?fù)潆[藏廣播協(xié)議的啟發(fā)，我們利用改良NTRU(Number Theory Research Unit)加密算法的半同態(tài)特性設(shè)計(jì)了一種高效的拓?fù)潆[藏廣播方案。NTRU[10]是一個(gè)相對(duì)較新的公鑰加密系統(tǒng)，由布朗大學(xué)3位數(shù)學(xué)教授Jeffrey Hoffstein,J.Pipher和 J.H.Silverman 于1996年所設(shè)計(jì)。仍不斷有改進(jìn)算法被提出，并通過(guò)引入新的參數(shù)等方法來(lái)抵御目前已知攻擊，并提高其計(jì)算能力[11-13]。由于NTRU算法的加密和解密過(guò)程只使用簡(jiǎn)單的多項(xiàng)式乘法，具有密鑰生成簡(jiǎn)單、加解密速度快等特點(diǎn)，使其在移動(dòng)設(shè)備或智能卡等資源受限的環(huán)境中更具競(jìng)爭(zhēng)力。此外，其半同態(tài)特性能夠保證，因此我們將其作為基本構(gòu)建模塊用于不經(jīng)意傳輸協(xié)議設(shè)計(jì)，并引入不可信的第三方以確保消息廣播的中間結(jié)果不為任何節(jié)點(diǎn)所獲知，從而實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的隱藏。

2 Tal Moran協(xié)議

Tal Moran在文獻(xiàn)[8]中首次就半誠(chéng)實(shí)模型下拓?fù)潆[私保護(hù)的安全性問(wèn)題給出了明確定義。簡(jiǎn)單而言，如果我們用一個(gè)非完全圖G=(V,E)來(lái)描述網(wǎng)絡(luò)，則基于不可分辨性博弈的定義可概括如下：

設(shè)A?V為攻擊者已攻破的節(jié)點(diǎn)子集，G0、G1分別為基于原節(jié)點(diǎn)集合V所構(gòu)造的兩個(gè)異構(gòu)網(wǎng)絡(luò)拓?fù)洌瑵M足子節(jié)點(diǎn)集合A所構(gòu)成的子圖相同，隨后發(fā)送給挑戰(zhàn)者。挑戰(zhàn)者隨機(jī)選擇Gb并在協(xié)議執(zhí)行后返回集合A中各節(jié)點(diǎn)的詳細(xì)執(zhí)行過(guò)程(包括所收發(fā)及處理的數(shù)據(jù))。攻擊者分析這些過(guò)程并試圖還原挑戰(zhàn)者的選擇Gb。如果計(jì)算能力有限的攻擊者在上述博弈中的取勝的概率只比簡(jiǎn)單地猜測(cè)b值稍大，則稱該協(xié)議對(duì)于選擇性拓?fù)涔羰前踩腫8]。

為保證消息廣播能滿足上述拓?fù)潆[私安全性定義，Tal Moran在理論上提出一種基于秘鑰共享的安全廣播方案。其基本思想在于利用多方安全計(jì)算的方法保證協(xié)議在執(zhí)行過(guò)程中不會(huì)將消息的內(nèi)容暴露給任一中間節(jié)點(diǎn)。具體而言，每一輪中節(jié)點(diǎn)將來(lái)自鄰域的廣播和當(dāng)前自身消息做或運(yùn)算，并將其作為下一輪的消息廣播至相鄰節(jié)點(diǎn)，當(dāng)輪數(shù)達(dá)到一定要求，源節(jié)點(diǎn)消息則可被所有節(jié)點(diǎn)獲知。值得注意的是，在消息到達(dá)某一節(jié)點(diǎn)后，其或運(yùn)算的結(jié)果才會(huì)轉(zhuǎn)為非0，從而它能夠據(jù)此推斷出源節(jié)點(diǎn)大致的拓?fù)湮恢?詳見(jiàn)第4節(jié))。為保證中間結(jié)果不被任何節(jié)點(diǎn)獲知，Tal Moran假定所有節(jié)點(diǎn)均擁有一個(gè)公私鑰對(duì)，且私鑰作為共享秘密分布在其相鄰節(jié)點(diǎn)當(dāng)中，所有消息的發(fā)送均以密文的形式進(jìn)行，而或運(yùn)算只能通過(guò)某種多方安全計(jì)算方案恢復(fù)出私鑰才能完成，并且計(jì)算結(jié)果(除最后一輪)也是以密文的形式存儲(chǔ)在其持有節(jié)點(diǎn)當(dāng)中的。

盡管可證明Tal Moran協(xié)議能保證任一節(jié)點(diǎn)的整個(gè)鄰域未被攻破時(shí)的拓?fù)浔Ｃ苄?，但它未考慮任意節(jié)點(diǎn)子集被攻破時(shí)的情況。同時(shí)，該協(xié)議只在較高層面上進(jìn)行了概念設(shè)計(jì)，并未涉及具體算法實(shí)現(xiàn)，其中多方安全計(jì)算怎樣進(jìn)行，如何確?；謴?fù)出的私鑰不被泄露等問(wèn)題均未考慮。通過(guò)第6節(jié)的對(duì)比實(shí)驗(yàn)也將看到，該協(xié)議的計(jì)算、通信負(fù)荷嚴(yán)重依賴于節(jié)點(diǎn)的平均度數(shù)，存在較大的性能缺陷。若需對(duì)Tal Moran協(xié)議細(xì)節(jié)進(jìn)一步了解，我們建議讀者就文獻(xiàn)[8] 深入閱讀。

3 NTRU密碼算法及其半同態(tài)性質(zhì)

我們發(fā)現(xiàn)NTRU密碼算法在一定條件下滿足半同態(tài)性質(zhì)，并基于該特性來(lái)完成協(xié)議中不經(jīng)意傳輸方案的設(shè)計(jì)。NTRU運(yùn)行在一個(gè)截?cái)喽囗?xiàng)式環(huán)R=Z[X]/(XN-1)之上，其安全性依賴于格中的最短向量問(wèn)題，所有多項(xiàng)式系數(shù)均為整數(shù)，且次數(shù)不超過(guò)N-1[10]：

a=a0+a1X1+a2X2+…+aN-2XN-2+aN-1XN-1。

(1)

NTRU密碼系統(tǒng)由3個(gè)整數(shù)參數(shù)(N,p,q)所指定。為秘密發(fā)送消息，發(fā)送方須事先生成兩個(gè)關(guān)鍵多項(xiàng)式f和g，同時(shí)要求f在模p和模q之下均存在逆元，分別表示為fp和fq，并計(jì)算h=pfqg作為公鑰發(fā)布。

為加密消息m，我們可將其視為一個(gè)位串或三進(jìn)制串，并將其表示為截?cái)喹h(huán)上系數(shù)取{-1,0,1}的多項(xiàng)式，然后隨機(jī)選擇多項(xiàng)式r，使用公鑰h對(duì)其進(jìn)行加密運(yùn)算得到密文：

c=r·h+m(modq)。

(2)

就解密過(guò)程而言，接收方可先將密文消息c與自己的私鑰f相乘，得到

a=f·c(modq)=p·r·g+f·m，

(3)

并將其系數(shù)平移到[-q/2,q/2]區(qū)間內(nèi)。由于

p·r·g(modp)=0，所以，接收者便能夠以如下方式計(jì)算并解密秘密信息:

m=fp·a(modp)。

(4)

我們注意到只要選取足夠大的模數(shù)p并將消息m所對(duì)應(yīng)的多項(xiàng)式系數(shù)限定在[-p/2,p/2]區(qū)間之內(nèi)(原始算法為取自集合{-1,0,1})，仍然可以準(zhǔn)確恢復(fù)出密文。因此，我們利用這種性質(zhì)設(shè)計(jì)了如下可作為協(xié)議基本構(gòu)件的半同態(tài)加密方案。

具體而言，我們首先將兩個(gè)待加密的明文以多項(xiàng)式m1、m2的系數(shù)形式分別表示為(a1,1,a1,2,…a1,N-2,a1,N-1)和(a2,1,a2,2,…a2,N-2,a2,N-1)，滿足a1,i+a2,i∈[-p/2,p/2]，0≤i≤N-1，則對(duì)應(yīng)密文的和可記作

c1+c2=p·(r1+r2)·fq·g+m1+m2(modq);

(5)

然后我們按照上述過(guò)程解密獲得明文m1+m2，其系數(shù)為(a1,1+a2,1,a1,2+a2,2,…a1,N-2+a2,N-2,a1,N-1+a2,N-1)，而密文半同態(tài)相加的結(jié)果(m1、m2按位異或)為(a1,1+a2,1,a1,2+a2,2,…a1,N-2+a2,N-2,a1,N-1+a2,N-1)即密文半同態(tài)相加的結(jié)果與明文按位加的結(jié)果相同。

4 系統(tǒng)模型與拓?fù)浔┞秵?wèn)題

我們將網(wǎng)絡(luò)表示為一個(gè)無(wú)向連通圖G=(V,E)。對(duì)任一節(jié)點(diǎn)vi∈V，其封閉鄰域定義為N(vi)={vj∈V,(vi,vj)∈E}∪{vi}。在攻擊模型中，我們考慮計(jì)算能力有限的靜態(tài)攻擊者，并假設(shè)它已經(jīng)侵入部分網(wǎng)絡(luò)節(jié)點(diǎn)。攻擊者行為遵循半誠(chéng)實(shí)模型，即它會(huì)嚴(yán)格遵循協(xié)議規(guī)則，但又期望通過(guò)分析數(shù)據(jù)來(lái)獲取未攻破節(jié)點(diǎn)的隱私信息，當(dāng)然它也能看到誠(chéng)實(shí)參與方在每一輪所收發(fā)的所有信息。

某一節(jié)點(diǎn)為向整個(gè)網(wǎng)絡(luò)廣播數(shù)據(jù)m，可先將消息表示為一個(gè)二進(jìn)制位串，并通過(guò)執(zhí)行下面給出的簡(jiǎn)單廣播協(xié)議來(lái)完成：

(1)在第一輪中，發(fā)送者將二進(jìn)制消息m廣播給所有相鄰節(jié)點(diǎn)，而其他節(jié)點(diǎn)則向其相鄰節(jié)點(diǎn)廣播0串。需注意的是所有這些二進(jìn)制串長(zhǎng)度均相等。

(2)對(duì)于隨后的每一輪，每個(gè)參與者都先將其收到的所有消息按位或，再通過(guò)廣播的方式將結(jié)果發(fā)送至相鄰節(jié)點(diǎn)。

顯然，k輪后凡是距離發(fā)送者k跳或更少的跳數(shù)的節(jié)點(diǎn)都將收到消息m，且在diam(G)輪后消息必然能夠到達(dá)網(wǎng)絡(luò)中任何一個(gè)節(jié)點(diǎn)，其中diam(G)表示網(wǎng)絡(luò)的最長(zhǎng)路徑。

然而，盡管這個(gè)簡(jiǎn)單協(xié)議實(shí)現(xiàn)了廣播的功能，但會(huì)導(dǎo)致網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)暴露：每個(gè)節(jié)點(diǎn)都可以利用自身收到非零位串時(shí)的輪數(shù)計(jì)算出它與發(fā)送者之間的距離，而通過(guò)關(guān)注首個(gè)非零消息來(lái)自哪個(gè)相鄰節(jié)點(diǎn)它甚至可以推導(dǎo)出發(fā)送者的方向。為了解決拓?fù)浔┞秵?wèn)題，我們引入了一個(gè)半誠(chéng)實(shí)的服務(wù)器來(lái)幫助相鄰節(jié)點(diǎn)秘密計(jì)算每一輪廣播消息的或值，以使得中間結(jié)果得以隱藏，而且在我們的方案中網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)對(duì)服務(wù)器而言也是保密的。

5 拓?fù)潆[藏廣播協(xié)議設(shè)計(jì)

在這一節(jié)中，我們針對(duì)半誠(chéng)實(shí)攻擊模型設(shè)計(jì)了一種拓?fù)潆[藏廣播協(xié)議。該協(xié)議的3個(gè)指標(biāo)分別為：(1)即使攻擊者攻破了網(wǎng)絡(luò)中的任何一部分節(jié)點(diǎn)，其余節(jié)點(diǎn)的拓?fù)湫畔⒍疾粫?huì)被泄露；(2)即使引入了半誠(chéng)實(shí)的第三方，他也不能從收到的信息中分析出任何網(wǎng)絡(luò)拓?fù)湫畔ⅲ?3)即使廣播過(guò)程具有不經(jīng)意傳輸?shù)奶攸c(diǎn)，但在協(xié)議結(jié)束時(shí)所有節(jié)點(diǎn)都將正確恢復(fù)出廣播消息。具體而言，我們的協(xié)議分為如下三個(gè)步驟：

Step 1 初始化階段

Step 2 廣播階段

這一階段可視為上述簡(jiǎn)單廣播協(xié)議的改進(jìn)，使其具有拓?fù)潆[藏的能力。根據(jù)廣播深度(只廣播到一個(gè)有限的范圍，如本地信息查詢)或網(wǎng)絡(luò)直徑diam(G)(廣播到整個(gè)網(wǎng)絡(luò))，協(xié)議經(jīng)過(guò)多輪執(zhí)行完成：

(6)

(7)

Step 3 結(jié)束階段

為了確保任何節(jié)點(diǎn)在最后都能正確恢復(fù)出廣播消息，我們將最后一輪作為獨(dú)立的階段進(jìn)行描述。在最后一輪t=e中，每個(gè)節(jié)點(diǎn)對(duì)其收到消息計(jì)算半同態(tài)和

(8)

6 協(xié)議性能及安全性分析

首先，我們給出該方案的兩個(gè)安全性定理及其證明。

定理1 即使攻擊者控制了網(wǎng)絡(luò)任何一部分節(jié)點(diǎn)，其余節(jié)點(diǎn)的拓?fù)潆[藏信息也不會(huì)被泄露。

證明：我們根據(jù)Tal Moran所提出的基于不可分辨性博弈拓?fù)潆[藏安全性定義進(jìn)行證明。

將網(wǎng)絡(luò)表示為圖G=(V,E)，設(shè)Π為運(yùn)行在網(wǎng)絡(luò)中的廣播協(xié)議，并定義節(jié)點(diǎn)vi的輸入為mi∈{0,ms}，其中ms表示待廣播的消息。

假設(shè)攻擊者已控制網(wǎng)絡(luò)G中任意一部分節(jié)點(diǎn)A∈V,并將mj作為已攻破節(jié)點(diǎn)vj∈A的輸入。隨后，根據(jù)已控制節(jié)點(diǎn)分別構(gòu)造兩圖Gk=(Vk,Ek)，其中k∈{0,1},滿足A?V0∩V1及NG0[A]=NG1[A]，并將相關(guān)信息 (A;G0,G1;{mj})發(fā)送給挑戰(zhàn)者。如有A?V0∩V1或存在非法輸入mj則認(rèn)為挑戰(zhàn)者自動(dòng)獲勝。

然后，挑戰(zhàn)者隨機(jī)選取b∈{0,1}并在圖Gb中運(yùn)行協(xié)議Π，攻擊者可觀察到已攻破節(jié)點(diǎn)vj∈A的整個(gè)執(zhí)行過(guò)程。

最后，攻擊者判斷該協(xié)議在哪一個(gè)圖中運(yùn)行，并輸出自己的結(jié)果b′∈{0,1}。如果b′=b我們便認(rèn)為他贏得該博弈，否則為失敗。

根據(jù)上述規(guī)則,基于不可分辨性博弈的拓?fù)潆[私安全可定義如下：

定義1 對(duì)于任何計(jì)算能力在概率多樣式時(shí)間內(nèi)的攻擊者I而言，若存在一個(gè)足夠小的值μ(n)，滿足在多方安全計(jì)算協(xié)議執(zhí)行完成后有

(9)

我們則稱該協(xié)議在選擇拓?fù)涔粝率遣豢煞直嫘园踩摹?/p>

定理2 服務(wù)器不知道有關(guān)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的任何信息。

為能夠真實(shí)反映協(xié)議應(yīng)用的實(shí)際場(chǎng)景，我們利用RepastSymphony建模工具來(lái)實(shí)現(xiàn)協(xié)議的性能分析?？紤]到我們的方案是第一次將拓?fù)潆[藏廣播實(shí)例化，為便于比較，我們還分別利用RSA密碼體制以及NTRU加密算法對(duì)文獻(xiàn)[8]中的協(xié)議進(jìn)行了仿真。事實(shí)上，盡管我們的協(xié)議受TalMoran的開(kāi)創(chuàng)性工作[8]所啟發(fā)，但它在秘密共享及加密方案等方面很大程度上有別于它。還值得一提的是，TalMoran忽視了一個(gè)關(guān)鍵問(wèn)題即如何處理從封閉鄰域的共享密鑰中恢復(fù)出原始密鑰。為此，我們將TalMoran協(xié)議中密鑰重構(gòu)及加密解密等操作交由服務(wù)器完成，但這也就意味著網(wǎng)絡(luò)拓?fù)鋵⒈┞督o第三方?？紤]到仿真與現(xiàn)實(shí)中因特網(wǎng)、無(wú)線自組織網(wǎng)拓?fù)浣Y(jié)構(gòu)的一致性以及抗密碼分析能力[12]，我們用Watts-Strogatz結(jié)構(gòu)來(lái)構(gòu)建網(wǎng)絡(luò)并選擇實(shí)驗(yàn)參數(shù)(如表1所示)。

表1 仿真參數(shù)Tab.1 Simulation parameters

仿真使用的硬件平臺(tái)為英特爾酷睿i5-2430m處理器及3GB內(nèi)存，而實(shí)際應(yīng)用中可選用性能更高的服務(wù)器系統(tǒng)以提高性能。由于運(yùn)行負(fù)載主要由服務(wù)器承擔(dān)，因此其每一輪的計(jì)算負(fù)荷和通信開(kāi)銷通過(guò)50次測(cè)試的平均值求得并與TalMoran的協(xié)議進(jìn)行對(duì)比，如圖1和圖2所示。

圖1 每一輪每個(gè)節(jié)點(diǎn)服務(wù)器的計(jì)算負(fù)擔(dān)Fig.1 Computation burden of server for each round per node

通過(guò)圖1可以看出，我們方案的計(jì)算復(fù)雜度在平均節(jié)點(diǎn)度數(shù)較大時(shí)明顯優(yōu)于TalMoran協(xié)議。這是因?yàn)樵赥alMoran的協(xié)議中解密加密操作必須執(zhí)行deg(vi)+1次，而我們的方案只需執(zhí)行固定次數(shù)為n+1的NTRU算法。即使為提高效率而采用NTRU算法來(lái)實(shí)現(xiàn)TalMoran協(xié)議，但隨著平均度數(shù)的增加，其性能退化仍然突出。在我們方案中，雖然每個(gè)節(jié)點(diǎn)向服務(wù)器發(fā)送消息前必須執(zhí)行半同態(tài)運(yùn)算并偽造虛假密文，但高效的多項(xiàng)式計(jì)算不會(huì)帶來(lái)太多的運(yùn)行負(fù)荷。當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)，我們也可以通過(guò)部署一系列的本地服務(wù)器對(duì)服務(wù)器負(fù)載進(jìn)行分?jǐn)偂?/p>

就通信開(kāi)銷而言，每個(gè)節(jié)點(diǎn)首先廣播當(dāng)前Nlbq位的中間結(jié)果給相鄰節(jié)點(diǎn)，而置換后提交給服務(wù)器的多項(xiàng)式總共(n+1)Nlbq位。從服務(wù)器返回的信息長(zhǎng)度亦與收到的信息長(zhǎng)度相同。假定TalMoran的協(xié)議中RSA或NTRU密鑰長(zhǎng)度為K(在我們的實(shí)驗(yàn)中，RSA的密鑰長(zhǎng)度為1 024bit，NTRU的密鑰長(zhǎng)度為N(2+「lbp?)=3 123bit)，則服務(wù)器必須獲取(deg(vi)+1)K比特的共享密鑰信息并執(zhí)行或運(yùn)算來(lái)恢復(fù)出節(jié)點(diǎn)vi的私鑰。同時(shí)，用RSA實(shí)現(xiàn)時(shí)服務(wù)器需收發(fā)(deg(vi)+1)K比特的密文，而用NTRU實(shí)現(xiàn)時(shí)其收發(fā)的密文長(zhǎng)度為(deg(vi)+1)N「lbq?位。由于密文較長(zhǎng)，基于NTRU實(shí)現(xiàn)的協(xié)議均會(huì)帶來(lái)更多的通信開(kāi)銷。然而，由于我們的協(xié)議中的通信開(kāi)銷只與偽造密文的數(shù)量相關(guān)，它不會(huì)TalMoran方案隨著節(jié)點(diǎn)平均度數(shù)的增加而增加，如圖2所示。

圖2 每輪每個(gè)節(jié)點(diǎn)服務(wù)器的通信開(kāi)銷Fig.2 Communication overhead of server for each round per node

還值得一提的是，TalMoran協(xié)議中任一節(jié)點(diǎn)的私鑰都以秘密共享的方式分布在其封閉鄰域當(dāng)中，因此相鄰節(jié)點(diǎn)的身份無(wú)法隱藏，且網(wǎng)絡(luò)必須是靜態(tài)的。同時(shí)，TalMoran沒(méi)有解決密鑰重構(gòu)的問(wèn)題，這便意味著密鑰一旦恢復(fù)則可能被攻擊者所利用，而我們的方案不存在上述缺陷。

7 結(jié)束語(yǔ)

本文的主要貢獻(xiàn)是設(shè)計(jì)了一種安全高效的拓?fù)潆[藏廣播協(xié)議。我們基于文獻(xiàn)[8]中的簡(jiǎn)單廣播方案，利用NTRU半同態(tài)性質(zhì)及秘密共享機(jī)制來(lái)防止任何一方通過(guò)中間結(jié)果推斷出網(wǎng)絡(luò)拓?fù)湫畔ⅰＥcTal Moran方案所進(jìn)行的性能比較以及安全性分析表明，我們的協(xié)議在計(jì)算強(qiáng)度、通信負(fù)荷以及安全性方面是相對(duì)較優(yōu)的。然而，如果服務(wù)器與任何網(wǎng)絡(luò)節(jié)點(diǎn)相勾結(jié)，我們的協(xié)議將不再安全，因此我們把該問(wèn)題的解決作為下一步工作方向。此外，我們?cè)诜桨钢袥](méi)有考慮惡意攻擊模型，因此如何在主動(dòng)攻擊的環(huán)境中實(shí)現(xiàn)廣播協(xié)議的拓?fù)潆[藏功能也將是有待考慮的問(wèn)題之一。

[1] YAO A C. Protocols for secure computations[C]//Proceedings of 23rd Annual Symposium on Foundations of Computer Science.Chicago,IL,USA:IEEE,1982:160-164.

[2] PETTAI M,LAUD P. Automatic proofs of privacy of secure multi-party computation protocols against active adversaries[C]//Proceedings of 2005 28th IEEE Computer Security Foundations Symposium.Verona,Italy:IEEE,2015:75-89.

[3] SHUKLA S,SADASHIVAPPA G. Secure multi-party computation protocol using asymmetric encryption[C]//Proceedings of 2014 International Conference on Computing for Sustainable Global Development.New Delhi,India:IEEE,2014:780-785.

[4] NAOR M,PINKAS B,SUMNER R. Privacy preserving auctions and mechanism design[C]//Proceedings of ACM Conference on Electronic Commerce. Denver,CO,USA:IEEE,2015:129-139.

[5] 蒙云番,孫光昊,邢杰,等. 基于網(wǎng)絡(luò)編碼和ECC的無(wú)線體域網(wǎng)安全簽名方案[J].電訊技術(shù),2015,55(6):605-610. MENG Yunfan,SUN Guanghao,XING Jie,et al.A secure signature scheme for wireless body area networks based on network coding and ECC algorithm[J].Telecommunication Engineering,2015(6) :605-610.(in Chinese)

[6] 霍躍華,劉銀龍. 內(nèi)容中心網(wǎng)絡(luò)中安全問(wèn)題研究綜述[J].電訊技術(shù),2016,56(2):224-232. HUO Yuehua,LIU Yinlong.Survey on security issues in content-centric networking[J].Telecommunication Engineering,2016,56(2) :224-232.(in Chinese)

[7] GOLDWASSER S. Multi-party computations:past and present[C]//Proceedings of Sixteenth ACM Symposium on Principles of Distributed Computing.Santa Barbara,CA,USA:ACM,1997:1-6.

[8] MORAN T,ORLOV I,RICHELSON S. Topology-hiding computation[M]//Theory of Cryptography.Heidelberg,Berlin:Springer,2015:159-181.

[9] HINKELMANN M,JAKOBY A.Communications in unknown networks:preserving the secret of topology[J].Theoretical Computer Science,2007,384(2):184-200.

[10] HOFFSTEIN J,PIPHER J,SILVERMAN J H. NTRU:a ring-based public key cryptosystem[C]//Proceedings of 1998 International Symposium on Algorithmic Number Theory.Heidelberg,Berlin:Springer-Verlag,1998:267-288.

[11] HERMANS J,VERCAUTEREN F,PRENEEL B. Speed records for NTRU topics in cryptology-CT-RSA 2010[M].Heidelberg,Berlin:Springer,2010:73-88.

[12] STEHLE D,STEINFELD R. Making NTRU as secure as worst-case problems over ideal lattices[C]//Proceedings of 2011 International Conference on Theory and Applications of Cryptographic Techniques:Advances in Cryptology.Heidelberg,Berlin:Springer-Verlag,2011:27-47.

[13] 陳虎,胡予濮. NTRU格上無(wú)證書(shū)加密[J].電子與信息學(xué)報(bào),2016,38(2):347-353. CHEN Hu,HU Yupu. Certificateless encryption over NTRU lattices[J].Journal of Electronics and Information Technology,2016,38(2):347-353.(in Chinese)

黃大榮(1978—) ，男，湖北建始人，2006 年于重慶大學(xué)獲工學(xué)博士學(xué)位，現(xiàn)為副教授、碩士生導(dǎo)師，主要研究方向?yàn)閺?fù)雜系統(tǒng)的可靠性分析、 信息融合理論、 故障診斷與預(yù)測(cè)。

Email: drhuang@cquc.edu.cn

Design of a Topology-hiding Broadcast Protocol Based on Oblivious Transfer

MI Bo,ZHOU Xiaoyan,HUANG Darong
(School of Information Science and Engineering，Chongqing Jiaotong University，Chongqing 400074，China)

In order to protect sensitive information such as node relationship and geographical position,an efficient public key cryptosystem named NTRU(Number Theory Research Unit) is introduced into oblivious transfer protocol and an untrusted third party is used to hide the intermediate process of broadcasting for the sake of topological privacy. The protocol can be considered as the implementation of topology hiding broadcast,and it addresses some uncovered problems of its previous conceptual schemes such as key reconstruction,confidentiality of IDs within neighboring nodes as well as nodes network dynamicity. Security and performance analysis indicates that the proposed protocol endures topology concealment as long as any part of the network is corrupted,and manifests its merits of low computation and communication overheads as well as the advantage of independence on node degree.

secure multi-party computation(SMC);topology-hiding;number theory research unit(NTRU);oblivious transfer;broadcast protocol design

2016-05-03；

2016-08-12 Received date:2016-05-03；Revised date：2016-08-12

重慶市教委科學(xué)技術(shù)研究項(xiàng)目(JK1705139)

10.3969/j.issn.1001-893x.2017.02.009

米波，周小艷，黃大榮.基于不經(jīng)意傳輸?shù)耐負(fù)潆[藏廣播協(xié)議設(shè)計(jì)[J].電訊技術(shù)，2017,57(2):173-179.[MI Bo,ZHOU Xiaoyan,HUANG Darong.Design of a topology-hiding broadcast protocol based on oblivious transfer[J].Telecommunication Engineering,2017,57(2):173-179.]

TN918.91

A

1001-893X(2017)02-0173-07

米 波(1982—)，男，重慶永川人，2009年于重慶大學(xué)獲工學(xué)博士學(xué)位，現(xiàn)為副教授、碩士生導(dǎo)師，主要研究方向?yàn)槎喾桨踩?jì)算、數(shù)據(jù)隱私保護(hù)和無(wú)線自組織網(wǎng)絡(luò)安全；

Email:mi_bo@163.com

周小艷(1991—)，女，湖北荊州人，2014年獲學(xué)士學(xué)位，現(xiàn)為碩士研究生，主要研究方向?yàn)槎喾桨踩?jì)算;

Email:hellozxy_1991@163.com

*通信作者：hellozxy_1991@163.com Corresponding author：hellozxy_1991@163.com