基于雙服務(wù)器模型的可公開驗(yàn)證多元多項(xiàng)式外包計算方案

羅小雙，楊曉元，李　聰，王緒安

(1.武警工程大學(xué) 密碼工程學(xué)院，西安 710086；　2.網(wǎng)絡(luò)與信息安全武警部隊(duì)重點(diǎn)實(shí)驗(yàn)室，西安 710086)(*通信作者電子郵箱yxyangyxyang@163.com)

0　引言

云計算技術(shù)成為互聯(lián)網(wǎng)時代必不可少的工具，逐漸滲透到日常生活的方方面面。由于云具有強(qiáng)大的計算能力和存儲能力[1]，計算能力較弱的用戶傾向于將復(fù)雜計算外包給云服務(wù)器來完成[2]，從而降低本地計算的復(fù)雜度、減少計算量，提高用戶的運(yùn)算效率。但是數(shù)據(jù)一旦外包給云來完成，不可避免地會帶來隱私泄露的安全問題。為了防止不可信云服務(wù)器泄露和濫用用戶的數(shù)據(jù)，用戶需要對交付給云服務(wù)器運(yùn)算的數(shù)據(jù)進(jìn)行加密或者盲化處理，以此來保證數(shù)據(jù)的隱私性和完整性；并且，用戶能夠?qū)υ品?wù)器返回的計算結(jié)果進(jìn)行驗(yàn)證，從而獲得正確的計算結(jié)果。

2010年歐洲密碼會議(CRYPTO 2010)上，Gennaro等[3]將外包計算[4]和驗(yàn)證技術(shù)結(jié)合起來，首次提出可驗(yàn)證計算(Verifiable Computation)的概念，運(yùn)用混淆電路和全同態(tài)加密構(gòu)造了一個可驗(yàn)證計算的外包方案，該方案能夠保證輸入與輸出的隱私性，但是只能做到私有驗(yàn)證。2011年，Benabbas等[5]提出了選擇明文攻擊(Chosen Plaintext Attack, CPA)安全的多項(xiàng)式外包計算方案，解決了Gennaro等[3]留下的公開問題，該方案運(yùn)用加法同態(tài)加密算法來保證多項(xiàng)式的隱私性，但是不能保證輸入的隱私性和實(shí)現(xiàn)公開驗(yàn)證。Barbosa等[6]提出了可委托的同態(tài)加密(Delegatable Homomorphic Encryption, DHE)密碼學(xué)原語，并給出了如何運(yùn)用DHE構(gòu)造可驗(yàn)證計算方案的方法。2012年，F(xiàn)iore等[7]提出了可公開驗(yàn)證的多項(xiàng)式外包計算方案，但是不能保證輸入和函數(shù)的隱私性。2013年，Zhang等[8]利用多線性映射和同態(tài)加密算法構(gòu)造了單變量多項(xiàng)式外包計算方案，該方案能夠保證輸入的隱私性，其擴(kuò)展方案保證了函數(shù)的隱私性，但是都只能做到私有驗(yàn)證。任艷麗等[9]在此基礎(chǔ)上構(gòu)造了多元多項(xiàng)式的可驗(yàn)證外包計算方案，同樣只能做到私有驗(yàn)證。Papamanthou等[10]提出了動態(tài)多項(xiàng)式的可驗(yàn)證外包計算方案，允許對系數(shù)進(jìn)行遞增的更新。CCS2014，F(xiàn)iore等[11]提出了適應(yīng)性安全的可驗(yàn)證多項(xiàng)式外包計算方案，但是該方案只能保證函數(shù)的隱私性。為了減少存儲開銷，2015年，Zhang等[12]首次提出了批驗(yàn)證(Batch Verifiable Computation, BVC)的概念，構(gòu)造了兩個批驗(yàn)證的多項(xiàng)式外包計算方案，提出了如何構(gòu)造可公開進(jìn)行批驗(yàn)證的外包計算方案這一公開問題。2016年，Sun等[13]解決了這一公開問題，能夠做到任何第三方都能有效驗(yàn)證服務(wù)器返回結(jié)果的正確性。

