云環(huán)境下基于運算電路的同態(tài)認證方案

白 平，張 薇，王緒安

(1.武警工程大學(xué) 密碼工程學(xué)院，西安 710086； 2.武警工程大學(xué) 信息安全保密重點實驗室，西安 710086)

0 引言

隨著云計算技術(shù)[1]的不斷發(fā)展，利用 “云端”存儲數(shù)據(jù)越來越受到廣大用戶的青睞；與此同時，外包給 “云端”的數(shù)據(jù)如何確保其安全性和可靠性同樣引起了人們的關(guān)注。目前，對于外包數(shù)據(jù)的安全性已經(jīng)通過各種加密方式[2]進行了有效的解決。然而，如何對外包數(shù)據(jù)的計算結(jié)果進行有效驗證仍是當(dāng)前比較棘手的問題，見文獻[3-5]。本文的研究重點也是側(cè)重于如何進行外包數(shù)據(jù)的驗證?？紤]如下一個具體的應(yīng)用環(huán)境：假設(shè)用戶把數(shù)據(jù)m1,m2,…,mn外包給“云端”進行存儲，隨后用戶想要 “云端”對這些數(shù)據(jù)進行某種運算如R(m1,m2,…,mn) →m。存在的問題是用戶如何確保云服務(wù)器能夠正確執(zhí)行計算指令呢？一個最直觀的方法是云服務(wù)器把這些數(shù)據(jù)回傳給用戶，由用戶自己計算，然后與服務(wù)器計算的結(jié)果進行對比。這種方法雖然簡單卻極大地削弱了外包的價值，增加了用戶的開銷花費。此外，由于不同的服務(wù)器提供不同的服務(wù)功能，用戶可能會在服務(wù)器之間進行數(shù)據(jù)傳輸以保證用戶利益最大化，但是服務(wù)器是一個不可完全信任的機構(gòu)，用戶數(shù)據(jù)可能會因為各種原因被惡意篡改甚至丟失，給用戶帶來了極大的安全隱患，這就迫切需要去尋找一個安全高效的機制來完成外包計算的驗證以及用戶數(shù)據(jù)在不同服務(wù)器傳輸過程中的完整性。

同態(tài)消息運算認證(Homomorphic Message AuthentiCator, HomMAC)最初由Gennaro等[6]提出。相比其他驗證方法如PDP(Provable Data Possession)[7]，同態(tài)消息運算認證具有兩個獨特的優(yōu)點：1)允許任何人在不知道私鑰的情況下認證待驗證的消息；2)允許擁有私鑰用戶在不知道原始輸入情況下驗證計算結(jié)果的正確性。

該方案將同態(tài)解密思想(homomorphic decryption)運用到Catalano等[8]提出的基于算術(shù)電路實用同態(tài)消息認證方案中，構(gòu)造了云環(huán)境下基于運算電路的同態(tài)認證方案。相比文獻[8],方案在復(fù)雜度上有所增長。然而，本方案可以進行任意次乘法同態(tài)而不會增大驗證標(biāo)簽大小，實現(xiàn)了更高效的同態(tài)認證。另外，可以提供不同服務(wù)器之間數(shù)據(jù)完整性和有效性的驗證，增強了用戶外包數(shù)據(jù)的安全性。同態(tài)消息認證允許用戶在不知道私鑰情況下對數(shù)據(jù)消息進行驗證，從而很大程度上方便了用戶。隨著同態(tài)認證受到越來越多的關(guān)注，涌現(xiàn)出了許多這方面研究成果[9-11]。

1 預(yù)備知識

1.1 標(biāo)簽函數(shù)

標(biāo)簽函數(shù)(labeled program)由Gennaro等[6]提出。標(biāo)簽函數(shù)定義為P=(f,τ1,τ2,…,τn)，其中f:Mn→M是運算函數(shù),τ1,τ2,…τn∈{0,1}*是二進制串。在標(biāo)簽函數(shù)P1,P2,…Pt和函數(shù)g:Mt→M已知情況下，標(biāo)簽函數(shù)也可表示為P*=g(P1,P2,…,Pt)。文獻[6]的方案中限制了標(biāo)簽函數(shù)在布爾電路f:{0,1}n→ {0,1}中，本文方案中將其擴展到運算電路中，為f:Mn→M。

1.2 同態(tài)消息運算認證方案

同態(tài)消息運算認證(HomMAC)方案主要由4個算法構(gòu)成,具體如下。

