基于單服務器的群上冪指數安全外包計算方案

李 帥 付安民 蘇 铓 陳珍珠 孫銀霞

1(南京理工大學計算機科學與工程學院 南京 210094) 2(貴州大學貴州省公共大數據重點實驗室 貴陽 550025) 3 (南京師范大學計算機科學與技術學院 南京 210023) (1373975356@qq.com)

云計算是一種新興的計算模式，它將計算任務分布在大量計算機構成的資源池上，使各種應用系統能夠根據需要獲取計算力、存儲空間和信息服務.隨著云計算的快速發展，出現了一種新的計算模式：外包計算.外包計算允許使用資源受限設備(如智能手機和平板電腦)的用戶將復雜計算任務外包給云服務器，從而節省計算時間.

但由于云服務器并不是完全可信的，因此也遇到一些新的安全問題和挑戰[1-4]：1)用戶數據經常會包含一些隱私信息(如個人醫療記錄、個人收入狀況和家庭成員信息等)，而這些信息用戶并不希望泄露給云服務器.因此，如何保護用戶敏感的輸入/輸出信息是數據外包計算過程中的首要安全挑戰.2)外包計算通常需要大量的計算資源，云服務器可能為了節省計算資源而“偷懶”，并且軟件上的漏洞或者來自敵手的惡意攻擊都可能會影響云服務器計算結果的正確性.因此，如何有效驗證云服務器返回計算結果的正確性是數據外包計算過程中另一個安全挑戰.

在密碼學領域，將昂貴的計算外包給不完全可信的設備受到廣泛研究[5-14].Chaum等人[5]首次提出了“wallets with observers”的概念，在每次執行任務時允許用戶在自己的設備上安裝一塊硬件來執行計算.Hohenberger等人[6]進一步給出了外包計算的安全定義和安全模型，并基于不可信的雙服務器模型，提出了首個冪指數運算安全外包方案.但可惜該方案對服務器返回的計算結果的可驗證概率僅為1/2.陳曉峰等人[7]在Hohenberger方案的基礎上，基于雙服務器模型，提出了一個新的冪指數運算安全外包方案，其對服務器返回的計算結果的可驗證概率提高到了2/3.最近，任艷麗等人[13]提出了一個新的基于雙服務器模型的冪指數運算安全外包方案，其對服務器返回的計算結果的可驗證概率達到了1.值得注意的是，文獻[6-7,13]方案中都是基于不可信的雙服務器模型，并且它們都要求雙服務器之間不能進行共謀.Dijk等人[9]首次提出了基于單個不可信服務器的冪指數運算外包計算方案，但該方案在外包計算過程中服務器能夠獲取到指數運算中的底數，因此，該方案并不能有效實現數據的隱私保護.

在冪指數外包計算領域，特別是基于不可信的雙服務器模型方面，學者提出了大量可驗證計算外包方案，但現有方案大多關注的是數域上的冪指數運算外包，而鮮有關注群域上的冪指數運算.群域上的冪指數運算在基于身份簽名[15-16]、盲簽名[17]等領域有廣泛運用.特別是現有的云存儲可證明的數據持有[18-24](provable data possession, PDP)方案大都需要涉及到大量群上的冪指數運算操作.因此，最近Wang等人[8]提出了一個群上的冪指數運算安全外包方案，該方案基于單個不可信服務器，能夠有效實現底數和指數的隱私保護，但可惜該方案對服務器返回的計算結果的可驗證概率僅為1/2.

本文基于單服務器模型，提出了一個新的群域上的冪指數運算安全外包方案GEXP(outsourcing power exponent on a group field)，能夠有效避免雙服務器模型存在的共謀攻擊問題.GEXP通過使用一種新的數學分割方法，用戶可以將原始數據安全分割成隨機片的形式，從而很好地實現了數據外包中的隱私保護.同時，與已有方案相比，GEXP能夠實現對外包計算結果的可完全驗證.此外，針對云存儲數據完整性保護方案中普遍涉及到大量群域上的冪指數運算問題，本文還給出了方案GEXP在一個典型的云端群組數據完整性驗證方案Panda中的具體應用.

