李秋賢，周全興，王振龍，丁紅發(fā)，潘齊欣

（1.凱里學(xué)院 大數(shù)據(jù)工程學(xué)院，貴州 凱里 556011；2.貴州財(cái)經(jīng)大學(xué) 信息學(xué)院，貴陽(yáng) 550025）

0 概述

在大數(shù)據(jù)快速發(fā)展的時(shí)代背景下，云計(jì)算通過(guò)強(qiáng)大的計(jì)算能力和存儲(chǔ)能力［1］為云端客戶提供各種委托計(jì)算服務(wù)，能夠節(jié)省委托方大量的計(jì)算時(shí)間和計(jì)算成本，但委托計(jì)算驗(yàn)證結(jié)果所消耗的時(shí)間必須遠(yuǎn)少于計(jì)算函數(shù)本身，否則委托計(jì)算將毫無(wú)意義。隨著計(jì)算需求量的增加，委托計(jì)算也面臨很多嚴(yán)峻的挑戰(zhàn)［2］，如計(jì)算協(xié)議中會(huì)存在惡意的計(jì)算方故意偏離協(xié)議的執(zhí)行，從而泄露用戶的隱私數(shù)據(jù)或返回非正確的計(jì)算結(jié)果，或者計(jì)算方誠(chéng)實(shí)地將計(jì)算結(jié)果返回給用戶，而惡意的私自驗(yàn)證客戶卻聲稱服務(wù)器返回的結(jié)果不正確，從而拒絕支付委托費(fèi)用。因此，有必要設(shè)計(jì)一種在不泄露用戶隱私的前提下能夠公開(kāi)驗(yàn)證的委托計(jì)算協(xié)議。

針對(duì)數(shù)據(jù)的安全性和隱私性，公開(kāi)可驗(yàn)證計(jì)算（PVC）方案［3］能夠提供較好的解決思路，其計(jì)算過(guò)程為：委托方對(duì)需要委托的函數(shù)進(jìn)行一系列混淆加密后發(fā)送給云端服務(wù)器；服務(wù)器返回正確的計(jì)算結(jié)果和結(jié)果證明，所有的公開(kāi)驗(yàn)證者都可以驗(yàn)證其結(jié)果的正確性，且驗(yàn)證成本遠(yuǎn)小于本地執(zhí)行的成本。可驗(yàn)證計(jì)算一般分為兩類：一類是一般函數(shù)的可驗(yàn)證委托計(jì)算［4-5］，適用于任何函數(shù)的計(jì)算；另一類是特殊函數(shù)的委托計(jì)算，如矩陣乘法和多項(xiàng)式計(jì)算［6-8］、模指數(shù)運(yùn)算［9］等。在實(shí)際委托計(jì)算環(huán)境中，許多問(wèn)題都可以轉(zhuǎn)化為多元多項(xiàng)式的求值模型，如評(píng)估一個(gè)人的健康狀況、根據(jù)水源中的COD 濃度建立污染物水質(zhì)分析模型等。

2010 年，GENNARO 等人［10］在CRYPTO 會(huì)議上首次提出可驗(yàn)證計(jì)算的概念，并利用全同態(tài)加密技術(shù)和混淆電路技術(shù)構(gòu)造可驗(yàn)證計(jì)算方案，從而保證了委托計(jì)算輸入與輸出的隱私性。文獻(xiàn)［11］設(shè)計(jì)選擇明文攻擊（CPA）安全的多項(xiàng)式委托計(jì)算協(xié)議來(lái)保證多項(xiàng)式函數(shù)的隱私性，以解決可驗(yàn)證計(jì)算方案只能私自驗(yàn)證的問(wèn)題。文獻(xiàn)［12］利用全同態(tài)加密技術(shù)，在所構(gòu)造的非交互式委托計(jì)算方案中降低了委托計(jì)算的通信量。文獻(xiàn)［13］利用多線性映射和全同態(tài)加密技術(shù)，在保證輸入隱私性的情況下，設(shè)計(jì)了單變量多項(xiàng)式委托計(jì)算方案。文獻(xiàn)［14］構(gòu)造了多項(xiàng)式委托計(jì)算協(xié)議，但不能保證其可證明安全性。文獻(xiàn)［15］通過(guò)隨機(jī)化混淆電路提出的可驗(yàn)證委托計(jì)算方案，實(shí)現(xiàn)了混淆電路的可重用。文獻(xiàn)［16-17］在博弈論的框架下設(shè)計(jì)理性委托計(jì)算協(xié)議，利用混淆電路與全同態(tài)加密技術(shù)設(shè)計(jì)可證明安全的委托計(jì)算方案，保證了可驗(yàn)證計(jì)算的有效性。

