單服務(wù)器模型下雙線性運算外包協(xié)議設(shè)計

王少輝，李 赫，劉夢青，肖 甫

(1.南京郵電大學(xué) 計算機學(xué)院，江蘇 南京 210003；2.江蘇省無線傳感網(wǎng)高技術(shù)研究重點實驗室，江蘇 南京 210003)

單服務(wù)器模型下雙線性運算外包協(xié)議設(shè)計

王少輝1,2，李 赫1,2，劉夢青1,2，肖 甫1,2

(1.南京郵電大學(xué) 計算機學(xué)院，江蘇 南京 210003；2.江蘇省無線傳感網(wǎng)高技術(shù)研究重點實驗室，江蘇 南京 210003)

雙線性對運算在密碼學(xué)領(lǐng)域具有廣泛的應(yīng)用，但是雙線性對運算也是此類密碼協(xié)議中最耗計算資源的運算。目前解決該問題的方法之一是將復(fù)雜的運算外包給計算能力強大但不可信的服務(wù)器。對最近在雙服務(wù)器模型下提出的雙線性對運算外包協(xié)議的安全性進行了分析，分析結(jié)果表明如果資源受限設(shè)備發(fā)起的質(zhì)詢消息以明文的方式發(fā)送，則這些協(xié)議不能提供足夠的安全性保障。并且在單服務(wù)器模型下提出了一個高效的可驗證雙線性對運算外包協(xié)議，即外包用戶可以驗證服務(wù)器回復(fù)消息的正確性。新協(xié)議中受限設(shè)備只需執(zhí)行1個G1和G2中的標量加法和1個群GT中的模冪運算，執(zhí)行效率要優(yōu)于目前已提出的雙線性對運算外包協(xié)議。

雙線性對；云計算；安全外包；可驗證性

1 概 述

2000年，Joux[1]發(fā)現(xiàn)橢圓曲線上雙線性對可應(yīng)用于密碼算法的設(shè)計中，而Boneh和Franklin[2]利用雙線性對提出了第一個適用的基于身份的加密方案。此后，雙線性對運算成為密碼學(xué)領(lǐng)域最常用的設(shè)計工具之一，其廣泛應(yīng)用于基于身份的密碼系統(tǒng)的算法設(shè)計中。盡管眾多密碼學(xué)者提出不同的方法以提高雙線性對運算的執(zhí)行效率[3-4]，但相比模冪運算，雙線性對的計算成本仍然太高，以致不能應(yīng)用在某些資源受限的設(shè)備中，如RFID、智能卡等。

隨著云計算的快速發(fā)展，如何將耗資源運算，如模冪運算、雙線性對運算，安全地外包給計算功能強大但不可信的服務(wù)器，已成為科學(xué)界密切關(guān)注的研究熱點之一。在計算外包應(yīng)用中，資源受限用戶可以通過按次付費的方式，無限次使用外部的計算資源，從而減少企業(yè)用戶在部署和維護硬件/軟件方面的支出開銷。

雙線性對運算外包協(xié)議通常需要考慮如下的安全需求：

隱私性：該安全需求要求不可信服務(wù)器在參與運算外包的過程中，不能獲得任何有關(guān)用戶隱私數(shù)據(jù)的信息(如雙線性對運算的輸入或輸出信息)。

可驗證性：外包用戶可以驗證服務(wù)器返回結(jié)果的正確性，即一個誠信的云服務(wù)器返回的正確結(jié)果一定能通過用戶的驗證，并被用戶接受；而惡意服務(wù)器返回的錯誤結(jié)果則不能通過用戶的驗證。

服務(wù)器的數(shù)量：在單服務(wù)器模型中，只允許一個不可信服務(wù)器參與運算外包協(xié)議；而雙服務(wù)器模型則意味著用戶將運算外包給兩個相互獨立的服務(wù)器，并假設(shè)這兩個服務(wù)器獨立運作，不會合謀以獲得額外的秘密信息。