KeyGen(1λ) 輸入安全參數(shù)λ，輸出私鑰sk和解密密鑰ek。

Auth(sk,τ,m) 輸入私鑰sk，消息m∈Μ和對應(yīng)消息標(biāo)記τ，輸出驗證標(biāo)簽σ。

Ver(sk,m,P,σ) 輸入私鑰sk、消息m、驗證標(biāo)簽P=(f,τ1,τ2,…,τn)和標(biāo)簽函數(shù)P=(f,τ1,τ2,…,τn)，則驗證結(jié)果正確時輸出為1；反之，輸出為0。

Eval(ek,f,σ) 輸入解密密鑰ek，運算電路f:Mn→M和驗證標(biāo)簽向量σ=(σ1,σ2,…,σn)，輸出新驗證標(biāo)簽σ。

1.3 半誠實模型

定義1 半誠實模型：設(shè)g=(g1,g2)是確定性函數(shù)，如果存在多項式時間的方案Sim1和Sim2，即：

那么協(xié)議η在靜態(tài)半誠實敵手A存在情況下是安全的計算函數(shù)g。

1.4 同態(tài)解密

同態(tài)解密方法被廣泛應(yīng)用于降低噪聲的各種場景中。當(dāng)進行同態(tài)密文乘法運算時，密文大小會被迅速放大，從而制約了密文操作次數(shù)，影響了同態(tài)效率。在實際云數(shù)據(jù)傳輸過程中，需要對傳輸數(shù)據(jù)進行驗證。然而，驗證標(biāo)簽的大小會隨同態(tài)乘法運算被放大，影響驗證的效率。在本方案中，對同態(tài)乘法運算后的密文作同態(tài)解密操作，則可以將驗證標(biāo)簽的大小降低到接近初始狀態(tài)時的大小，從而達到任意次密文運算的目的。方案中設(shè)置了如圖1所示的電路，該電路中包含一個加密電路和一個解密電路，輸入到該電路的多項式驗證標(biāo)簽運用某種算法協(xié)議進行一系列的加解密操作后可以降低多項式驗證標(biāo)簽的次數(shù)。為了便于進行下一次運算，還在電路中增加一個門電路，統(tǒng)稱為增強驗證電路Ω。

圖1 增強驗證電路示意圖

2 安全模型、結(jié)構(gòu)模型及實例模型分析

2.1 云環(huán)境下基于運算電路的同態(tài)認證方案安全模型

在同態(tài)消息運算認證(HomMAC)中，敵手A和挑戰(zhàn)者B進行博弈游戲，具體游戲HomUF-CMAA,HomMAC(λ)過程如下:

Setup 挑戰(zhàn)者B運行KeyGen(1λ)獲得了私鑰sk和解密密鑰ek，而后發(fā)送解密密鑰ek給敵手A，同時，初始化列表T=?。

Tag queries 敵手A不間斷地詢問消息標(biāo)記τ，具體分以下三種情況：1)假如敵手A發(fā)送重復(fù)詢問(τ,m)∈T給挑戰(zhàn)者B,則挑戰(zhàn)者B發(fā)送相同的答復(fù)。2)假如敵手A發(fā)送詢問(τ′,m)∈T給挑戰(zhàn)者B,即用同一個標(biāo)記τ標(biāo)記了兩個不同消息m和m′，則挑戰(zhàn)者B忽略此詢問。3)假如敵手A發(fā)送詢問(τ,m)?T給挑戰(zhàn)者B，則挑戰(zhàn)者B運算TagGen(sk,τ,m)生成新的驗證標(biāo)簽σ← TagGen(sk,t,m)，同時更新T=T∪(τ,m)。

Verification queries 敵手A發(fā)送詢問(m,P,σ)給挑戰(zhàn)者B，挑戰(zhàn)者B運用Ver(sk,m,P,σ)進行驗證，輸出結(jié)果為1或者0。

1)偽造1：P*不是定義在T上。

2)偽造2：P*定義在T上,但是m*不是正確的輸出，即m*≠f*({mj}(τj,mj)∈T)。

若上述游戲概率可表示為Pr[HomUF-CMAC,HomMAC(λ)=1]≤ε(λ)，其中ε(λ)是一個可忽略的函數(shù)，則可以判定該同態(tài)認證方案是安全的。

2.2 云環(huán)境下基于運算電路的同態(tài)認證方案結(jié)構(gòu)模型

