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

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

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

0 概述

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

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

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

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

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

1 預備知識

1.1 全同態(tài)加密

全同態(tài)加密通常包括4 個階段［22］，即預處理階段(SK，PK)←SetupFHE(1λ)、加密階段c←EncryptFHE(PK，m)、解密階段m←DecryptFHE(SK，c)和運算函數(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)表示為隨機的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。設，δ∈?N且rl∈?N，hk=。

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

1.2 多線性映射

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

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 困難性問題假設

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

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

2 安全模型

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

2.1 協(xié)議安全性

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

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

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

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

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

2.2 協(xié)議隱私性

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

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

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

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

3）挑戰(zhàn)階段：詢問結束后，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é)議構造

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

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

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

1）初始化階段

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

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

4 協(xié)議分析

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

4.1 有效性分析

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

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

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

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

4.2 安全性分析

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

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

5 性能分析與實驗仿真

5.1 性能分析

表1 本文協(xié)議各階段的計算復雜度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é)議進行仿真實現(xiàn)。用戶和云服務器的運行環(huán)境分別為Intel?CoreTMi3 Processor（2.4 GH，4 GB 內存）和Intel i5 Processor（3.0 GHz，8 GB 內存）。對n元d階多項式進行實驗模擬時，實驗的安全參數(shù)設置為安全參數(shù)|λ|=30 bit，n=4，多項式的次數(shù)設為d=43 和d=127。

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

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

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

6 結束語

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