針對具體的密碼學(xué)運算，密碼學(xué)者已經(jīng)提出了眾多運算外包協(xié)議[5-7]，同時也提出了一些通用的安全運算外包協(xié)議構(gòu)造[8-9]。具體到雙線性對運算，2005年，Girault和Lefranc[10]提出了服務(wù)器輔助驗證的概念，第一次對基于雙線性對密碼方案的安全外包算法進行了研究。他們將雙線性對運算的輸入進行盲化，從而實現(xiàn)了無條件的隱私性安全保障。Mames等[11]首次提出了可驗證的雙線性對運算外包協(xié)議，他們通過讓一臺服務(wù)器計算兩組可比較的結(jié)果來檢查服務(wù)器返回數(shù)據(jù)的正確性。Kang等[12]對文獻[11]的結(jié)果進行改進，提出了一種更高效的方案。但是，這些方案的計算效率仍然比較低，并不能適用在資源受限的設(shè)備中。

Canard等在文獻[13]中提出了一種更高效的可驗證雙線性對運算外包協(xié)議。當雙線性對的輸入可公開時，該協(xié)議只需要2個群G1和G2中的標量乘法運算和1個群GT下的模冪運算。Guillevic等[14]提出了兩種滿足隱私性的高效雙線性對運算外包協(xié)議。在單服務(wù)器模式下，新協(xié)議的執(zhí)行效率要優(yōu)于以往所有協(xié)議，但該協(xié)議不滿足可驗證性。針對雙服務(wù)器模型，Chen等[15]提出了一種安全的雙線性對運算外包協(xié)議，該協(xié)議的顯著特點是資源受限設(shè)備不需要進行任何耗資源操作，如群G1上的標量乘法運算或GT上的模冪運算。最近，Tian等[16]在雙服務(wù)器模型下，提出了兩種新的計算外包算法以優(yōu)化文獻[15]算法的效率。

文中首先回顧了在雙服務(wù)器模型下最近新提出的一些雙線性對運算外包協(xié)議[15-16]的安全性。在雙服務(wù)器模型下，通常都假設(shè)兩個服務(wù)器中至多存在一個惡意的服務(wù)器。如果資源受限設(shè)備發(fā)送的質(zhì)詢消息是明文發(fā)送，則文獻[15-16]中所提方案并不能抵御攻擊者或惡意服務(wù)器所發(fā)起的被動攻擊，其可以以很高的概率推斷出雙線性對運算的輸入或輸出。接著在單服務(wù)器模型下提出了一種高效的可驗證雙線性對運算外包協(xié)議，新方案只需1個群G1和G2中的標量乘法運算和1個群GT中的模冪運算。

2 基礎(chǔ)知識

2.1 雙線性對

設(shè)加法循環(huán)群G1、G2和乘法循環(huán)群GT具有相同的大素數(shù)階q，g1、g2分別為群G1和G2的生成元，雙線性對運算e:G1×G2→GT滿足3個性質(zhì)：

(2)非退化性：存在R∈G1,Q∈G2，并且有e(R,Q)≠1；

(3)可計算性:對所有R∈G1,Q∈G2，存在有效算法計算e(R,Q)。

2.2 安全雙線性對運算外包協(xié)議

通常一種安全的雙線性對運算外包協(xié)議由計算資源受限的外包用戶T和計算資源強大的外包服務(wù)器組成，按照參與服務(wù)器的數(shù)目，可以分為單服務(wù)器運算外包協(xié)議和雙服務(wù)器運算外包協(xié)議。圖1給出了單服務(wù)器下的雙線性對運算外包協(xié)議的執(zhí)行過程。此時，用戶T為了計算雙線性對e(A,B)的值，首先向服務(wù)器發(fā)起質(zhì)詢消息(QueryMessages)；然后服務(wù)器對用戶的質(zhì)詢做出響應(yīng)(ResponseMessages)；用戶最終將推導(dǎo)得到雙線性對e(A,B)的值。

圖1 單服務(wù)器模型下的運算外包過程

Mames等[11]指出一個安全的單服務(wù)器雙線性對運算外包協(xié)議應(yīng)提供完備性、可驗證性和隱私性這三種安全需求：

(1)完整性：當外包用戶和一個誠實的服務(wù)器交互執(zhí)行協(xié)議后，用戶T將以不可忽略的概率優(yōu)勢計算得到e(A,B)。

