黃春水,任艷麗,蔡建興

(上海大學通信與信息工程學院,上海 200444)

可驗證模指數(shù)批計算外包方案

黃春水,任艷麗,蔡建興

(上海大學通信與信息工程學院,上海 200444)

隨著云計算的發(fā)展,如何將一些耗時的計算任務(wù)安全地外包給不受信任的云服務(wù)器引起了人們的廣泛關(guān)注.目前的模指數(shù)運算外包方案大多基于兩個不可信的服務(wù)器,或者外包結(jié)果的可驗證概率不高.因此,使用隨機置換方法,提出了一個新的模指數(shù)批計算外包方案.模指數(shù)運算的底數(shù)和指數(shù)對于服務(wù)器都是保密的,并且用戶的可驗證概率接近于1.與已有方案相比,所提方案基于單個不可信服務(wù)器實現(xiàn)了輸入數(shù)據(jù)的隱私性,并提高了外包結(jié)果的可驗證概率.對所提方案進行了模擬實驗,測試結(jié)果表明外包方案極大地降低了用戶的計算代價.

云計算;外包方案;可驗證;模指數(shù)運算

隨著云計算[1]的興起,外包計算引起了人們廣泛的關(guān)注.通過外包計算,計算能力有限的客戶可以將任務(wù)外包給云服務(wù)器,這將為那些資源受限的設(shè)備節(jié)省大量的計算時間.同時,外包計算也面臨著許多挑戰(zhàn)[2-3],對安全性有很高的要求.云服務(wù)器并不是完全可信的,有可能存在泄露用戶的信息,或故意返回錯誤結(jié)果的情況,而可驗證計算(Verifiable Computation,VC)[4]方案很好地解決了這個問題.通過可驗證計算方案,用戶的信息都是對服務(wù)器保密的,并且服務(wù)器返回的任何錯誤結(jié)果都將不能通過驗證.

模指數(shù)運算是密碼系統(tǒng)中最常見的、最為耗時的運算之一.許多公鑰加密、數(shù)字簽名方案[5]需要用到模指數(shù)運算,研究如何實現(xiàn)模指數(shù)安全外包計算具有重要的現(xiàn)實意義.文獻[6]定義了第一個外包計算安全模型,并且基于兩個不可信的服務(wù)器,提出了單個模指數(shù)運算外包算法.文獻[7]提出了新的模指數(shù)運算外包方案,在計算效率與可驗證率方面都要優(yōu)于文獻[6]的.盡管文獻[6-7]中的方案實現(xiàn)了指數(shù)與底數(shù)的隱私性,但它們都需要進行大量復雜的預計算操作,效率不高,并且遇到惡意的服務(wù)器時,用戶檢測出錯誤的概率也都不是很高,文獻[6-7]的可驗證率分別為1/2、2/3.文獻[8]提出了多個模指數(shù)相乘的外包計算方案,與文獻[6-7]比,文獻[8]只用了一個服務(wù)器,也同時實現(xiàn)了指數(shù)與底數(shù)的隱私.但是,由于文獻[8]的方案是針對多個模指數(shù)相乘的外包計算方案,在單個模指數(shù)外包方面效率遠低于文獻[6-7]的,并且遇到惡意的服務(wù)器時,文獻[8]的可驗證率也僅有1/2.文獻[9]提出了基于單個服務(wù)器的批量模指數(shù)外包方案,與文獻[6-8]相比,文獻[9]的方案不需要復雜的預計算操作,因此在批量外包計算模指數(shù)方面效率更高,且可驗證概率接近于1.但是,文獻[9]的方案在隱私性方面有明顯的缺陷,不能同時實現(xiàn)指數(shù)和底數(shù)的隱私性.

筆者使用隨機置換方法,提出了一個新的模指數(shù)批計算外包方案.方案基于單個服務(wù)器,同時實現(xiàn)了底數(shù)和指數(shù)的隱私性.當服務(wù)器不誠實時,外包用戶能以接近于1的概率檢測到錯誤.與同類方案相比,筆者提出的方案僅需少量的預計算操作,效率優(yōu)于文獻[6-8]中的方案,稍遜于文獻[9]中的方案.但是與文獻[9]相比,筆者提出的方案同時實現(xiàn)了指數(shù)和底數(shù)的隱私性,安全性高于文獻[9]中的方案.

1　筆者提出的方案