當(dāng)前，可驗(yàn)證的安全外包計算方案大都基于單服務(wù)器模型，用戶將外包數(shù)據(jù)交給單個云服務(wù)器來進(jìn)行計算，并通過云服務(wù)器返回的輔助信息來驗(yàn)證結(jié)果的正確性，但是不能完全做到可公開驗(yàn)證的情況下保證輸入和輸出的隱私性，并且受限于預(yù)計算量較大、交互輪數(shù)較多等實(shí)際缺陷。實(shí)際情況下，云服務(wù)提供商并不僅限于單個實(shí)體，可能存在多個服務(wù)提供商同時提供服務(wù)。云服務(wù)提供商之間存在一定的競爭關(guān)系，因而不會為了短期利益而勾結(jié)在一起攻擊用戶隱私數(shù)據(jù)。本文利用多線性映射[14]和BGN(Boneh-Goh-Nissim)同態(tài)加密算法[15]，提出了雙服務(wù)器安全模型下的多元多項(xiàng)式外包計算方案，該方案能夠同時保證輸入和輸出的隱私性，并且實(shí)現(xiàn)了可公開驗(yàn)證的功能。分析結(jié)果表明，本文方案在安全性上能夠達(dá)到CPA安全，用戶的計算代價遠(yuǎn)遠(yuǎn)小于服務(wù)器以及直接計算多元多項(xiàng)式函數(shù)的計算代價。

1　預(yù)備知識

1.1　BGN加密算法

BGN加密算法[15]支持任意次的加法同態(tài)操作和一次乘法同態(tài)操作。其具體算法如下所示：

1)密鑰生成(KeyGen(1λ)→pk,sk)：選擇安全參數(shù)λ∈Z+，生成元組(p,q,G,G1,e)。其中：p和q分別是兩個不同的大素數(shù)，循環(huán)群G的階為N=pq，雙線性映射e：G×G→G1，G1的階為g1=e(g,g)。從G中隨機(jī)選擇兩個生成元g和u，令h=uq，h1=e(g,h)。公鑰pk={N,G,G1,e,g,h}，私鑰sk=p。

2)加密(Enc(m,pk)→c)：從{1,2,…,N}中隨機(jī)選擇一個r，用公鑰pk加密消息m∈M，輸出密文c，即c=gmhr∈G1。

3)解密(Dec(c,sk)→m)：用私鑰sk解密密文c輸出m∈M，即cp=(gp)m。

BGN加密算法其同態(tài)性質(zhì)為：給定兩個密文c1=gm1hr1和c2=gm2hr2，則：

1)加法同態(tài)：c1·c2=gm1hr1·gm2hr2=gm1+m2·hr1+r2，即Enc(m1+m2)=c1·c2。

2)乘法同態(tài)：存在某個δ∈ZN，使得h=gqδ。則：

e(c1,c2)=e(gm1hr1,gm2hr2)=e(gm1+qδr1,gm2+qδr2)=

所以Enc(m1·m2)=e(c1,c2)。

1.2　多線性映射

1.3　 安全模型

可驗(yàn)證計算中，用戶將編碼后的函數(shù)f和輸入x發(fā)送給云服務(wù)器，云服務(wù)器能夠計算出被編碼的f(x)和一個附加證明，用戶驗(yàn)證云服務(wù)器的計算結(jié)果是否正確并輸出。方案Π=(KeyGen,ProbGen,Compute,Verify)由四部分組成，其具體描述如下：

1)(pk,sk)←KeyGen(1λ,f):輸入安全參數(shù)λ和函數(shù)f，產(chǎn)生公鑰pk和私鑰sk。

2)(σ,τ)←ProbGen(sk,x):輸入私鑰sk和x，產(chǎn)生編碼后輸入σ和可驗(yàn)證密鑰τ。

3)(ρ,π)←Compute(pk,σ):輸入公鑰pk和編碼后輸入σ，產(chǎn)生編碼后的輸出ρ和證明π。