如何使委托計(jì)算能在公開(kāi)可驗(yàn)證情況下保證計(jì)算結(jié)果的隱私性以及協(xié)議的安全性，一直是眾多研究學(xué)者所關(guān)心的問(wèn)題。文獻(xiàn)［18］針對(duì)身份驗(yàn)證過(guò)程，提出一種新的方案來(lái)解決因用戶損壞和服務(wù)器受損而引起的各種問(wèn)題，該方案被證明是安全的，且避免了隱私性與實(shí)用性的沖突。文獻(xiàn)［19］針對(duì)協(xié)議中會(huì)存在惡意攻擊者的問(wèn)題構(gòu)造了一種更強(qiáng)大的C2C PAKE 協(xié)議來(lái)應(yīng)對(duì)惡意攻擊，以保證協(xié)議中通信的安全。文獻(xiàn)［20］提出了一種魯棒的多因素身份驗(yàn)證方案，利用RSA 密碼系統(tǒng)的不平衡計(jì)算特性保證方案的安全性。文獻(xiàn)［21］通過(guò)使用基于身份的簽名方案構(gòu)造一種針對(duì)MCC 服務(wù)的PAA 方案，該方案不僅能夠保證參與者的通信安全，而且可以滿足MCC 服務(wù)的安全要求。

本文利用全同態(tài)加密與多線性映射技術(shù)構(gòu)造可公開(kāi)驗(yàn)證的多元多項(xiàng)式委托計(jì)算安全協(xié)議，并在標(biāo)準(zhǔn)模型下，基于多線性Diffie-Hellman（Multi-linear Diffie-Hellman，MDH）困難性數(shù)學(xué)問(wèn)題假設(shè)證明協(xié)議的有效性和安全隱私性，存在任意第三方利用多線性性質(zhì)都可以滿足委托計(jì)算結(jié)果的正確性。

1 預(yù)備知識(shí)

1.1 全同態(tài)加密

全同態(tài)加密通常包括4 個(gè)階段［22］，即預(yù)處理階段(SK，PK)←SetupFHE(1λ)、加密階段c←EncryptFHE(PK，m)、解密階段m←DecryptFHE(SK，c)和運(yùn)算函數(shù)階段cf←EvalFHE(PK，cin，f)。

對(duì)于任意的k∈?N且k≥2，BGN 同態(tài)加密算法BGNk=(Gen，Enc，Dec)描述如下：

1）密鑰生成算法。Γk=(N，G1，G2，…，Gk，e，g1，g2，…，gk)←G(1λ，k)表示為隨機(jī)的k多線性映射實(shí)例，其中，N=pq，p和q均為λbit 大素?cái)?shù)，e是任意自然常數(shù)，gi是循環(huán)群Gi的生成元，公鑰PK=(g1，h)和私鑰SK=p，h=uq，u←G1，h=uq，u←G1表示散列函數(shù)。

2）加密算法。密文c=Enc(PK，m)，輸入明文m和公鑰PK，輸出密文，其中，r∈?N。設(shè)，δ∈?N且rl∈?N，hk=。

3）解密算法。明文m=Dec(SK，c)，此算法是以SK和密文c為輸入的解密算法，輸出消息m，使得，并求解離散對(duì)數(shù)問(wèn)題得到明文m。

1.2 多線性映射

設(shè)G1和G2分別為q階（q為大素?cái)?shù)）加法循環(huán)群(G1，+)和乘法循環(huán)群（G2，+），多線性映射e：具有以下性質(zhì)：

1）多線性：對(duì)于任意g1，g2，…，gn∈G1和a1，，滿足等式en(a1g1，a2g2，…，an gn)=。

2）非退化性：如果任意g是G1的生成元，則en(g，g，…，g)是G2的生成元。

3）可計(jì)算性：對(duì)所有的g1，g2，…，gn∈G1，存在有效的計(jì)算法則en(g，g，…，g)，則稱en(g，g，…，g)為多線性映射。

1.3 困難性問(wèn)題假設(shè)

MDH 困難性問(wèn)題描述如下：在(G1，G2，e)中，G1、G2均是N循環(huán)群，隨機(jī)選取x1，x2，…，xn∈?N，對(duì)于給定G1的生成元，計(jì)算是困難的。

多線性離散對(duì)數(shù)問(wèn)題（MDL）描述如下：設(shè)G1為N階循環(huán)群，對(duì)于所有的k＞1(1≤i≤k)以及gi是循環(huán)群Gi的一個(gè)生成元，給定(i，gi，gxi)，對(duì)于任意x∈?*N，求解x是困難的。