在筆者提出的方案中,用到了一個被稱為Rand[6]的子程序,用于產(chǎn)生隨機數(shù)對.Rand子程序的輸入是素數(shù)p、q,底數(shù),且滿足q|p-1,輸出(a,gamod p),其中.目前,實現(xiàn)這一Rand子程序有兩種方式:一種方式是預先使用一個可信任的服務(wù)器,產(chǎn)生形如(a,gamod p)的隨機數(shù)對組成表,然后將這張表加載到客戶端T的內(nèi)存中去,每次調(diào)用Rand子程序,T就從表中隨機取出一個隨機數(shù)對,這種方式因此被稱為查表法.另一種就是用EBPV發(fā)生器[10]產(chǎn)生獨立的隨機數(shù)對,這種方式可以抵擋敵手自適應的攻擊,一個n比特的指數(shù)運行的時間復雜度為O(log2n).

1.1可驗證模指數(shù)計算方案

可驗證模指數(shù)計算方案是一個基于可信的客戶端T與不可信的服務(wù)器端U的雙方協(xié)議.T提供底數(shù)u和指數(shù)x作為輸入,經(jīng)盲化操作后,再發(fā)送給U.最后,U返回計算結(jié)果和一個驗證值.用戶利用服務(wù)器返回的驗證值驗證服務(wù)器返回的計算結(jié)果的正確性.一般的可驗證模指數(shù)計算方案都包含3個算法:

(1)(σu,σx)←Prob Gen(x,τ,u).輸入指數(shù)x、秘密輸入τ和底數(shù)u,輸出盲化后的指數(shù)σx和盲化后的底數(shù)σu.

(2)σy←Com pute(σu,σx).輸入σx和σu,輸出盲化后的模指數(shù)計算結(jié)果σy.

(3){y,⊥}←Verify(σy,τ).輸入盲化后的模指數(shù)計算結(jié)果σy,完成正確性證明.若驗證結(jié)果正確,輸出計算結(jié)果y=ux;否則,輸出⊥.

1.2可驗證模指數(shù)批計算外包方案

可驗證模指數(shù)批計算外包算法是在一個不可信的服務(wù)器上實現(xiàn)的.輸入輸出,其中p、q是兩個大素數(shù),且滿足q|p-1.筆者提出的外包方案包含3個子算法,如下所示.

算法1 Prob Gen((x1,x2,…,xt),τ,u).

T調(diào)用Rand子程序,產(chǎn)生3個隨機數(shù)對(α,gα),(β,gβ),(a,ga),然后從中選取兩個隨機數(shù)b,b′.定義τ={(α,gα),(β,gβ),(a,ga),b,b′},v=gαmod p,μ=gβmod p,γ=gamod p.

然后,客戶端T利用秘密輸入τ對底數(shù)u與指數(shù)xi進行盲化處理.

最后輸出盲化后的指數(shù)σx={A,D}和盲化后的底數(shù)σu={g,w}.將(σu,σx)={(D,g,p),(A,w,p)}發(fā)給服務(wù)器.

算法2 Compute(σu,σx).

U利用T發(fā)過來的σu、σx計算出結(jié)果σy,并將它發(fā)回給客戶端.

利用T傳過來的(D,g,p),(A,w,p),U完成計算并返回對應的查詢結(jié)果:

算法3 Verify(σy,τ).

T接收到從服務(wù)器U傳過來的σy集合后,進行如下操作來驗證U返回的計算結(jié)果的有效性:

(1)T從σy中取出,其中,1≤k≤t.

(2)T從σy中取出,其中,1≤k≤t.

如果對于所有的i∈[1,t],上面的驗證等式(1)都成立,那么輸出;否則,輸出⊥.

2　方案分析

使用與文獻[6-7]相同的安全定義,從理論上證明筆者所提方案的正確性和安全性.受篇幅限制,相關(guān)安全定義不再給出,具體安全定義和模型見文獻[6-7].

2.1正確性

通過以下引理證明方案的正確性,即只要服務(wù)器是誠實的,通過以上筆者提出的方案總能夠得到正確的計算結(jié)果y=uxi且式(1)成立.

引理1 如果服務(wù)器是誠實的,則y=uxi且式(1)成立.

由式(2)可知,只要服務(wù)器是誠實的,則式(1)成立.

2.2安全性