1 問題描述

1.1 系統模型

一個安全的外包算法包括2個不同的實體，如圖1所示.首先，用戶User調用子程序RandG產生盲化隨機對；然后，User借助子程序產生的隨機對實現了對原始數據的分割隱藏，將盲化后的隨機數對上傳到公共云服務器(public cloud server, PCS)；PCS利用這些盲化隨機數對進行計算，并將計算后結果返回給User；最終，User驗證PCS返回的計算結果的正確性.外包算法中涉到的2個實體的描述如下：

1) 外包用戶(User).有很多復雜的計算任務需要去處理,但缺乏足夠的計算資源.

2) 公共云服務器(PCS).由公共云服務提供者進行管理.海量的存儲空間和強大的計算能力為其處理用戶的計算任務提供了強有力的保證.但是，通常情況下公共云服務器并不是完全可信的.

Fig. 1 System model圖1 系統模型

1.2 安全定義

定義1. 安全的冪指數外包算法.該算法由4個子算法組成：

1) SetUp(g).使用變量g來初始化子程序RandG，用戶調用RandG生成一些盲化隨機數對(a，ga).

2) Mask((d，u)，(a，ga)).輸入原始數據(d，u)和盲化對(a，ga).使用邏輯分割算法將原始數據分割成隨機片的形式.這些隨機片由2部分組成：①需要PCS計算的盲化后的隨機數對(αj,βj);②用來驗證最終計算結果正確性的秘密值s.

3) Compute((αj,βj)).輸入由Mask算法分割產生的隨機數對(αj,βj)，PCS輸出相應的計算結果σy.

4) Verify(σy,s).輸入PCS返回的計算結果σy和秘密值s來對結果進行驗證.如果驗證沒有通過，用戶輸出“error”;否則，User恢復最終的計算結果ud.

2 冪指數運算的安全外包計算方案

本文提出了一個基于單個不可信服務器模型的群上冪指數運算的安全外包方案GEXP，在方案GEXP中，用戶User借助子程序RandG實現了將指數運算安全外包給云服務器PCS，所提出的算法能夠確保敵手A在整個外包計算的過程中不能獲取到任何關于輸入和輸出的隱私信息.我們首先假設p是一個大素數，G是一個階數為p的循環群.方案GEXP的輸入為u∈G和d∈p，輸出為ud.

2.1 子程序Rand

在冪指數外包方案中，普遍需要使用一個稱為Rand的子程序來生成隨機盲化對[6-8].Rand的輸入是一個素數p和一個底數g∈(也有可能是其他的數值)，每次調用后輸出一個具有(a,gamodp)形式的隨機的、獨立的盲化對，其中a∈為了提高安全性，Rand的輸出分布應該與真正隨機的情形是計算上不可區分的.有2種方式可以用來實現這個子程序：1)檢查表方法；2)預處理技術[10].

本文中我們使用了和文獻[8]類似的擴展子程序RandG，其輸入是一個p階循環群G的生成元g，其中p是一個大素數，也有可能是一些其他的數值，每次調用的輸出是一個具有(a,ga)形式的隨機的、獨立的盲化對，其中a∈

2.2 冪指數外包方案

我們提出的冪指數運算安全外包方案由4個子算法組成：

1) SetUp(g).用戶User首先使用變量g來初始化子程序RandG，然后5次調用子程序RandG生成5組隨機盲化對(α,gα)，(β,gβ)，(λ,gλ)，(η,gη)，(t,gt)，并定義v1=gα，v2=gλ.

2) Mask((u,d),(a,ga)).子算法Mask是用來對原始數據u和d進行邏輯分割處理，將原始數據分割成隨機片的形式.使得服務器PCS在計算過程中不能獲取到任何輸入輸出的敏感信息.第1次邏輯分割：

(1)

其中，w1=uv1.第2次邏輯分割：

(2)

