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

白 平，張 薇，王緒安

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

0 引言

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

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

該方案將同態(tài)解密思想(homomorphic decryption)運(yùn)用到Catalano等[8]提出的基于算術(shù)電路實(shí)用同態(tài)消息認(rèn)證方案中，構(gòu)造了云環(huán)境下基于運(yùn)算電路的同態(tài)認(rèn)證方案。相比文獻(xiàn)[8],方案在復(fù)雜度上有所增長。然而，本方案可以進(jìn)行任意次乘法同態(tài)而不會增大驗(yàn)證標(biāo)簽大小，實(shí)現(xiàn)了更高效的同態(tài)認(rèn)證。另外，可以提供不同服務(wù)器之間數(shù)據(jù)完整性和有效性的驗(yàn)證，增強(qiáng)了用戶外包數(shù)據(jù)的安全性。同態(tài)消息認(rèn)證允許用戶在不知道私鑰情況下對數(shù)據(jù)消息進(jìn)行驗(yàn)證，從而很大程度上方便了用戶。隨著同態(tài)認(rèn)證受到越來越多的關(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是運(yùn)算函數(shù),τ1,τ2,…τn∈{0,1}*是二進(jìn)制串。在標(biāo)簽函數(shù)P1,P2,…Pt和函數(shù)g:Mt→M已知情況下，標(biāo)簽函數(shù)也可表示為P*=g(P1,P2,…,Pt)。文獻(xiàn)[6]的方案中限制了標(biāo)簽函數(shù)在布爾電路f:{0,1}n→ {0,1}中，本文方案中將其擴(kuò)展到運(yùn)算電路中，為f:Mn→M。

1.2 同態(tài)消息運(yùn)算認(rèn)證方案

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

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

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

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

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

1.3 半誠實(shí)模型

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

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

1.4 同態(tài)解密

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

圖1 增強(qiáng)驗(yàn)證電路示意圖

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

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

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

Setup 挑戰(zhàn)者B運(yùn)行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運(yùn)算TagGen(sk,τ,m)生成新的驗(yàn)證標(biāo)簽σ← TagGen(sk,t,m)，同時更新T=T∪(τ,m)。

Verification queries 敵手A發(fā)送詢問(m,P,σ)給挑戰(zhàn)者B，挑戰(zhàn)者B運(yùn)用Ver(sk,m,P,σ)進(jìn)行驗(yàn)證，輸出結(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)認(rèn)證方案是安全的。

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

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

圖2 方案運(yùn)行模擬示意圖

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(1)

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

4 方案的分析

4.1 安全性分析

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

命題1 令λ,n∈N,Π表示階為q的有限域M上的運(yùn)算電路f:Mn→M的集合,其中電路f的深度最大為d且有d/q<1/2。可以得出如下推斷：對于f∈Π存在這樣的概率算法：?μ∈Mn,y∈M使得f(μ)=y的概率至少為1-2-λ。

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

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

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

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

Q·2-λ

(2)

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

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

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

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

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

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

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

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

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

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

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

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

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

如果事件Bad4在游戲4中發(fā)生，挑戰(zhàn)者B可能會對某些驗(yàn)證詢問提供不同的回應(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隨機(jī)選擇的變量x、參數(shù)γτ和敵手A隨機(jī)選擇的參數(shù)所評估代替。

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

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

(4)

(5)

(6)

(7)

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

(8)

進(jìn)而可以得到上限值：

(9)

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

(10)

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

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

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

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

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

4.2 性能分析

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

驗(yàn)證標(biāo)簽大小的增長主要來源于同態(tài)乘法的運(yùn)算，本文中增強(qiáng)電路的輸入可以表示成多項(xiàng)式函數(shù)，故電路的深度可以用輸入位的對稱多項(xiàng)式來衡量本文假設(shè)方案中增強(qiáng)電路中輸入的驗(yàn)證標(biāo)簽多項(xiàng)式分別表示為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)分別表示電路輸入，那么如何確定這兩個多項(xiàng)式相乘結(jié)果的次數(shù)呢？運(yùn)用如下結(jié)論：

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

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

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

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

進(jìn)位：

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

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

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

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

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

5 結(jié)語

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