2 安全模型

本文提出基于隱私保護(hù)可證明安全的委托計(jì)算協(xié)議及其安全模型，并從安全性和隱私性角度對(duì)協(xié)議進(jìn)行驗(yàn)證。

2.1 協(xié)議安全性

在安全模型試驗(yàn)中，假設(shè)需要委托多元多項(xiàng)式函數(shù)F，將函數(shù)的輸入定義為x。本文協(xié)議運(yùn)用全同態(tài)加密算法對(duì)輸入x進(jìn)行加密，其中公共值為σx←(PK，Encrypt)，私有值τx←(SK)。定義敵手在此安全模型中的優(yōu)勢(shì)為ADVA(PVMPC，F(xiàn)，λ)=，即存在任意多項(xiàng)式概率的敵手A，如果概率是可以忽略的，則協(xié)議是安全的。形式化分析如下：

公開(kāi)可驗(yàn)證多元多項(xiàng)式委托計(jì)算協(xié)議的安全性驗(yàn)證過(guò)程如下：

假設(shè)該試驗(yàn)中存在敵手A 和挑戰(zhàn)者C 兩個(gè)主要參與者。

1）初始化階段：挑戰(zhàn)者C 首先需要執(zhí)行KeyGen算法，然后把生成的公鑰PK發(fā)送給敵手A。

2）詢問(wèn)階段：敵手A 對(duì)C 進(jìn)行有界多項(xiàng)式次加密詢問(wèn)后發(fā)送函數(shù)(x1，x2，…，xn)給C，C 加密后將密文σ=(σx1，σx2，…，σxn)發(fā)送給A。

2.2 協(xié)議隱私性

該協(xié)議的隱私性驗(yàn)證過(guò)程如下：

假設(shè)游戲中存在敵手A、挑戰(zhàn)者C 和模擬器S 3 個(gè)主要參與者。

1）初始化階段：S 與C 執(zhí)行Setup 算法，并將公鑰PK發(fā)送給A。

2）詢問(wèn)階段：A 發(fā)送(x1，x2，…，xn)給S 進(jìn)行加密詢問(wèn)，S 返回σ=(σx1，σx2，…，σxn)給A，在此過(guò)程中的詢問(wèn)可以是重復(fù)多次的。

3）挑戰(zhàn)階段：詢問(wèn)結(jié)束后，A 選擇兩個(gè)輸入x1=(x11，x12，…，x1n)和x2=(x21，x22，…，x2n)發(fā)送給S，S 選擇i∈{1，2，…，k}，計(jì)算，并發(fā)送給C，C 選擇b={0，1}，并發(fā)送Enc(βb)給S，S 計(jì)算出T=(Enc(x1)，，并將T發(fā)送給A，A 返回b′={0，1}給S。

4）猜測(cè)階段：如果b′=1，則S 輸出，否則輸出；如果則敵手A 贏得這個(gè)游戲。

3 協(xié)議構(gòu)造

在上節(jié)構(gòu)建的安全模型中引入全同態(tài)加密技術(shù)和雙線性映射方案，設(shè)計(jì)隱私保護(hù)下可公開(kāi)驗(yàn)證的多元多項(xiàng)式委托計(jì)算協(xié)議，如圖1 所示。

圖1 可公開(kāi)驗(yàn)證委托計(jì)算協(xié)議示意圖Fig.1 Schematic diagram of publicly verifiable delegation computing protocol

假設(shè)委托方需要將n元d次多項(xiàng)式函數(shù)以及輸入(x1，x2，…，xn)委托給云服務(wù)器進(jìn)行計(jì)算，協(xié)議算法描述如下：

1）初始化階段

如果以上驗(yàn)證成立，則輸出計(jì)算加密函數(shù)值ρ，否則輸出⊥。

（3）PrivRet(VKx，PKx，ρ)。當(dāng)公開(kāi)驗(yàn)證者返回計(jì)算加密函數(shù)值ρ給用戶時(shí)，用戶用私人檢索密鑰驗(yàn)證計(jì)算的真實(shí)值y=F(x1，x2，…，xn)，且y滿足ρp=(gpkn)y，否則公開(kāi)驗(yàn)證者輸出⊥。

4 協(xié)議分析

對(duì)本文提出的基于隱私保護(hù)的可證明安全委托計(jì)算協(xié)議進(jìn)行有效性和安全性分析。

4.1 有效性分析

如果協(xié)議中服務(wù)器返回的計(jì)算加密函數(shù)值ρ及驗(yàn)證證明π能夠通過(guò)公開(kāi)驗(yàn)證者的驗(yàn)證，即表明本文協(xié)議是正確且有效的。

引理如果云端服務(wù)器是誠(chéng)實(shí)的，則有式（2）成立且y=f(x1，x2，…xn)成立。

因此，如果云端服務(wù)器是誠(chéng)實(shí)的，則式（2）成立。又因?yàn)橛腥缦碌仁匠闪ⅲ?/p>