其中，β=αd-rmodp和l1=d-k1t1modp.下面對ud進行一組類似的邏輯分割：

(3)

其中，w2=uv2.

(4)

其中,η=λd-r′ modp和l2=d-k2t2modp.

通過上述的邏輯分割，底數u已經由隨機數對(v1,w1)和(v2,w2)實現了隱藏，指數d則由隨機值l1,k1,t1和l2,k2,t2來進行隱藏處理.

3) Compute((αj,βj)).用戶User上傳盲化后的數據對(rt,gt),(r′t,gt),(l1,w1),(l2,w2),(k1,w1),(k2,w2)，云服務器PCS計算的指數運算并將相應的計算結果σy={gr,gr′,,,,}返回給用戶User：

(5)

4) Verify((σy,s)).當收到云服務器PCS返回的計算結果σy后，用戶User利用秘密值s(t1和t2)來驗證云服務器PCS返回計算結果的正確性，即驗證

(6)

值得注意的是，為了進一步提高輸入的安全性，邏輯分割中使用的隨機盲化因子t1,t2通常至少選取64 b長度[8].

3 安全分析

本節我們從正確性和安全性2個方面來對設計的冪指數外包方案GEXP進行分析和證明.由于篇幅限制，本文沒有給出完整的冪指數外包計算安全定義與模型，具體請參閱文獻[6].

3.1 正確性

定理1. 基于單個不可信的服務器模型，算法(T,U)是方案GEXP的一個正確的實現，其中，輸入(d,u)可能是誠實的、秘密的輸入，或是誠實的、受保護的輸入，或是惡意的、受保護的輸入.

證明. 如果云服務器PCS是誠實的，用戶User可以執行計算：

(7)

(8)

證畢.

3.2 安全性

定理2. 基于單個不可信的服務器模型，算法(T,U)是方案GEXP的一個安全外包實現，其中輸入(d,u)可能是誠實的、秘密的輸入，或是誠實的、受保護的輸入，或是惡意的、受保護的輸入.

證明UVIEWreal～UVIEWideal.如果輸入(d,u)不是誠實的秘密的輸入、誠實的受保護的輸入和惡意的受保護的輸入情形時，U′總能獲取到輸入信息.顯然，在這種情況下，模擬器S2的執行過程將與實際的實驗中相同.因此，我們僅僅需要考慮輸入是誠實地秘密的、誠實地受保護的和惡意地受保護的情形.在理想的實驗環境中，模擬器S2的執行過程如下：當接收了第i輪的輸入后，S2以(αj,βj)的形式向U′進行了6次隨機詢問；然后S2保存它自己的所有狀態以及U′的狀態.同上面證明EVIEWireal～EVIEWiideal的過程類似，在實際實驗中U′的輸入和理想實驗中由S2隨機選擇的輸入是計算上不可區分的.盡管E能夠區分出實際實驗和理想實驗這2種不同的情形，但是E卻不會將這些信息傳遞給U′.因此，我們可以得到UVIEWreal～UVIEWideal.綜上所述，算法(T,U)是方案GEXP的一個安全外包實現.

證畢.

當外包用戶User收到服務器PCS返回的計算結果后，User能夠通過驗證

(9)

是否成立來判斷服務器PCS是否產生了正確的響應.

如果等式不成立，表明PCS產生了錯誤的響應，User能夠以100%的概率驗證服務器返回的計算結果的正確性，因此算法GEXP的可驗證概率為1.

證畢.

定理4.基于單個不可信的服務器模型，方案GEXP滿足輸入u，d和輸出ud的隱私性.

證明. 在用戶User請求服務器PCS的過程中，敵手能夠獲取到與底數u相關的信息為w1和w2，其中w1=uv1，w2=uv2，v1=gα，v2=gλ.v1和v2分別是子程序RandG產生的盲化隨機對(形如(a,ga)隨機、獨立盲化對)中的一部分.底數u則由隨機數v1，v2實現了隱藏.此外，用戶User請求服務器PCS是以一種隨機的方式進行的(請求計算數據對的順序是任意的).因此，敵手不能獲取到底數u的信息.