(2)隱私性：一個不可信服務(wù)器不能通過協(xié)議的交互獲得任何關(guān)于雙線性對輸入A和B，或者輸出e(A,B)的信息。將外包協(xié)議執(zhí)行過程中，服務(wù)器所接收到的消息記做View(A,B)，隱私性也就是說，對于任何惡意服務(wù)器，都存在一個模擬器S，對于任何輸入A和B，模擬器S的輸出和服務(wù)器接收的消息View(A,B)計算不可區(qū)分。

(3)可驗證性：外包用戶T能以不可忽略的概率優(yōu)勢檢測到不可信服務(wù)器的欺騙行為。即，對任意的雙線性對輸入A和B，對于不可信服務(wù)器的錯誤響應(yīng)消息，用戶T能以不可忽略的概率優(yōu)勢發(fā)現(xiàn)錯誤，并輸出錯誤結(jié)果⊥。

雙服務(wù)器模型下的雙線性對運算外包協(xié)議執(zhí)行過程如圖2所示。此時外包用戶將分別向兩個服務(wù)器發(fā)起質(zhì)詢消息，并利用接收到的兩組應(yīng)答消息計算得到e(A,B)的值。雙服務(wù)器模型要求兩個服務(wù)器至少有一個是誠實服務(wù)器，并且兩個服務(wù)器彼此獨立運行，不會合謀破壞協(xié)議的安全性，其安全需求與單服務(wù)器模型下的外包協(xié)議類似，這里不再贅述。

圖2 雙服務(wù)器模型下的運算外包過程

3 方案的安全分析

最近，Chen等[15]在雙服務(wù)器模型下，提出了一種高效的雙線性對運算外包協(xié)議Pair。與以往的算法相比，Pair協(xié)議的顯著特性是外包用戶T只需要進行群G1和G2中的點加運算和群GT中的乘法運算，而不需要進行任何耗資源運算，如標量乘法運算和模冪運算。而在2015年AsiaCCS國際大會上，Tian等[16]進一步改進了Chen等的方案，提出了兩種新的雙服務(wù)器模型下的雙線性對運算外包協(xié)議。

因為外包用戶T通常是一些資源受限的設(shè)備，如智能卡片、RFID標簽或傳感器節(jié)點，所以通常在外包用戶和服務(wù)器之間創(chuàng)建安全信道是不可行的。如果外包用戶T發(fā)起的質(zhì)詢消息以明文的方式發(fā)送給服務(wù)器，那么文獻[15-16]所提方案將不能提供任何的安全保障，因為攻擊者通過被動的偵聽信道便可以以很高的概率優(yōu)勢推斷出雙向性對運算的輸入A,B以及輸出e(A,B)。

下面以Pair協(xié)議為例，說明上面提到的三種雙線性對運算外包協(xié)議存在的安全缺陷。

對于A∈G1,B∈G2，為了安全外包運算e(A,B)，Pair協(xié)議將執(zhí)行以下操作：

(1)用戶T運行Rand算法得到三個六元組：(Xi,Yi,xiXi,yiXi,yiYi,e(Xi,Yi)xi+yi-xiyi),i=1,2,3。

(2)用戶T按照隨機順序向服務(wù)器1發(fā)起以下質(zhì)詢：

S1(A+x1X1,B+y1Y1)→e(A+x1X1,B+y1Y1)=α1

S1(x2X2,y2Y2)→e(x2X2,y2Y2)

S1(x3X3,y3Y3)→e(x3X3,y3Y3)

其中，S1(ι1,ι2)→e(ι1,ι2)表示用戶T發(fā)送雙線性對的輸入(ι1,ι2)給服務(wù)器1，而服務(wù)器1返回響應(yīng)結(jié)果e(ι1,ι2)。

(3)用戶T按照隨機順序向服務(wù)器2發(fā)起以下質(zhì)詢：

S2(A+X1,y1Y1)→e(A+X1,y1Y1)=α2

S2(x1X1,B+Y1)→e(x1X1,B+Y1)=α3

S2(x2X2,y2Y2)→e(x2X2,y2Y2)

S2(x3X3,y3Y3)→e(x3X3,y3Y3)