4){f(x),⊥}←Verify(sk,τ,ρ,π):輸入私鑰sk和可驗(yàn)證密鑰τ，編碼后的輸入ρ和證明π，輸出f(x)或者⊥。

下面介紹可驗(yàn)證計算的安全模型，包括可驗(yàn)證性和隱私性[9]。

Setup階段：B執(zhí)行Setup算法，并將公鑰pk發(fā)送給A。

Phase1階段：A對B進(jìn)行輸入的加密詢問：A將(α1,α2,…,αn)發(fā)送給B，B將σ=(σα1,σα2,…,σαn)返回給A。該詢問可重復(fù)多次。

如果多項(xiàng)式時間內(nèi)敵手經(jīng)過q次詢問后都不能以大于ε的概率贏得上述游戲，則可公開驗(yàn)證多元多項(xiàng)式外包計算方案是可驗(yàn)證的。

輸入隱私性可以通過三個參與者進(jìn)行下列游戲，包括敵手A，模擬器S和挑戰(zhàn)者B。

Setup階段：S與B執(zhí)行Setup算法，并把公鑰pk發(fā)送給A。

Phase1階段： A發(fā)送函數(shù)輸入(α1,α2,…,αn)給S進(jìn)行加密詢問，S返回σ=(σα1,σα2,…,σαn)給A。該詢問可重復(fù)多次。

1.4　困難問題

本文方案的隱私性和安全性依賴于子群判定假設(shè)(Subgroup Decision Assumption, SDA)問題[8]。

定義2SDA問題。如果對于任意概率多項(xiàng)式敵手A，|Pr[A(Γk,u)=1]-Pr[A(Γk,uq)=1]|

2　可公開驗(yàn)證多項(xiàng)式外包計算方案

2.1　基于多線性映射的擴(kuò)展BGN同態(tài)加密算法

1)BGNk加法同態(tài)操作：Enc(m1+m2+…+mk)=Enc(m1)·Enc(m2)·…·Enc(mk)。

2)BGNk乘法同態(tài)操作：Enc(m1·m2·…·mk)=ek(Enc(m1),Enc(m2),…,Enc(mk))。

2.2　基于擴(kuò)展BGN同態(tài)加密的基礎(chǔ)計算方法

2.3　基于雙服務(wù)器模型的可公開驗(yàn)證外包計算方案

現(xiàn)基于上述的計算方法介紹本文方案算法如下：

σf(α1,α2,…,αn)=Enc(f(α1,α2,…,αn))=

所以ρ1=e(Enc(f(α1,α2,…,αn)),Enc(γ))=e(σf(α1,α2,…,αn),ψγ)。同理，云服務(wù)器S2接收到用戶發(fā)送來的σ后，計算得到

和

4)驗(yàn)證結(jié)果Verify(ρ1,ρ2):用戶接收到ρ1和ρ2，驗(yàn)證e(ψγ,ρ2)=e(ψη,ρ1)是否成立。如果等式成立，則用戶輸出f(α)。

3　方案分析

3.1　正確性分析

引理1如果兩個不可勾結(jié)的云服務(wù)器是誠實(shí)的，則y=f(α1,α2,…,αn)成立。

證明因?yàn)?/p>

e(ψγ,ρ2)=e(Enc(γ),Enc(ηf(α1,α2,…,αn)))=

Enc(γηf(α1,α2,…,αn))

e(ψη,ρ1)=e(Enc(η),Enc(γf(α1,α2,…,αn)))=

Enc(ηγf(α1,α2,…,αn))

如果云服務(wù)器返回的值是正確的，則e(ψγ,ρ2)=e(ψη,ρ1)成立。

因?yàn)?

所以：

因此，用戶解密e(ψγ,ρ2)p便能夠計算出y=f(α1,α2,…,αn)。

3.2　安全性分析

上述方案Π輸入的隱私性基于SDA問題，兩個不可勾結(jié)的不可信云服務(wù)器不能區(qū)分用戶的兩個不同輸入，從而保證輸入數(shù)據(jù)的安全性；并且方案Π能夠驗(yàn)證結(jié)果的正確性，使得云服務(wù)器不會迫使用戶接收偽造的返回值y≠f(α1,α2,…,αn)。