在我們的外包方案中，指數d可以被拆分為d=l1+k1t1，d=l2+k2t2.d由隨機數t1，t2實現了隱藏，其中t1，t2長度通常至少是64 b.敵手通過猜測t1，t2恢復出d的概率是可以忽略的.因此，敵手同樣不能獲取到指數d的信息.

敵手可以獲取到用戶User請求服務器的PCS的數據對，但是通過這些數據并不能直接計算出最終的結果ud，并且已經證明了敵手不能獲取到底數u和指數d的信息，也就無法通過u，d計算出ud.因此，敵手也不能獲取輸出ud的信息.

綜上所述，方案GEXP滿足輸入u，d和輸出ud的隱私性.

證畢.

4 性能分析

本節通過理論分析和實驗模擬2方面對設計的冪指數運算外包方案GEXP的性能進行分析.

4.1 理論分析

我們將本文提出的方案GEXP分別與陳曉峰等人[7]、Wang等人[8]和任艷麗等人[13]提出的代表性冪指數外包方案進行了對比分析，其中Multi-plications表示乘法運算，Inversions表示求逆運算，Invoke(Rand)表示調用Rand次數，Invoke(PCS)表示請求服務器次數.表1給出了方案效率和結果可驗證概率的對比.

Table 1 Comparison of Exponentiation Outsourcing Schemes表1 指數安全外包方案對比

從表1可以看出，與文獻[7-8]相比，方案GEXP在外包計算結果的可驗證概率上有了很大的提升.在方案GEXP中，外包用戶能夠以100%的概率檢測出服務器的不端行為，完全避免被服務器欺騙.雖然文獻[7,13]在Multiplications方面要比方案GEXP和文獻[8]小，其中文獻[13]的可驗證概率也達到了100%.但是文獻[7,13]都是基于雙服務器模型，可能遭受共謀攻擊.此外，文獻[8]與方案GEXP的Multiplications在開銷方面受x，t1，t2等變量的影響.隨著x，t1，t2等變量值的增大，用戶的計算開銷也會隨之增大(在4.2節實驗中會進一步分析).但與此同時，方案的安全性也會相應提高(d=c+bx，d=l1+k1t1，d=l2+k2t2)，因為此時敵手更難猜測出d.

4.2 實驗模擬

為了具體評估方案的性能，我們對本文提出的方案GEXP和文獻[8]中的Exp方案進行了實驗模擬.方案GEXP需要使用2臺機器進行模擬，用戶和服務器分別使用Intel Core i5 processors(1.20 GHz和2 GB內存)和Intel Core i5 processors(3.20 GHz和8 GB內存)進行模擬.使用的編程語言為Java語言.

圖2給出了使用方案GEXP和直接計算群上的冪指數運算的時間開銷對比.從圖2中可以看出，方案GEXP的時間開銷要遠小于直接計算的時間開銷，能夠明顯提升資源受限用戶的計算處理能力.

Fig. 2 Simulation of time cost for two schemes圖2 2種方案的時間開銷統計圖

圖3給出了在底數長度固定和指數長度變化時，方案GEXP和直接計算的時間開銷對比.從圖3中我們可以看出，不借助外包算法直接計算群上的指數運算時，其時間開銷隨著指數長度的增加呈現線性增長.當使用本文提出的外包計算方案GEXP時，時間開銷會大幅度減小，并且時間開銷基本上是固定的，不會隨著指數長度的增加而增加.

Fig. 3 Time cost of ud (fixed base-variable exponent)圖3 ud的時間開銷統計圖(底數固定、指數可變)