(4)用戶T通過檢驗兩個服務(wù)器是否返回不同的e(x2X2,y2Y2)和e(x3X3,y3Y3)的值來驗證兩個服務(wù)器中是否存在惡意服務(wù)器。如果不相等則驗證失敗，T輸出“錯誤”；否則e(A,B)可以通過如下方式計算得到：

安全分析如下：

假設(shè)用戶T發(fā)送給服務(wù)器1和服務(wù)器2的質(zhì)詢消息都為明文，一個被動攻擊者可以通過竊聽信道，收集到雙線性對運算的7對輸入和響應(yīng)的回復(fù)消息。如果兩個服務(wù)器都誠實地執(zhí)行Pair協(xié)議，攻擊者通過比較響應(yīng)消息，可以丟棄雙線性對e(x2X2,y2Y2)和e(x3X3,y3Y3)。

此時攻擊者手中擁有三組質(zhì)詢—響應(yīng)消息組：((β1,β2)→α1), ((γ1,θ1)→α2), ((γ2,θ2)→α3)。這樣攻擊者可以以0.5的概率推導(dǎo)出e(A,B)的值，因為下面的兩個等式至少有一個成立：

e(A,B)=e(β1-γ1,β2-θ2)

e(A,B)=e(β1-γ2,β2-θ1)

4 單服務(wù)器模型下外包協(xié)議的設(shè)計

本節(jié)首先在單服務(wù)器模型下，提出了一種新的雙線性對運算外包協(xié)議，然后給出協(xié)議的安全性分析以及和其他協(xié)議的性能比較。

4.1 新方案設(shè)計

協(xié)議的輸入是A∈G1,B∈G2，輸出是e(A,B)，其中要求輸入A,B滿足隱私性。新單服務(wù)器下的雙線性對運算外包協(xié)議執(zhí)行如下：

(1)用戶T調(diào)用Rand算法得到一個新的七元組：(a,b,-X1,-Y1,aX1,bY1,e(X1,Y1)-ab)。

(2)用戶T向服務(wù)器發(fā)起以下隨機查詢：

S(A+aX1,B+bY1)→e(A+aX1,B+bY1)=α1

S(bA,aB)→e(bA,aB)=α2

S(-X1,aB)→e(-X1,aB)=α3

S(bA,-Y1)→e(bA,-Y1)=α4

(3)用戶T檢查如下公式是否成立：

α2=(α1α3α4e(X1,Y1)-ab)ab

若成立，則計算并得到雙線對e(A,B)的值為：

e(A,B)=α1α3α4e(X1,Y1)-ab

否則，拒絕服務(wù)器端返回的結(jié)果，并輸出“錯誤”。

4.2 性能比較和安全性分析

(1)性能比較。

Canard等在文獻[13]中針對雙線性對e(A,B)的輸入A和B可公開的應(yīng)用，提出了一種高效的雙線性對運算外包協(xié)議，同時為了獲得輸入信息的隱私性，他們還提出了一般的通用轉(zhuǎn)換方法。Canard等所提方案是目前單服務(wù)器模型下效率最優(yōu)的雙線性對運算外包協(xié)議，表1中給出了文中新提出的外包協(xié)議和Canard等所提方案中外包用戶和服務(wù)器的性能比較。

表1 計算開銷比較

這里只統(tǒng)計在線運算量。如表1所示，m1,m2分別表示群G1和G2中的標量乘法運算，而eT代表群GT中的模冪運算，這兩種運算比群G1的點加運算或GT的點乘運算要耗費更多的資源。通過比較可以看出，文中提出的新算法中，外包用戶需要1個群G1和G2中的標量乘法運算，和1個群GT中的模冪運算，遠少于文獻[13]中外包用戶的計算量；而兩種協(xié)議中服務(wù)器端的計算量相當，都需要計算4個雙線性對運算，這里用PT表示。

(2)安全分析。

類似文獻[11-12]中協(xié)議的安全性論證，通過如下定理證明新協(xié)議滿足運算外包協(xié)議的安全需求。

定理1：新提出的雙線性對運算外包協(xié)議是一種滿足隱私性的安全可驗證的運算外包協(xié)議，即新協(xié)議滿足完備性、保密性和可驗證性。