引理2如果SDA對于Γkn+2來說是困難問題，則本文方案Π能夠獲得輸入輸出隱私安全。

1)模擬者S選擇多元多項(xiàng)式

然后將公鑰(N,G1,G2,…,Gkn+2,e,g1,g2,…,gkn+2,h)發(fā)送給A。

因此：

Pr[B|i=l,b=1]Pr[b=1])=

Pr[b′=1|i=l,b=1])=

Pr[A(pk,Ul+1)=1])=

即敵手A能夠至少以不可忽略的概率ε/k來攻破BGNkn+2語義安全。當(dāng)SDA問題成立時，該假設(shè)不成立。

同理，用戶將參數(shù)ψγ和ψη公開，敵手A也不能攻破BGNkn+2語義安全來區(qū)分兩個不同的輸入γ0和γ1以及輸入η0和η1。當(dāng)SDA困難問題成立時，敵手也不能攻破BGNkn+2語義安全來區(qū)分兩個不同的輸出。

綜上所述，本文方案Π能夠獲得輸入輸出的隱私安全。

引理3假設(shè)兩個不可勾結(jié)的云服務(wù)器從用戶接收的輸入隱私安全，并且BGNkn+2加密方案安全，則本文方案Π能夠驗(yàn)證結(jié)果的正確性，獲得正確的輸出。

證明假設(shè)存在惡意敵手A以不可忽略的概率ε攻破BGNkn+2加密方案，當(dāng)用戶公開參數(shù)ψγ和ψη后，惡意敵手A(包括云服務(wù)器S1)能夠破解找到γ′使得γ′=γ的概率為Pr[γ′=γ]≥ε，同時得到η′和f′(α1,α2,…,αn)的概率分別都為Pr[η′=η]≥ε和Pr[f′(α1,α2,…,αn)=f(α1,α2,…,αn)]≥ε，故而敵手A偽造出γ′η′f′(α1,α2,…,αn)的概率為Pr[γ′η′f′(α1,α2,…,αn)=γηf(α1,α2,…,αn)]≥ε3。

同理，惡意敵手A′(包括云服務(wù)器S2)能夠偽造出γ″使得γ″=γ的概率為Pr[γ″=γ]≥ε，同時得到η″和f″(α1,α2,…,αn)的概率分別都為Pr[η″=η]≥ε和Pr[f″(α1,α2,…,αn)=f(α1,α2,…,αn)]≥ε，故而敵手A偽造出γ″η″f″(α1,α2,…,αn)的概率為Pr[γ″η″f″(α1,α2,…,αn)=γηf(α1,α2,…,αn)]≥ε3。因?yàn)閮蓚€云服務(wù)器S1和S2不能相互勾結(jié)串通，所以惡意敵手偽造出γ″η″f″(α1,α2,…,αn)=γ′η′f′(α1,α2,…,αn)使得通過公開驗(yàn)證e(ψγ,ρ2)=e(ψη,ρ1)的概率為Pr[e(ψγ,ρ2)=e(ψη,ρ1)]≥(ε3)·(ε3)=ε6，即敵手至少能夠以ε6的概率通過用戶或公共的驗(yàn)證。當(dāng)SDA問題成立時，BGNkn+2加密方案安全，該假設(shè)不成立。

定理1如果SDA成立，則基于兩個不可勾結(jié)的云服務(wù)器的外包計算方案是滿足輸入隱私安全的可公開驗(yàn)證方案。

證明結(jié)合引理1～3可證明該定理。為了保證多元多項(xiàng)式函數(shù)的隱私性，用戶可以對多項(xiàng)式系數(shù)進(jìn)行加密得到Enc(fi1,i2,…,in)，然后傳送給兩個不同的云服務(wù)器S1和S2。云服務(wù)器計算出

從而計算出Enc(f(α1,α2,…,αn))，并且可以證明該方案輸入與多項(xiàng)式函數(shù)的隱私性和安全性。

3.3　性能分析

表1　本文方案效率分析Tab. 1　Efficiency analysis of the proposed scheme