為了進一步評估我們所提出方案的性能，我們與同是基于單服務器模型的文獻[8]中的Exp方案進行了實驗對比分析.圖4給出了分別使用方案GEXP、文獻[8]中的Exp方案以及直接計算群上的冪指數運算的時間開銷對比.從圖4可以看出，方案GEXP和文獻[8]中Exp方案的時間開銷要遠小于直接計算的時間開銷，方案GEXP的時間開銷要比文獻[8]中Exp方案的稍大一些.這是因為方案GEXP犧牲用戶少量時間換取了驗證概率的大幅提升.此外，從圖4我們可以看出,隨著參數x，t1，t2的增大，方案GEXP和文獻[8]中Exp方案的用戶計算開銷隨之增大，但與此同時，方案的安全性也會提高.

Fig. 4 Simulation for different schemes圖4 不同方案時間開銷對比圖

5 應 用

隨著云計算的快速發展，企業用戶和個人可以更經濟、更方便地使用云端提供的數據服務，包括數據存儲和數據共享等.但當用戶將數據上傳到云端后，他們失去了對數據的直接控制權，此時他們最關心的問題就是數據的完整性.可證明數據持有PDP是驗證云端數據完整性的關鍵技術，該技術可以允許一個驗證者去公開地驗證用戶存儲在云端數據的完整性.但現有PDP方案中普遍需要涉及到群上的冪指數運算這一費時操作.

因此，我們使用所提出的方案GEXP去安全外包王博洋等人[25]提出的云端群組數據完整性驗證方案Panda方案中的核心代理重簽名HAPS.我們所提出的HAPS安全外包算法由6個子算法組成：

1) Initialize.令G1和G2是2個p階循環群，g是G1的生成元，e:G1×G1→G2是一個雙線性映射，ω是G1的另一個生成元.(e,p,G1,G2,g,ω,H)是系統的公開參數，其中函數H:{0,1}*→G1.

2) KeyGen.給定系統的公開參數(e,p,G1,G2,g,ω,H)，用戶uA選擇一個隨機數a∈輸出公鑰pkA=ga，并保持私鑰skA=a私有.

3) ReKey.代理按照如下的方式生成重簽密鑰rkA→B：

① 代理產生一個隨機數r∈并將該隨機數發送給用戶uA；

② 用戶uA計算ra，并將計算后的結果發送給用戶uB，其中skA=a；

③ 用戶uB計算rba，并將計算后的結果發送給代理，其中skA=b；

④ 代理恢復重簽密鑰rkA→B=ba∈

4) Sign.給定私鑰skA=a、數據塊m∈p以及數據塊標識id，對于數據塊m上的簽名，用戶uA調用函數FGEXP，獲取并輸出：

σ=FGEXP(a,H(id)FGEXP(m,ω))=
FGEXP(a,H(id)ωm)=(H(id)ωm)a∈G1.

(10)

5) Resign.給定重簽密鑰rkA→B、公鑰pkA、簽名σ、數據塊m∈p以及數據塊標識id，代理核對如果驗證結果為0，代理輸出⊥；否則，代理調用函數FGEXP，獲得并輸出

σ′=σrkA→B=FGEXP(ba,σ)=
(H(id)ωm)a·ba=(H(id)ωm)b.

(11)

6) Verify.給定公鑰pkA、數據塊m、數據塊標識id以及簽名σ，驗證者調用函數FGEXP，獲取ωm=FGEXP(m,ω).如果e(σ,g)=e(H(id)ωm,pkA)成立，驗證者輸出1，否則輸出0.

6 結束語

在本文中，基于單個不可信服務器模型，我們提出了一個新的群域上的冪指數運算安全外包方案GEXP，能夠有效避免雙服務器模型存在的共謀攻擊問題.方案GEXP通過使用一種新的數學分割方法，用戶可以將原始數據安全地分割成隨機片的形式，從而保護了原始數據的隱私.與現有的方案相比，我們的方案GEXP在外包計算結果可驗證概率上有了顯著的提升，如果云服務器產生了任何不正確的響應，用戶能夠以100%的概率檢測出錯誤.最后，針對云存儲數據完整性保護方案中普遍涉及到大量群域上的冪指數運算問題，利用所提出的外包計算方案GEXP作為子程序實現了Panda方案的安全外包.