基于隱私保護(hù)的可證明安全委托計算協(xié)議

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

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

0 概述

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

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

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

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

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

1 預(yù)備知識

1.1 全同態(tài)加密

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

對于任意的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多線性映射實例，其中，N=pq，p和q均為λbit 大素數(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，使得，并求解離散對數(shù)問題得到明文m。

1.2 多線性映射

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

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

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

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

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

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

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

2 安全模型

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

2.1 協(xié)議安全性

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

公開可驗證多元多項式委托計算協(xié)議的安全性驗證過程如下：

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

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

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

2.2 協(xié)議隱私性

該協(xié)議的隱私性驗證過程如下：

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

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

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

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

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

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

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

圖1 可公開驗證委托計算協(xié)議示意圖Fig.1 Schematic diagram of publicly verifiable delegation computing protocol

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

1）初始化階段

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

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

4 協(xié)議分析

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

4.1 有效性分析

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

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

因此，如果云端服務(wù)器是誠實的，則式（2）成立。又因為有如下等式成立：

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

4.2 安全性分析

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

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

5 性能分析與實驗仿真

5.1 性能分析

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

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

5.2 實驗仿真

為更清晰地體現(xiàn)本文協(xié)議的效率優(yōu)勢，對本文協(xié)議進(jìn)行仿真實現(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)存）。對n元d階多項式進(jìn)行實驗?zāi)M時，實驗的安全參數(shù)設(shè)置為安全參數(shù)|λ|=30 bit，n=4，多項式的次數(shù)設(shè)為d=43 和d=127。

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

圖2 委托計算與直接計算的時間消耗Fig.2 Time consumption of delegation calculation and direct calculation

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

6 結(jié)束語

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