為了更加清晰地展示本文方案的高效性，對其進(jìn)行了性能測試，運(yùn)行環(huán)境為64位Windows操作系統(tǒng)，頻率為2.5 GHz 4核Core i5 CPU，內(nèi)存4 GB，采用密碼函數(shù)庫jPBC(java Pairing-Based Cryptography)TypeA1合數(shù)階對稱雙線性群進(jìn)行仿真實(shí)驗(yàn)。分別測試了BGN加解密算法、雙線性對運(yùn)算的平均運(yùn)行時間，具體如表2所示。對n元d階多項(xiàng)式進(jìn)行測試時，實(shí)驗(yàn)參數(shù)設(shè)置為安全參數(shù)|λ|=20 bit，n=4，k=6，d=63，多項(xiàng)式輸入αi的長度l分別為20、30、40、50 bit，多項(xiàng)式項(xiàng)數(shù)|f|分別設(shè)置為1 000、5 000、10 000、20 000，其平均運(yùn)行時間如表3所示。

表2　基本密碼學(xué)操作時間開銷　msTab. 2　Time overhead of fundamental cryptographic operations　ms

本文分別大致計算出不同輸入長度(l)時用戶計算的時間消耗，然后與直接計算多項(xiàng)式的時間消耗進(jìn)行對比分析。當(dāng)l固定長度為20 bit時，其運(yùn)行時間如圖1(a)所示；隨著多項(xiàng)式項(xiàng)數(shù)的逐漸增多，本文方案外包計算的優(yōu)勢逐漸顯示出來，其時間消耗只與多項(xiàng)式的深度有關(guān)，不會隨著多項(xiàng)式項(xiàng)數(shù)的增加而增加；當(dāng)多項(xiàng)式項(xiàng)數(shù)固定為10 000時，其運(yùn)行時間如圖1(b)所示，本文方案外包計算的時間消耗小于直接計算的時間消耗，但會隨著輸入長度的增加而增加。

表3　4元63階多項(xiàng)式平均運(yùn)行時間　msTab. 3　Average running time of 4-variate 63-order polynomials 　ms

圖1　外包計算和直接計算時間對比Fig. 1　Computing time comparison between outsourced and direct computation

通過理論分析與實(shí)踐對比，外包計算方案中用戶的計算量遠(yuǎn)遠(yuǎn)小于直接計算函數(shù)的計算量，也小于云服務(wù)器的計算量，因此該方案是高效的可驗(yàn)證外包計算方案。

4　結(jié)語

利用多線性映射和BGN同態(tài)加密算法，設(shè)計了可公開驗(yàn)證的多元多項(xiàng)式外包計算方案。該方案基于雙服務(wù)器模型，用戶需要向兩個云服務(wù)器發(fā)送外包數(shù)據(jù)，利用兩個不可勾結(jié)的云服務(wù)器的計算能力，計算出兩個不同的結(jié)果，用戶或者第三方可以通過公開的數(shù)據(jù)對結(jié)果進(jìn)行驗(yàn)證，如果驗(yàn)證通過，用戶可以用私鑰解密得到多項(xiàng)式的值。方案的輸入采用同態(tài)加密算法進(jìn)行處理，在標(biāo)準(zhǔn)模型下達(dá)到CPA安全，能夠保證輸入與輸出的隱私性，并且能夠做到公開驗(yàn)證。但是為了保證輸入輸出的隱私性與安全性，方案均采用同態(tài)加密算法進(jìn)行加密，一定程度上增加了計算、通信和存儲復(fù)雜度。如何利用非同態(tài)加密技術(shù)對數(shù)據(jù)進(jìn)行處理，同時針對多個多元多項(xiàng)式函數(shù)進(jìn)行外包計算或者實(shí)現(xiàn)批驗(yàn)證是提高多項(xiàng)式外包計算效率的研究重點(diǎn)。

參考文獻(xiàn):

[1]ABO-ALIAN A, BADR N L, TOLBA M F. Data storage security service in cloud computing: challenges and solutions [M]// Multimedia Forensics and Security, Intelligent Systems Reference Library, vol 115. Cham: Springer, 2017: 25-57.