通過以下兩個引理證明方案的安全性.

引理2 基于單個不可信服務(wù)器模型,算法(T,U)是外包算法BExp的λ安全外包的實現(xiàn).其中,輸入(x1,x2,…,xt;u)可能是可信任的秘密輸入,或是可信任的受保護的輸入,或是敵手的受保護的輸入.

證明 首先,證明EVIEWreal～EVIEWideal.如果輸入{(xi;u):1≤i≤t}不是可信的秘密輸入,E總能知道輸入信息.顯然,這種情況下模擬器S1執(zhí)行過程將與實際的環(huán)境相同.因此,只需考慮輸入{(xi;u): 1≤i≤t}是可信任的秘密輸入的情況.

在理想的實驗環(huán)境中,模擬器S1執(zhí)行過程如下:當接收到第i個輸入時,S1忽略它們,并向U′提交4t個形如的查詢操作.然后,S1隨機檢測2t個輸出:如果有一個錯誤被檢測出來,輸出“error”,indi=1(ind表示是否發(fā)現(xiàn)錯誤,如果發(fā)現(xiàn)則為1;否則為零);如果沒有錯誤被檢測出來,S1繼續(xù)檢查其他2t個輸出;如果所有的輸出都通過檢測,S1輸出,indi=0;否則,S1挑選t個隨機數(shù)z1,z2,…,zt,并輸出.在上面的所有情況中,模擬器S1都要保存它自己的所有狀態(tài).U′的輸入分布在實際和理想的實驗環(huán)境中,在計算上都是不可區(qū)分的.在理想實驗環(huán)境中,所有的輸入都是隨機選取的.在實際實驗環(huán)境中,由于T在向U提交查詢請求操作之前,所有指數(shù)已經(jīng)過一個映射函數(shù)加密擾亂,因此兩次查詢操作的過程是獨立隨機的,在計算上不可區(qū)分.

接下來證明UVIEWreal～UVIEWideal.如果輸入{(xi;u):1≤i≤t}不是可信的秘密輸入、可信的受保護的輸入和敵手的受保護的輸入時,U′總能知道輸入信息.顯然,這種情況下模擬器S2執(zhí)行過程將與實際的環(huán)境相同.因此,只需考慮輸入是可信的秘密輸入、可信的受保護的輸入和敵手的受保護的輸入時的情況.

在理想的實驗環(huán)境中,模擬器S2執(zhí)行過程如下:當接收到第i個輸入時,S2忽略它們,并向U′提交4t個形如的查詢操作,然后保存自己和的所有狀態(tài).同上面證明的過程一樣,U′的輸入分布在實際和理想的實驗環(huán)境中在計算上都是不可區(qū)分的.因此,盡管通過indi的值E能夠很容易地區(qū)別真實環(huán)境和理想環(huán)境,但是E不能把這一信息傳遞給U′.所以,有UVIEWreal～UVIEWideal成立.

引理3 在單個服務(wù)器惡意模型中,算法(T,U)是外包算法BExp的(O((6t+log2n)(nt)),(4t2-1)(4t2),λ)安全外包的實現(xiàn).

證明 用平方乘算法計算一個模指數(shù)形如uamod p,大概需要1.5n次的模乘運算,其中n表示指數(shù)a的比特長度.因此,用平方乘算法直接計算t個指數(shù)大概需要進行1.5nt次模乘運算.而用BExp算法計算t個指數(shù),需要1次模逆運算,6t+1次模乘運算.另外,還調(diào)用了3次Rand子程序.在1.1節(jié)中提到過如果使用EBPV發(fā)生器來實現(xiàn)Rand子程序,那么一個n比特的指數(shù)運行的時間復雜度為O(log2n).所以,算法BExp的時間復雜度為O((6t+log2n)(nt)).

在算法2中,用戶T向服務(wù)器提交了兩次查詢操作,每次計算的模指數(shù)長度為2t.這兩次查詢的結(jié)果影響著算法3的最終驗證結(jié)果.假設(shè)某次外包計算過程中U向T返回了一個錯誤的結(jié)果,要想通過算法3的驗證使用戶T接受這個錯誤的結(jié)果,U必須選取2個合適的數(shù)字,代替算法2產(chǎn)生的兩個結(jié)果集合中的某兩個數(shù).但由于算法2中兩次查詢操作在計算上是不可區(qū)分的,并且查詢操作前輸入已經(jīng)通過映射函數(shù)擾亂,所以替換成功的概率為1/(4t2).即U給T返回了一個錯誤的計算結(jié)果,最終被T檢測出來的概率為(4t2-1)(4t2)(在下面的3.2節(jié)實驗中,t取的都是10 00以上,可驗證率接近于1).所以,算法BExp的可驗證率為(4t2-1)(4t2).