當(dāng)兩個多項式驗證標(biāo)簽σi(i=1,2)進行同態(tài)乘法運算時，首先會輸入到一個乘法門電路中，經(jīng)過乘法門電路的作用后，驗證標(biāo)簽的大小會被迅速放大。為了降低驗證標(biāo)簽的大小，將其結(jié)果輸入到增強驗證電路Ω中，通過增強驗證電路中加密電路和解密電路的共同作用，輸出新的密文驗證標(biāo)簽大小會接近于一個新鮮密文大小，從而保持了驗證標(biāo)簽的大小在低水平范圍內(nèi)。反復(fù)遞歸此過程，則可以達到任意次密文運算的目的。

圖2 方案運行模擬示意圖

2.3 云環(huán)境下基于運算電路的同態(tài)認證方案實例模型

云環(huán)境下外包數(shù)據(jù)的存儲主要由三種實體結(jié)構(gòu)組成：普通用戶、云服務(wù)器、可信第三方。

普通用戶 數(shù)據(jù)存儲計算能力相對較弱，傾向于把一些復(fù)雜的數(shù)據(jù)資源交給云服務(wù)器來存儲或者計算，但希望這些數(shù)據(jù)不能被云服務(wù)器竊取或者篡改。

云服務(wù)器 有大量的存儲和計算能力，能為用戶提供云存儲和計算服務(wù)，但是云服務(wù)器上的數(shù)據(jù)可能會遭受黑客的惡意攻擊，所以必須對存儲數(shù)據(jù)進行驗證以確保安全性。

第三方 作為用戶與云服務(wù)器的中間媒介，第三方(Third Party Administrator, TPA)將得到的最終結(jié)果反饋給事先指定用戶，確保傳輸數(shù)據(jù)的安全性。

圖3 傳輸數(shù)據(jù)實例模型

3 云環(huán)境下基于運算電路的同態(tài)認證方案

1)同態(tài)加法運算。取d=max(d1,d2)，則通過計算y(z)=y(1)(z)+y(2)(z)，得到新多項式驗證標(biāo)簽σ的系數(shù)為(y0,y1,…,yd)。

3)帶變量的同態(tài)乘法運算。取d=di(i=1,2)，另一個標(biāo)簽為變量c，則通過計算y(z)=c·y(1)(z)，得到新多項式驗證標(biāo)簽σ的系數(shù)σ=(y0,y1,…,yd)。

Homomorphic_decryption(σ，pk，skv) 將GateEval(ek,g,σ1,σ2)生成的新多項式驗證標(biāo)簽σ輸入到增強驗證電路Ω中，利用公鑰pk對新驗證標(biāo)簽σ進行加密，而后輸入解密電路中用私鑰skv進行解密，該解密電路輸出的密文相當(dāng)于一個新鮮密文，它的大小會遠遠小于之前的密文大小。

Ver(sk,m,P,σ) 定義P=(f,τ1,τ2,…,τn)為標(biāo)簽函數(shù)，驗證標(biāo)簽為σ=(y0,y1,…,yd)以及m∈Zp。具體驗證過程如下：

1)如果y0≠m，則返回0；否則進行下一步。

2)令消息標(biāo)記為τ，計算γτ=FK(τ)。

3)對步驟2)中的每一個γτi(i=1,2,…,n)，計算f(γτ1,γτ2,…,γτn) →ρ。而后運用x計算如下等式是否成立：

(1)

若為真，則輸出為1；否則輸出為0。

4 方案的分析

4.1 安全性分析

本方案的安全性依賴于同態(tài)認證的安全性以及增強驗證電路Ω的安全性。同態(tài)認證的安全性可以利用Schwartz等[12]方案中的命題1進行證明，增強驗證電路的安全則可以在半誠實模型下得以證明。

命題1 令λ,n∈N,Π表示階為q的有限域M上的運算電路f:Mn→M的集合,其中電路f的深度最大為d且有d/q<1/2?？梢缘贸鋈缦峦茢啵簩τ趂∈Π存在這樣的概率算法：?μ∈Mn,y∈M使得f(μ)=y的概率至少為1-2-λ。

定理1 如果F是一個偽隨機函數(shù)，則方案的同態(tài)消息認證是安全的。

為了證明方案的正確性，定義一個由敵手A執(zhí)行的實驗游戲Gi(i=1,2,…,4)，并最終輸出1。

游戲G0輸入驗證詢問(m,P,σ),為了辨別標(biāo)簽函數(shù)P是否被定義在T上，挑戰(zhàn)者B使用命題1進行概率測試，則任何敵手A進行Q次驗證詢問后可得到如下不等式：