[2]曹珍富.密碼學(xué)的新發(fā)展[J].四川大學(xué)學(xué)報(工程科學(xué)版),2015,47(1):1-12. (CAO Z F. New development of cryptography[J]. Journal of Sichuan University (Engineering Science Edition), 2015, 47(1): 1-12.)

[3]GENNARO R, GENTRY C, PARNO B. Non-interactive verifiable computing: outsourcing computation to untrusted workers [C]// CRYPTO 2010: Proceedings of the 2010 Conference on Advances in Cryptology, LNCS 6223. Berlin: Springer, 2010: 465-482.

[4]李勇,曾振宇,張曉菲.支持屬性撤銷的外包解密方案[J].清華大學(xué)學(xué)報(自然科學(xué)版),2013,53(12):1664-1669. (LI Y, ZENG Z Y, ZHANG X F. Outsourced decryption scheme supporting attribute revocation [J]. Journal of Tsinghua University (Science and Technology), 2013, 53(12): 1664-1669.)

[5]BENABBAS S, GENNARO R, VAHLIS Y. Verifiable delegation of computation over large datasets [C]// CRYPTO 2011: Proceedings of the 2011 Annual Cryptology Conference, LNCS 6841. Berlin: Springer, 2011: 111-131.

[6]BARBOSA M, FARSHIM P. Delegatable homomorphic encryption with applications to secure outsourcing of computation [C]// CT-RSA 2012: Proceedings of the Cryptographers’ Track at the RSA Conference, LNCS 7178. Berlin: Springer, 2011: 296-312.

[7]FIORE D, GENNARO R. Publicly verifiable delegation of large polynomials and matrix computations, with applications [C]// CCS ’12: Proceedings of the 2012 ACM Conference on Computer and Communications Security. New York: ACM, 2012: 501-512.

[8]ZHANG L F, SAFAVI-NAINI R. Private outsourcing of polynomial evaluation and matrix multiplication using multilinear maps [C]// Proceedings of the 12th International Conference on Cryptology and Network Security, LNCS 8257. Cham: Springer, 2013: 329-348.

[9]任艷麗,谷大武,蔡建興,等.隱私保護(hù)的可驗(yàn)證多元多項(xiàng)式外包計算方案[J].通信學(xué)報,2015,36(8):23-30. (REN Y L, GU D W, CAN J X, et al. Verifiably private outsourcing scheme for multivariate polynomial evaluation [J]. Journal on Communications, 2015, 36(8): 23-30.)

[10]PAPAMANTHOU C, SHI E, TAMASSIA R. Signatures of correct computation [C]// Proceedings of the 10th Theory of Cryptography Conference on Theory of Cryptography, LNCS 7785. Berlin: Springer, 2013: 222-242.

[11]FIORE D, GENNARO R, PASTRO V. Efficiently verifiable computation on encrypted data [C]// CCS ’14: Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2014: 844-855.

[12]ZHANG L F, SAFAVI-NAINI R. Batch verifiable computation of polynomials on outsourced data [C]// ESORICS 2015: Proceedings of the 2015 European Symposium on Research in Computer Security, LNCS 9327. Cham: Springer, 2015: 167-185.

[13]SUN Y, YU Y, LI X, et al. Batch verifiable computation with public verifiability for outsourcing polynomials and matrix computations [C]// Proceedings of the 21st Australasian Conference on Information Security and Privacy: Part I, LNCS 9722. Cham: Springer, 2016: 293-309.

[14]GARG S, GENTRY C, HALEVI S. Candidate multilinear maps from ideal lattices [C]// EUROCRYPT 2013: Proceedings of the 2013 Annual International Conference on the Theory and Applications of Cryptographic Techniques, LNCS 7881. Berlin: Springer, 2012: 1-17.

[15]BONEH D, GOH E-J, NISSIM K. Evaluating 2-DNF formulas on ciphertexts [C]// TCC 2005: Proceedings of the 2005 Theory of Cryptography Conference, LNCS 3378. Berlin: Springer, 2005: 325-341.