綜上所述,可以說算法(T,U)是外包算法BExp的(O((6t+log2n)(nt)),(4t2-1)(4t2),λ)安全外包的實現(xiàn).

3　性能分析

3.1理論分析

假設(shè)將t個底數(shù)相同、指數(shù)不同的模指數(shù)外包給云服務(wù)器,統(tǒng)計出在不同方案中,客戶T需要做的模乘運算次數(shù)、模逆運算次數(shù)、查詢服務(wù)器的次數(shù)、隱私性狀況、可驗證率以及使用的服務(wù)器數(shù)量,如表1所示,其中m表示文獻[4]中選取的隨機數(shù)個數(shù),m＞100.

表1　模指數(shù)運算外包方案比較

根據(jù)表1,同文獻[6-7]相比,筆者在實現(xiàn)用戶的指數(shù)、底數(shù)都對服務(wù)器保密的同時,效率上有明顯的提高.所做的模乘運算、模逆運算和查詢服務(wù)器的次數(shù)都要少于文獻[6-7]中的.隨著外包模指數(shù)數(shù)量增多(t越大),這種效率的提升越明顯.并且,筆者只用了一個服務(wù)器,可驗證率也要高于文獻[6-7]的.文獻[8]雖然也只用了一個服務(wù)器并能夠?qū)崿F(xiàn)完全隱私,但在效率和可驗證率上都不及筆者提出的方案.與文獻[9]相比,盡管文獻[9]的可驗證率和服務(wù)器個數(shù)都與筆者提出的方案相同,甚至模乘運算、模逆運算和查詢服務(wù)器的次數(shù)比筆者提出的方案少,效率方面比筆者提出的方案略高,但是,文獻[9]不能實現(xiàn)用戶的指數(shù)、底數(shù)同時對服務(wù)器保密,安全性方面不如筆者提出的方案.

3.2實驗分析

首先,對筆者提出的方案進行實驗,統(tǒng)計出外包不同數(shù)量的模指數(shù)時,用戶端所需要的時間曲線圖(如圖1所示).由圖1可知,采用筆者提出的外包方案,用戶通過外包方案計算出結(jié)果的時間遠小于用戶直接計算的時間.并且,隨著待外包模指數(shù)個數(shù)的增多,兩者之間的時間差值增大,筆者提出的方案在大批量模指數(shù)外包方面的高效率特性更突出.

圖1　外包模指數(shù)方案實驗結(jié)果圖

接著,分別對文獻[7-9]的外包方案進行實驗.一共測試了9組不同個數(shù)的模指數(shù),統(tǒng)計用戶端所需要的時間如表2所示.

表2　4種外包方案的計算時間　ms

根據(jù)表2,可以得出與3.1節(jié)相同的結(jié)論.在外包的模指數(shù)個數(shù)相同的情況下,文獻[8]中方案所用的時間明顯高于其他3種方案的,這是由于文獻[8]中的方案主要是用于外包多個模指數(shù)乘法運算,所以在單個模指數(shù)外包上效率很低.筆者提出方案的時間介于文獻[7,9]中方案之間,這也和3.1節(jié)方案分析的結(jié)論吻合.在外包的模指數(shù)個數(shù)相同情況下,與文獻[7]中的方案相比,筆者提出的方案時間較少,這說明筆者提出的方案效率高于文獻[7]的.隨著外包的模指數(shù)個數(shù)增多,文獻[7]中的方案和筆者提出方案的時間差值增大,這意味著在實現(xiàn)大批量的模指數(shù)外包上,筆者提出的方案效率的優(yōu)勢更明顯.為了實現(xiàn)用戶提供的指數(shù)、底數(shù)都對服務(wù)器保密,提高算法的安全性,筆者提出的方案進行了少量的預計算操作.犧牲用戶少量時間換取了用戶安全性的提高,這就導致了筆者提出方案的效率比文獻[9]的低.

4　結(jié)束語