‖Pr[HomUF-CMAA,HomMAC(λ)]-Pr[G0(A)]‖≤

Q·2-λ

(2)

游戲G1同游戲G0中的博弈類似，所不同的是游戲G1中所用的是真正隨機函數(shù)R:{0,1}*→Zp，并隨機產(chǎn)生γτ∈Zp。

游戲G2首先，對于所有驗證詢問(m,P,σ=(y0,y1,…,yd))，如果y0≠m則輸出為0。其次，對于所有的驗證詢問(m,P,σ)，如果P不是被定義在T上，則挑戰(zhàn)者B執(zhí)行以下步驟：

1)對于每一個τi，如果(τi,·)?T,則計算γτ1←R(τi)。

2) 使用算法Ver(sk,m,P,σ)計算ρ的值。

游戲G3對于所有驗證詢問(m,P,σ)，其中P=(f,τ1,τ2,…,τn)定義在T上，挑戰(zhàn)者B執(zhí)行以下操作：

游戲G4設(shè)定bad是表示“false”的一個標(biāo)識符，當(dāng)挑戰(zhàn)者B接收到驗證詢問(m,P,σ)后，如果滿足以下兩個條件：

1)按照驗證詢問(m,P,σ)的要求，挑戰(zhàn)者B計算出了Z的值。

2)計算的輸出為Z=0 modp,則挑戰(zhàn)者B輸出1，并且設(shè)定bad → True。

定義bad4表示游戲G4中bad → True事件，由于所有偽造的驗證詢問只能是游戲G3中的1)或者2)，故任何敵手贏得游戲G4的概率為0，即Pr|G4|=0。

為了證明定理1,需要證明以下引理:

引理1的證明類似于偽隨機函數(shù)的安全性證明。

引理2 Pr|G2|≡Pr|G3|

引理3 Pr[G3]-Pr[G4]≤Pr[Bad4]

如果事件Bad4在游戲4中發(fā)生，挑戰(zhàn)者B可能會對某些驗證詢問提供不同的回應(yīng)，因此，有Pr[G3]-Pr[G4]≤Pr[Bad4]。

證明 對于j=1,2，…,Q,令Bj表示這樣一個事件:敵手A詢問了j次之后使得bad → True，則可以得出如下結(jié)論:

(3)

其中:證明的關(guān)鍵之處在于Pr[Bj]的概率由挑戰(zhàn)者B隨機選擇的變量x、參數(shù)γτ和敵手A隨機選擇的參數(shù)所評估代替。

定義(m,P,σ)表示第j次驗證詢問,根據(jù)P是否定義在T上,Bj有以下兩種可能性:

Pr[Bj]=Pr[Zj=0|Z1≠0∧Z2≠0∧…∧Zj-1≠0]

(4)

(5)

(6)

(7)

最后，將式(6)和(7)運用到式(5)中可推導(dǎo)出如下不等式：

(8)

進而可以得到上限值：

(9)

綜上所述，可以證明定理1：

(10)

本方案中增強驗證電路的安全性建立在半誠實模型下，參與方(真實方和模擬方)誠實的執(zhí)行相關(guān)算法協(xié)議，假設(shè)真實方與模擬方分別擁有多項式向量集合M*=(M1,M2,…,Mn)，S*=(S1,S2,…,Sn)，模糊匹配的操作對象就是針對M*和S*中的某兩個多項式向量進行作用。

在方案證明過程中為了標(biāo)識方便，將直接使用M和S作為向量，假設(shè)真實視圖中對向量M輸出為BFM,模擬視圖中對向量S輸出為CFS,將BFM和CFS進行作用產(chǎn)生交集BCFM∩S,記錄交集中匹配成功的個數(shù)。如果個數(shù)大于或者等于事先設(shè)定的門限值t，則真實視圖和模擬視圖具有不可區(qū)分性，反之，二者可區(qū)分。

定理2 設(shè)M、S分別是預(yù)定義的域，g∩是交集函數(shù)，|g∩|為交集中匹配成功的個數(shù)，那么M、S匹配的表達式為：

true={g∩(M,S)≥t}={|gM(M,S),gS(M,S)|≥t}={|(M∩S,∧)≥t|}

證明 假定方案中所用的不經(jīng)意傳輸(Obliviously Transfer, OT)協(xié)議是安全的，則真實發(fā)送者和模擬發(fā)送者的模擬器是存在的，現(xiàn)在利用這兩個模擬器作為子程序構(gòu)建出新的模擬器。

