基于雙服務器模型的可公開驗證多元多項式外包計算方案

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

(1.武警工程大學 密碼工程學院，西安 710086；　2.網絡與信息安全武警部隊重點實驗室，西安 710086)(*通信作者電子郵箱yxyangyxyang@163.com)

0　引言

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

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

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

1　預備知識

1.1　BGN加密算法

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

1)密鑰生成(KeyGen(1λ)→pk,sk)：選擇安全參數λ∈Z+，生成元組(p,q,G,G1,e)。其中：p和q分別是兩個不同的大素數，循環群G的階為N=pq，雙線性映射e：G×G→G1，G1的階為g1=e(g,g)。從G中隨機選擇兩個生成元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}中隨機選擇一個r，用公鑰pk加密消息m∈M，輸出密文c，即c=gmhr∈G1。

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

BGN加密算法其同態性質為：給定兩個密文c1=gm1hr1和c2=gm2hr2，則：

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

2)乘法同態：存在某個δ∈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　 安全模型

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

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

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

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

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

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

Setup階段：B執行Setup算法，并將公鑰pk發送給A。

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

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

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

Setup階段：S與B執行Setup算法，并把公鑰pk發送給A。

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

1.4　困難問題

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

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

2　可公開驗證多項式外包計算方案

2.1　基于多線性映射的擴展BGN同態加密算法

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

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

2.2　基于擴展BGN同態加密的基礎計算方法

2.3　基于雙服務器模型的可公開驗證外包計算方案

現基于上述的計算方法介紹本文方案算法如下：

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

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

和

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

3　方案分析

3.1　正確性分析

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

證明因為

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))

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

因為:

所以：

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

3.2　安全性分析

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

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

1)模擬者S選擇多元多項式

然后將公鑰(N,G1,G2,…,Gkn+2,e,g1,g2,…,gkn+2,h)發送給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語義安全。當SDA問題成立時，該假設不成立。

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

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

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

證明假設存在惡意敵手A以不可忽略的概率ε攻破BGNkn+2加密方案，當用戶公開參數ψγ和ψη后，惡意敵手A(包括云服務器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′(包括云服務器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。因為兩個云服務器S1和S2不能相互勾結串通，所以惡意敵手偽造出γ″η″f″(α1,α2,…,αn)=γ′η′f′(α1,α2,…,αn)使得通過公開驗證e(ψγ,ρ2)=e(ψη,ρ1)的概率為Pr[e(ψγ,ρ2)=e(ψη,ρ1)]≥(ε3)·(ε3)=ε6，即敵手至少能夠以ε6的概率通過用戶或公共的驗證。當SDA問題成立時，BGNkn+2加密方案安全，該假設不成立。

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

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

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

3.3　性能分析

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

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

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

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

表3　4元63階多項式平均運行時間　msTab. 3　Average running time of 4-variate 63-order polynomials 　ms

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

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

4　結語

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

參考文獻:

[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]曹珍富.密碼學的新發展[J].四川大學學報(工程科學版),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].清華大學學報(自然科學版),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]任艷麗,谷大武,蔡建興,等.隱私保護的可驗證多元多項式外包計算方案[J].通信學報,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.