基于單個不可信服務(wù)器,提出了一種新的模指數(shù)批外包計算方案.與目前已知的模指數(shù)外包方案相比,筆者提出的方案僅需付出少量的預計算操作代價,便能夠同時實現(xiàn)指數(shù)和底數(shù)的隱私性.在數(shù)據(jù)隱私的前提下,用戶實現(xiàn)外包的效率高于其他算法.另外,外包結(jié)果的可驗證概率較其他方案也有明顯優(yōu)勢,如果服務(wù)器不誠實,用戶檢測出錯誤的概率接近于1.后續(xù)需改進的工作是:在保證用戶外包效率不降低的情況下,盡可能地降低服務(wù)器的工作量.

[1]CHAPMAN C,EMMERICH W,MARQUEZ F G,et al.Software Architecture Definition for On-demand Cloud Provisioning[J].Cluster Computing,2012,15(2):79-100.

[2]REN K,WANG C,WANG Q.Security Challenges for the Public Cloud[J].IEEE Internet Computing,2012,16(1): 69-73.

[3]MEZGAR I,RAUSCHECKER U.The Challenge of Networked Enterprises for Cloud Computing Interoperability[J]. Computers in Industry,2014,65(4):657-674.

[4]GENNARO R,GENTRY C,PARNO B.Non-interactive Verifiable Computing:Outsourcing Computation to Untrusted Workers[C]//Lecture Notes in Computer Science:6223.Berlin:Springer,2010:465-482.

[5]江明明,胡予濮,王保倉,等.格上的代理重簽名方案[J].西安電子科技大學學報,2014,41(2):20-24. JIANG Mingming,HU Yupu,WANG Baocang,et al.Proxy Re-signature Scheme over the Lattice[J].Journal of Xidian University,2014,41(2):20-24.

[6]HOHENBERGER S,LYSYANSKAYA A.How to Securely Outsource Cryptographic Computations[C]//Lecture Notes in Computer Science:3378.Berlin:Springer,2005:264-282.

[7]CHEN X,LI J,MA J,et al.New Algorithms for Secure Outsourcing of Modular Exponentiations[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(9),2386-2396.

[8]WANG Y,WU Q,WONG D S,et al.Securely Outsourcing Exponentiations with Single Untrusted Program for Cloud Storage[C]//The 19th European Symposium on Research in Computer Security.Berlin:Springer,2014:326-343.

[9]MA X,LI J,ZHANG F.Outsourcing Computation of Modular Exponentiations in Cloud Computing[J].Cluster Computing,2013,16(4):787-796.

[10]NGUYEN P Q,SHPARLINSKI I E,STERN J.Distribution of Modular Sums and the Security of the Server Aided Exponentiation[C]//Progress in Computer Science and Applied Logic:20.Witzerland:Bikhauser Verlag AG,2001: 331-342.

(編輯:郭 華)

Verifiable outsourcing scheme for batch modular exponentiations

HUANG Chunshui,REN Yanli,CAI Jianxing
(School of Communication and Information Engineering,Shanghai Univ.,Shanghai 200444,China)

With the development of cloud computing,more and more people focus on how to outsource the expensive computations to the untrusted cloud servers.Currently,the outsourcing schemes for modular exponentiations are mostly based on two untrusted servers,or the checkability is very small.We propose a new outsourcing algorithm for batch modular exponentiations by using the random permutation.The exponent and the base are both private for the server,and the outsourcer can detect the error with probability close to 1.Compared with the previous algorithms,the proposed one is based on a single server, which realizes the privacy of inputs and increases the checkability of the outsourcing result.Finally,we simulate the proposed algorithm,and the experimental result shows that it can greatly reduce the computational cost for the outsourcer.

cloud computing;outsourcing algorithm;verifiable;modular exponentiation

TP309

A

1001-2400(2016)04-0135-06

10.3969/j.issn.1001-2400.2016.04.024

2015-04-14 網(wǎng)絡(luò)出版時間：2015-10-21

國家自然科學基金資助項目(61202367);上海市自然科學基金資助項目(12ZR1443700);上海市教委創(chuàng)新基金資助項目(14YZ020)

黃春水(1991-),男,上海大學碩士研究生,E-mail:chunshui_h@163.com.

網(wǎng)絡(luò)出版地址：http://www.cnki.net/kcms/detail/61.1076.TN.20151021.1046.048.html