因此，若式（2）成立，則y=f(x1，x2，…，xn)也成立，即證明本文提出的基于隱私保護(hù)的可證明安全委托計(jì)算協(xié)議是正確且有效的。如果存在多元多項(xiàng)式函數(shù)，本文協(xié)議能夠在可公開(kāi)驗(yàn)證條件下達(dá)到隱私保護(hù)和可證明安全的目標(biāo)。

4.2 安全性分析

定理1在MDH 困難性數(shù)學(xué)問(wèn)題假設(shè)下，本文提出的隱私保護(hù)下可公開(kāi)驗(yàn)證的委托計(jì)算協(xié)議是可證明安全的。

由此說(shuō)明模擬器S 能夠以不可忽略的概略ε解決數(shù)學(xué)難題(k(n+1))-MDH，這與假設(shè)(k(n+1))-MDH是困難問(wèn)題相矛盾，因此，假設(shè)不成立，則表明構(gòu)建的PVMPC 方案是安全且隱私的。

5 性能分析與實(shí)驗(yàn)仿真

5.1 性能分析

表1 本文協(xié)議各階段的計(jì)算復(fù)雜度Table 1 Computational complexity of each stage in the proposed protocol

表2 本文協(xié)議與其他協(xié)議性能對(duì)比Table 2 Performance comparison between the proposed protocol and other protocols

5.2 實(shí)驗(yàn)仿真

為更清晰地體現(xiàn)本文協(xié)議的效率優(yōu)勢(shì)，對(duì)本文協(xié)議進(jìn)行仿真實(shí)現(xiàn)。用戶和云服務(wù)器的運(yùn)行環(huán)境分別為Intel?CoreTMi3 Processor（2.4 GH，4 GB 內(nèi)存）和Intel i5 Processor（3.0 GHz，8 GB 內(nèi)存）。對(duì)n元d階多項(xiàng)式進(jìn)行實(shí)驗(yàn)?zāi)M時(shí)，實(shí)驗(yàn)的安全參數(shù)設(shè)置為安全參數(shù)|λ|=30 bit，n=4，多項(xiàng)式的次數(shù)設(shè)為d=43 和d=127。

分別對(duì)四元43 次多項(xiàng)式和四元127 次多項(xiàng)式進(jìn)行模擬實(shí)驗(yàn)，仿真委托計(jì)算和直接計(jì)算分別與群數(shù)階N和｜f｜的關(guān)系。設(shè)置外包任務(wù)輸入xi的長(zhǎng)度l=30 bit，多項(xiàng)式的項(xiàng)數(shù)｜f｜=1 000，5 000，10 000，15 000，20 000，25 000，實(shí)驗(yàn)結(jié)果如圖2 所示。

圖2 委托計(jì)算與直接計(jì)算的時(shí)間消耗Fig.2 Time consumption of delegation calculation and direct calculation

由仿真結(jié)果可知，本文協(xié)議中用戶的計(jì)算消耗量遠(yuǎn)小于用戶直接計(jì)算函數(shù)的計(jì)算量，由此表明本文方案是有效的。

6 結(jié)束語(yǔ)

為實(shí)現(xiàn)云計(jì)算中對(duì)計(jì)算結(jié)果的公開(kāi)可驗(yàn)證性、敏感數(shù)據(jù)的隱私性并抵抗對(duì)惡意用戶偏離協(xié)議的行為，本文基于全同態(tài)加密技術(shù)和多線性映射方案的優(yōu)勢(shì)，設(shè)計(jì)一個(gè)適用于多元多項(xiàng)式函數(shù)的委托計(jì)算協(xié)議，其在MDH 困難性問(wèn)題假設(shè)下滿足可證明安全性。性能分析和實(shí)驗(yàn)仿真結(jié)果驗(yàn)證了該協(xié)議的有效性和隱私保護(hù)性。本文工作是在雙線性映射方案中保證委托計(jì)算協(xié)議的安全隱私性，下一步將利用其他加密技術(shù)研究更高效的委托計(jì)算方案。