云環境下基于運算電路的同態認證方案

白 平，張 薇，王緒安

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

0 引言

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

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

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

1 預備知識

1.1 標簽函數

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

1.2 同態消息運算認證方案

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

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

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

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

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

1.3 半誠實模型

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

那么協議η在靜態半誠實敵手A存在情況下是安全的計算函數g。

1.4 同態解密

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

圖1 增強驗證電路示意圖

2 安全模型、結構模型及實例模型分析

2.1 云環境下基于運算電路的同態認證方案安全模型

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

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

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

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

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

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

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

2.2 云環境下基于運算電路的同態認證方案結構模型

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

圖2 方案運行模擬示意圖

2.3 云環境下基于運算電路的同態認證方案實例模型

云環境下外包數據的存儲主要由三種實體結構組成：普通用戶、云服務器、可信第三方。

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

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

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

圖3 傳輸數據實例模型

3 云環境下基于運算電路的同態認證方案

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

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

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

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

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

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

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

(1)

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

4 方案的分析

4.1 安全性分析

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

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

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

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

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

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

Q·2-λ

(2)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(3)

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

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

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

(4)

(5)

(6)

(7)

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

(8)

進而可以得到上限值：

(9)

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

(10)

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

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

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

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

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

4.2 性能分析

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

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

乘兩個t位數相當于加t位數，輸出位是輸入位的一個2次多項式：

t個數相加：3個數相加得到2個數相加，輸出位是關于輸入位的一個次數最多為2次的多項式：

那么t個數運用這個性質經過log3/2t次相加后得到兩個數，輸出位的次數為2log3/2t=tlog3/22=t1.71。

兩個t位數相加：

進位：

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

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

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

表1 關鍵詞索引結構

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

5 結語

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