證明：

完備性：容易驗證下列公式一定成立：

α1α3α4e(X1,Y1)-ab=e(A+aX1,B+

bY1)e(-X1,aB)e(bA,-Y1)e(X1,Y1)-ab=

e(A,B)e(A,Y1)be(X1,B)ae(X1,Y1)abe(A,

Y1)-be(X1,B)-ae(X1,Y1)-ab=e(A,B)

并且有：

α2=e(bA,aB)=e(A,B)ab

隱私性：從協(xié)議的設(shè)計可以看到，服務(wù)器所接收到的質(zhì)詢消息均是來自群G1和G2中隨機獨立分布的點。因此，模擬器S只需運行生成群G1和G2中隨機點，此時，模擬器的輸出和服務(wù)器接收到的消息分布計算不可區(qū)分。

可驗證性：如果α2≠e(A,B)ab，則下面的值在群GT中幾乎均勻地分布：

(1)

假設(shè)X1和Y1分別是G1和G2的生成元，并且A=xX1,B=yY1。對于x,y,u,v,w,z∈Zq，記U=A+aX1=uX1,V=B+bY1=vY1,W=bA=wX1和Z=aB=zY1。顯然下列等式一定成立：

u=x+a,v=y+b,w=bx,z=ay

并且存在β1,β2,β3,β4∈Zq，有如下等式成立：

α1=e(A+aX1,B+bY1)e(X1,Y1)β1

α2=e(A,B)abe(X1,Y1)β2

α3=e(X1,B)-ae(X1,Y1)β3

α4=e(A,Y1)-be(X1,Y1)β4

顯然當且僅當β2=0時，α2=e(A,B)ab。下面將說明當β2≠0時，用戶T將以不可忽略的概率輸出“錯誤”。由式(1)可以得到：

β1=β2(ab)-1-β3-β4modq

5 結(jié)束語

文中首先對最近提出的雙服務(wù)器模型下的雙線性對運算外包協(xié)議的安全性進行了分析，分析結(jié)果表明如果應(yīng)用中不存在安全信道，這些方案并不能提供足夠的安全性保證。作為被動的攻擊者，可以以較大的概率優(yōu)勢推測得到用戶所計算的雙線性對運算的輸入和輸出參數(shù)。同時，針對單服務(wù)器模型，提出了一種高效的可驗證的安全雙線性對運算外包協(xié)議，在解決雙線性對計算問題的同時，也保證了服務(wù)端返回結(jié)果的可驗證性，以使外包用戶可以放心地將自身的運算外包給云服務(wù)器完成。新方案只需要1個群G1和G2的標量加法運算，和1個群GT下的模冪運算。經(jīng)過比較分析，可以看出新協(xié)議的執(zhí)行效率要明顯優(yōu)于目前已有的方案。

為了提供可驗證性，認為在單服務(wù)器模型下設(shè)計雙線性對運算外包協(xié)議不可避免地要用到模冪運算，而模冪運算是除雙線性對運算外最耗費資源的密碼學(xué)運算。如何在單服務(wù)器模型和雙服務(wù)器模型下設(shè)計更為高效的安全雙線性對運算外包協(xié)議，將是下一步重點考慮的研究工作。

[1]JouxA.AoneroundprotocolfortripartiteDiffie-Hellman[C]//Internationalalgorithmicnumbertheorysymposium.[s.l.]:[s.n.],2006:385-393.

[2]BonehD,FranklinM.Identity-basedencryptionfromtheWeilpairing[C]//Annualinternationalcryptologyconference.Berlin:Springer,2001:213-229.

[3]BarretoP,GalbraithS,OheigeartaighC,etal.EfficientpairingcomputationonsupersingularAbelianvarieties[J].Designs,CodesandCryptography,2007,42(3):239-271.

[4]BarretoP,NaehrigM.Pairing-friendlyellipticcurvesofprimeorder[C]//Internationalworkshoponselectedareasincryptography.Berlin:Springer,2005.

[5]MatsumotoT,KatoK,ImaiH.Speedingupsecretcomputationswithinsecureauxiliarydevices[C]//Conferenceonthetheoryandapplicationofcryptography.NewYork:Springer,1988.

