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

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

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

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

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

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

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

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

1 問題描述

1.1 系統(tǒng)模型

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

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

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

Fig. 1 System model圖1 系統(tǒng)模型

1.2 安全定義

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

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

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

3) Compute((αj,βj)).輸入由Mask算法分割產(chǎn)生的隨機數(shù)對(αj,βj)，PCS輸出相應(yīng)的計算結(jié)果σy.

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

2 冪指數(shù)運算的安全外包計算方案

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

2.1 子程序Rand

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

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

2.2 冪指數(shù)外包方案

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

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

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

(1)

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

(2)

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

(3)

其中，w2=uv2.

(4)

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

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

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

(5)

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

(6)

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

3 安全分析

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

3.1 正確性

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

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

(7)

(8)

證畢.

3.2 安全性

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

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

證畢.

當(dāng)外包用戶User收到服務(wù)器PCS返回的計算結(jié)果后，User能夠通過驗證

(9)

是否成立來判斷服務(wù)器PCS是否產(chǎn)生了正確的響應(yīng).

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

證畢.

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

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

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

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

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

證畢.

4 性能分析

本節(jié)通過理論分析和實驗?zāi)M2方面對設(shè)計的冪指數(shù)運算外包方案GEXP的性能進行分析.

4.1 理論分析

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

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

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

4.2 實驗?zāi)M

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

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

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

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

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

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

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

5 應(yīng) 用

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

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

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

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

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

① 代理產(chǎn)生一個隨機數(shù)r∈并將該隨機數(shù)發(fā)送給用戶uA；

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

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

④ 代理恢復(fù)重簽密鑰rkA→B=ba∈

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

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

(10)

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

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

(11)

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

6 結(jié)束語

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