單服務器模型下雙線性運算外包協議設計

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

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

單服務器模型下雙線性運算外包協議設計

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

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

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

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

1 概 述

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

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

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

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

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

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

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

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

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

2 基礎知識

2.1 雙線性對

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

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

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

2.2 安全雙線性對運算外包協議

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

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

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

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

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

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

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

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

3 方案的安全分析

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

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

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

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

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

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

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發送雙線性對的輸入(ι1,ι2)給服務器1，而服務器1返回響應結果e(ι1,ι2)。

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

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

安全分析如下：

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

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

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

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

4 單服務器模型下外包協議的設計

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

4.1 新方案設計

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

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

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

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

否則，拒絕服務器端返回的結果，并輸出“錯誤”。

4.2 性能比較和安全性分析

(1)性能比較。

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

表1 計算開銷比較

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

(2)安全分析。

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

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

證明：

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

α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

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

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

(1)

假設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 結束語

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

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

[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

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

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

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