[6]ChaumD,PedersenT.Walletdatabaseswithobservers[C]//Annualinternationalcryptologyconference.Berlin:Springer,1992.

[7]LimCH,LeePJ.Server(prover/signer)-aidedverificationofidentityproofsandsignatures[C]//Internationalconferenceonthetheoryandapplicationsofcryptographictechniques.Berlin:Springer,1995.

[8]YaoAC.Protocolsforsecurecomputations[C]//23rdannualsymposiumonfoundationsofcomputerscience.[s.l.]:[s.n.],1982.

[9]CanardS,CoiselI,DevigneJ,etal.Towardgenericmethodforserver-aidedcryptography[C]//Internationalconferenceoninformationandcommunicationssecurity.[s.l.]:SpringerInternationalPublishing,2013.

[10]GiraultM,LefrancD.Server-aidedverification:theoryandpractice[C]//Internationalconferenceonthetheoryandapplicationofcryptologyandinformationsecurity.Berlin:Springer,2005.

[11]Chevallier-MamesB,CoronJS,McCullaghN,etal.Securedelegationofelliptic-curvepairing[C]//Internationalconferenceonsmartcardresearchandadvancedapplications.Berlin:Springer,2010.

[12]KangB,LeeM,ParkJ.Efficientdelegationofpairingcomputation[R].[s.l.]:[s.n.],2005.

[13]CanardS,DevigneJ,SandersO.Delegatingapairingcanbebothsecureandefficient[C]//Internationalconferenceonappliedcryptographyandnetworksecurity.[s.l.]:SpringerInternationalPublishing,2014.

[14]GuillevicA,VergnaudD.Algorithmsforoutsourcingpairingcomputation[C]//Internationalconferenceonsmartcardresearchandadvancedapplications.[s.l.]:SpringerInternationalPublishing,2014.

[15]ChenXiaofeng,SusiloW,LiJin,etal.Efficientalgorithmsforsecureoutsourcingofbilinearpairings[J].TheoreticalComputerScience,2015,562:112-121.

[16]TianHaibo,ZhangFangguo,RenKui.Securebilinearpairingoutsourcingmademoreefficientandflexible[C]//Proceedingsofthe10thACMsymposiumoninformation,computerandcommunicationssecurity.[s.l.]:ACM,2015.

Design of Efficient Outsourcing Protocol of Bilinear Pairings for a Single Server

WANG Shao-hui1,2,LI He1,2,LIU Meng-qing1,2,XIAO Fu1,2

(1.College of Computer,Nanjing University of Posts and Telecommunications,Nanjing 210003,China; 2.Key Laboratory of Jiangsu High Technology Research for Wireless Sensor Networks,Nanjing 210003,China)

Bilinear pairing operation has been widely applied in cryptography field,but the computation of bilinear pairings has been considered the most expensive operation in pairing-based cryptographic protocol.One of the ways to solve this problem now is to outsource expensive computation to untrusted but powerful servers.The security of some recently proposed pairing delegation algorithms are analyzed in the two-server assumption model,and it is found that if the query messages sent by the source-constrained devices are plaintext,these protocols cannot provide enough security guarantee.Also an efficient verifiable secret pairing outsourcing protocol is put forward in the single server assumption model,and the protocol enables the limited device to verify the value received from the server with one scalar addition inG1andG2,andoneexponentiationinGT,whichismuchmoreefficientthantheexistingprotocols.

bilinear pairing;cloud computing;secure outsourcing;verifiability

2016-01-29

2016-05-18

時間：2016-10-24

國家自然科學(xué)基金資助項目(61373006,61373139)；江蘇省科技支撐計劃基金項目(61003236)；南京郵電大學(xué)校科研項目(NY214064,NY213036)

王少輝(1977-),男,博士,副教授,研究方向為信息安全、密碼學(xué);李 赫(1993-),男,碩士研究生，研究方向為P2P網(wǎng)絡(luò)安全。

http://www.cnki.net/kcms/detail/61.1450.TP.20161024.1117.074.html

TP

A

1673-629X(2016)11-0116-05

10.3969/j.issn.1673-629X.2016.11.026