4.2 性能分析

在同態(tài)認證過程中，當(dāng)對多項式驗證標(biāo)簽進行運算時，驗證標(biāo)簽的大小會被迅速放大，影響認證效率，而這種增加主要來自于同態(tài)乘法運算。然而，如果對每一次運算后的驗證標(biāo)簽作一次同態(tài)解密運算，則可以得到一個類似于新鮮密文大小的新驗證標(biāo)簽，從而保證了驗證標(biāo)簽的大小維持在一個低水平范圍內(nèi)。本方案中較Catalano等[8]提出的基于算術(shù)電路可實用的同態(tài)消息認證方案最大的不同在于引進了一個Homomorphic decryption 算法,其作用在于將驗證標(biāo)簽的大小降低到類似新鮮密文的大小，從而保證了驗證標(biāo)簽大小被保持在一個低水平范圍內(nèi)。Catalano等提出的方案中存在的最大缺陷是多項式驗證標(biāo)簽的大小會隨電路的深度增加而遞增，在他們的方案中通過限制電路深度克服了這一缺陷。然而，他們的解決辦法是以犧牲下列條件為代價：事先固定電路所能運算的最大深度值D。在本文方案中不需要事先設(shè)定電路的深度值，在每次同態(tài)乘運算之后自動調(diào)動 Homomorphic decryption算法來降低標(biāo)簽系數(shù)，從而可以進行任意次驗證計算。本方案中存在的問題是每次調(diào)用 Homomorphic decryption算法勢必增加方案的復(fù)雜度。下面說明方案的復(fù)雜度。

驗證標(biāo)簽大小的增長主要來源于同態(tài)乘法的運算，本文中增強電路的輸入可以表示成多項式函數(shù)，故電路的深度可以用輸入位的對稱多項式來衡量本文假設(shè)方案中增強電路中輸入的驗證標(biāo)簽多項式分別表示為y(x1)=a1+a2(x1)2+a3(x1)3和y(x2)=b1+b2(x2)2+b3(x2)3，其中系數(shù)(a1,a2,a3)和(b1,b2,b3)分別表示電路輸入，那么如何確定這兩個多項式相乘結(jié)果的次數(shù)呢？運用如下結(jié)論：

乘兩個t位數(shù)相當(dāng)于加t位數(shù)，輸出位是輸入位的一個2次多項式：

t個數(shù)相加：3個數(shù)相加得到2個數(shù)相加，輸出位是關(guān)于輸入位的一個次數(shù)最多為2次的多項式：

那么t個數(shù)運用這個性質(zhì)經(jīng)過log3/2t次相加后得到兩個數(shù)，輸出位的次數(shù)為2log3/2t=tlog3/22=t1.71。

兩個t位數(shù)相加：

進位：

可以類推出：輸出位的次數(shù)最多為t。

綜上所述：乘兩個t位數(shù)的次數(shù)最多為2t1.71t=2t2.71。

Catalano等[13]運用分級編碼的思想，構(gòu)造了一個基于算術(shù)電路擴展的同態(tài)認證方案，下面將分別在是否支持密文的復(fù)合度、驗證標(biāo)簽大小、電路深度大小以及是否支持無上界的驗證詢問方面與文獻[6,8,13]進行比較。具體的比較結(jié)果如表1所示。

表1 關(guān)鍵詞索引結(jié)構(gòu)

通過表1可以得出，本方案相比文獻[6,8,13]，克服了它們部分缺點，例如相比GW13方案，本方案可以支持無上界的驗證詢問。不足之處是復(fù)合度有所減弱。相比CF13-2方案，本方案在電路深度進行優(yōu)化，可以進行深度為任意值的電路，在很大程度上增強了用戶數(shù)據(jù)驗證的實用性和可操作性。

5 結(jié)語

本文將同態(tài)解密方法運用到同態(tài)認證方案中，構(gòu)造了云環(huán)境下基于運算電路的同態(tài)認證方案。通過引入同態(tài)解密方法，方案可以達到對密文作任意功能的運算，進一步提高了云數(shù)據(jù)認證的效率，增強了用戶數(shù)據(jù)的安全性。由于方案中沒有討論增強驗證電路的深度是否在Permitted Function集合中，故無法確定方案為全同態(tài)認證。進一步的工作是探索方案是否為全同態(tài)認證，從而構(gòu)造效率更高、更為實用的云環(huán)境下全同態(tài)數(shù)據(jù)認證方案。