外包環境下格上可撤銷的屬性基加密方案*

于金霞，楊超超，張棋超，閆璽璽

河南理工大學 計算機科學與技術學院，河南 焦作 454000

1 引言

2005年，Sahai和Waters[1]在歐洲密碼學會上提出了屬性基加密（attribute-based encryption，ABE）的概念，它用一系列屬性來表示用戶的身份，并在選擇身份安全模型下完成了對方案的證明。2006年，Goyal等人[2]根據加密策略的不同將ABE體制分為密鑰策略屬性基加密（key-policy attribute based encryption，KP-ABE）和密文策略屬性基加密（ciphertext-policy attribute based encryption，CP-ABE）。與傳統的公鑰加密機制相比，屬性基加密具有用戶的動態性、訪問策略的靈活性以及用戶身份的隱私性等優點。這些特點使屬性基加密機制滿足當前大數據時代的需求。為了更好地存儲數據、管理數據和共享數據，數據擁有者可以將大量的密文數據給外包服務提供商，由外包服務提供商來存儲和管理外包的數據，并為數據使用者提供服務。而屬性基加密系統應用中，用戶或用戶的屬性會發生改變，因此屬性撤銷或更新是一個值得深入研究的問題。

針對上述問題，許多可撤銷的屬性基加密被提出。何倩等人[3]將屬性分為動態和靜態屬性，提出支持動靜態屬性撤銷的CP-ABE方案。Nomura等人[4]提出一種可撤銷的多機構CP-ABE方案，不需要為撤銷屬性的用戶更新密鑰。閆璽璽等人[5]提出一種支持用戶撤銷的CP-ABE方案，同時采用半策略隱藏方式實現隱私保護。Xu等人[6]提出一種云環境下支持細粒度訪問控制的可撤銷KP-ABE方案，為云中動態用戶組提供數據共享。王光波等人[7]利用云存儲中心實現屬性撤銷，提出云存儲環境下支持撤銷的CPABE方案。Liu等人[8]提出一種支持解密外包和屬性撤銷的CP-ABE方案，將一些解密計算任務外包給云服務器。趙等人[9]設計出一種無密鑰托管支持撤銷的CP-ABE方案，使用屬性版本密鑰來實現屬性撤銷。Liu等人[10]提出支持解密外包、屬性撤銷和策略更新的CP-ABE方案，通過實驗證明了方法的有效性和實用性。閆璽璽等人[11]設計了數據外包環境下一種支持撤銷的屬性基加密方案。上述方案大多是建立在雙線性對基礎上的，加解密過程中需要多次雙線性對運算，存在計算復雜度較高且無法抵抗量子攻擊等問題。基于格的密碼體制被認為是可以抵抗量子攻擊的，因此近年來基于格論構造的加密方案受到廣泛關注。Boyen[12]提出格上第一個屬性基加密方案，基于線性秘密共享技術（linear secret sharing schemes，LSSS）提出KP-ABE方案，由于該方案采用了通過矩陣級聯方式構造的大維數虛擬加密矩陣，使得效率不高。Wang[13]提出了格上支持多值屬性的屬性基加密方案，方案采用陷門生成算法及抽樣算法構造，通過“與”操作實現訪問控制。針對屬性撤銷問題，張欣威等人[14]提出采用二叉樹實現格上屬性撤銷的CP-ABE方案，但是該方案僅支持門限訪問結構，不支持屬性的即時撤銷。Wang等人[15]也利用二叉樹設計了格上支持撤銷且具有靈活訪問結構的CP-ABE方案，但不支持屬性的即時撤銷。

本文針對已有的格上可撤銷的屬性基加密方案的不足，結合閆璽璽等人[11]提出的CP-ABE方案，設計出一種外包環境下格上可撤銷的密文策略屬性基加密方案，借助數據外包管理服務器，實現屬性的即時撤銷。同時，方案采用訪問樹結構，實現細粒度的訪問策略，表達方式更加靈活。

2 相關知識

2.1 格和格上困難問題

定義1（格）Rm上n個線性無關的向量b1,b2,…,bn由這些向量線性組合構成的向量集合定義為格Λ，即格其中向量組b1,b2,…,bn構成格Λ的一組格基B。

定義2（q-元格）設q是素數，定義q-元格：

定義3（高斯參數）對任意s＞0，以向量c為中心，s為參數的格Λ上的離散高斯分布為，其中ρs,c(x)=exp(-π||x-c||2/s2)本文中||?||表示歐幾里德范數，即二范數。

定義4（判定性誤差學習問題（decisional learning with error，D-LWE））令q為一素數，n為正整數，對于任意α＞0，定義Ψα是一正態分布，其中心為O方差為為Ψα在Zq上的離散分布LWE問題實例是指：對于，判斷挑戰模型O是隨機采樣機還是偽隨機采樣機Os。Os和有如下特征：

Os：輸出帶噪聲的偽隨機樣本，其中是密鑰，是均勻向量，xi是離散分布χ上的噪聲。

(Zq,n,)-LWE問題允許重復詢問挑戰模型O，挑戰模型O隨機利用Os和為敵手生成若干采樣樣品(ωi,vi)，如果對于任意，敵手可以區分樣品來自Os或的優勢是可忽略的，則敵手可以解決判定性(Zq,n,)-LWE問題。

2.2 重要算法

引理1TrapGen(q,n)：對于q=poly(n)，n為正整數，m≥5nlbq存在概率多項式時間算法TrapGen(q,n)生產均勻隨機矩陣，其中ΤA是格的陷門基，且。

引理2SampleLeft(A,B,ΤA,u,σ)：

輸入：秩為n的矩陣，矩陣，格的陷門基，向量和高斯參數。

輸出：令F=A|B，則算法輸出向量，滿足F?e=umodq。

引理3SampleRight(A,B,R,u,σ)：

輸出：令F=A|AR+B則算法輸出向量滿足F?e=umodq。

3 方案定義和安全模型

3.1 數據外包系統架構

傳統的數據外包系統如圖1所示，包括可信屬性授權機構、數據管理服務器、數據服務器、數據擁有者和數據使用者五部分。

Fig.1 Data outsourcing system architecture圖1 數據外包系統架構

（1）可信屬性授權機構：生成系統的主公鑰和主私鑰，以及根據用戶的屬性為用戶生成私鑰。同時負責屬性的更新和撤銷。

（2）數據管理服務器：統一管理外包的數據，對請求訪問的用戶實現訪問控制。

（3）數據服務器：存儲外包的數據。

（4）數據擁有者：對數據進行加密，設置密文的訪問策略，將密文上傳到數據服務器，由數據管理服務器對數據密文進行管理。

（5）數據使用者：對數據服務器上的數據進行申請和正常的訪問。

3.2 算法定義

本方案包括如下7個步驟：

系統初始化Setup(1λ)：輸入安全參數λ、屬性域R，輸出公鑰PK、主私鑰MSK。

密鑰生成KGen(PK,MSK,ω,U) 輸入公共參數PK主私鑰MSK、屬性集合ω、用戶集合U，得到用戶的屬性私鑰SKω。

密鑰加密密鑰生成KEKGen(U)：輸入用戶集合U，輸出用戶的二叉樹KEK。

數據加密Enc(PK,M,T)：輸入公共參數PK、消息M、訪問樹T，輸出密文C。

數據重加密ReEnc(C,U)：輸入密文C、屬性用戶集合U，輸出重加密后的密文C'和頭部信息Hdr。

屬性群密鑰解密UkDec(Hdr.KEK)：輸入頭部信息Hdr用戶的二叉樹KEK輸出屬性用戶群密鑰Ki

數據解密Dec(C',SK,PK) 輸入重加密后的密文C'用戶的私鑰SKω、公共參數PK輸出明文消息M

3.3 安全模型

格上屬性基加密方案的安全性需滿足選擇屬性及選擇明文攻擊下的不可區分性。本方案采用Agrawal等人[16]提出的格上ABE方案的安全模型進行安全性證明，文獻[13]也是基于該安全模型證明的。安全模型由一個模擬器和一個敵手組成，具體游戲過程如下。

初始化：敵手選擇將要挑戰的訪問樹T?，然后交給模擬器。

系統設置：模擬器用Setup(1λ)算法，得到公共參數PP和系統的主私鑰MSK然后將PP發送給敵手。

階段1敵手詢問任何不滿足訪問樹T?的屬性集合的私鑰。依據敵手提交的詢問，模擬生成屬性集合私鑰SK，并運行KEKGen(U)算法計算用戶的二叉樹KEK，將它們傳給敵手。

挑戰：敵手選擇明文M0,M1∈{0,1}，并將其發給挑戰者B模擬器挑戰者隨機選取b∈{0,1} 通過Enc(PK,Mb,T)算法和ReEnc(C,U)算法計算出挑戰密文C'和頭信息Hdr返給攻擊者D并將其發送給敵手。

階段2同階段1。

猜測：敵手提交對b的猜想b'。

若無攻擊者在概率多項式時間內以不可忽略的優勢贏得此游戲，則方案支持選擇屬性和選擇明文攻擊下不可區分性的安全性。

4 方案構造

4.1 系統初始化

Setup(1λ)：輸入安全參數λ，屬性域R，生產公鑰PK和主私鑰MSK。

（1）授權機構利用陷門生成算法TrapGen(1λ)，生成一個均勻隨機矩陣和格的滿秩短基

（2）為每個屬性i∈R，隨機生成矩陣；

4.2 密鑰生成

KGen(PK,MSK,ω,U)：輸入公共參數PK、主私鑰MSK、屬性集合ω、用戶集合U，輸出用戶屬性私鑰SKω。

用戶請求獲得密鑰，認證機構為其生成用戶屬性私鑰。

（1）對于每個屬性i∈?，令計算

（2）輸出用戶私鑰SKω=(ei)i∈ω。

記錄每個屬性i∈R相應的屬性用戶群為Ui，并將其交給數據管理服務器。

4.3 密鑰加密密鑰生成

KEKGen(U)：輸入屬性用戶群U，輸出用戶的二叉樹KEK。

（1）數據管理服務器根據用戶數量生成二叉樹，樹中每個葉子節點表示一個用戶。為樹中的每個節點Vj隨機生成一個密鑰KEKj。Path(ut)表示從二叉樹的代表用戶ut的節點到根節點所經過的路徑節點集合，記為用戶ut的路徑密鑰。

（2）存在一個最小集合可以包含屬性用戶群Ui，記為KEK(Ui) 如圖2，假設存在4個用戶{u1,u2,u3,u4}屬性用戶群Uj={u1,u2,u3} 則KEK(Uj)={KEK2,KEK6}。

Fig.2 KEK binary tree圖2 KEK二叉樹

4.4 加密

數據擁有者獲取公共參數PK，根據訪問樹T，通過Enc(PK,M,T)算法加密消息M。

（1）隨機選擇s←，再選擇一個高斯誤差分布χ并從中選擇誤差參數x0并計算

（2）訪問樹的根節點的值設為s，標記為已分配，其他所有節點標記為未分配。訪問樹的葉子節點代表屬性。從上到下對樹中未標記的非葉子節點運行如下遞歸算法。

若該節點為∧操作，并且該節點的子節點未賦值，則為其孩子節點賦值一個隨機數sk，滿足，并標記為已分配。若該節點為∨操作，且其孩子節點為未分配，則其孩子節點賦值為s，并標記為已分配。若葉子節點對應的屬性為i，則記其對應的值為si。從高斯誤差分布χ中選擇x1,x2∈隨機選取R1,i,R2,i∈{-1,1}m×m計算

4.5 數據重加密

數據重加密ReEnc(C,U)輸入密文C，屬性用戶集合U，輸出重加密后的密文C'和頭部信息Hdr。

（1）數據管理服務器接受密文后，對密文進行重加密處理。隨機選擇一對互逆向量Fi和，計算，則密文

（2）選擇對稱加密算法Ek(x)，其中k為密鑰，x為明文。生成頭信息

當用戶向數據管理服務器發送使用請求時，數據管理服務器將(Hdr,C')發送給用戶。

4.6 數據解密

數據解密階段，先進行屬性群密鑰解密，再進行數據解密。

用戶先進行屬性群密鑰解密UkDec(Hdr.KEK)：輸入頭部信息Hdr，用戶的二叉樹KEK，解密頭信息得到，并更新用戶自己的私鑰

然后進行數據解密Dec(C',SK,PK)。選擇滿足訪問樹的最小屬性集合記為ω'，計算：

5 方案分析

5.1 正確性分析

用戶的屬性發生改變后，數據管理服務器對屬性群密鑰進行更新。用戶收到數據管理服務器發送更新后的(Hdr',C″) 并更新自己的私鑰，然后對密文進行解密，對于i∈f，有：

對于i?f，因此對于i∈ω bi=。在解密時，更新的密鑰和未更新的密鑰運算方式相同，解密算法能夠正常解密。

5.2 安全性證明

初始化：敵手D選擇要攻擊的訪問樹T，把其交給挑戰者B。

設置：挑戰者B收到T后：

（1）挑戰者訪問LWE采樣預言機O獲得樣本

（2）使用陷門生成算法TrapGen(n,q)生成(B,ΤB)。

（3）對于i∈T隨機選擇Ri∈{-1,1}m×m，計算Ai=ARi-B；對于i?T，隨機選擇Ri∈{-1,1}m×m，計算Ai=ARi。

最終，挑戰者B給敵手D返回公共參數PK=(A,B,{Ai}i∈T,u)，保留(ΤB,{Ri}i∈T,v0,vu)。

階段1敵手D可以詢問不滿足訪問樹T的屬性集ω。挑戰者B接收敵手D的詢問，然后運行算法SampleRight(A,B,Ri,ΤB,σ,u)→ei，得到敵手屬性私鑰SKω=(ei)i∈ω。用KEKGen(U)算法計算出用戶的二叉樹KEK。挑戰者B把屬性私鑰SKω和KEK交給敵手D。

挑戰：敵手D選擇明文M0,M1∈{0,1}發給挑戰者B。挑戰者隨機選取b∈(0,1)，對Mb進行加密，計算，得到密文C=(C0,{C1,i,C2,i}i∈ω)。隨機選擇一對互逆向量Fi和，計算，對密文進行重加密處理，得到。選擇對稱加密算法Ek(x)，其中k為密鑰，x為明文，生成頭信息Hdr=。挑戰者B將密文C'和頭信息Hdr返給攻擊者D。

階段2同階段1。

猜測：敵手提交對b的猜想b'。模擬器根據敵手對b的猜想b'挑戰定義4中的LWE問題，如果b'=b，則輸出O=Os此時敵手的優勢Pr[b'=b|O=Os]=1/2+ε如果b'≠b則輸出O=Os' 此時敵手的優勢Pr[b'≠b|O=Os']=1/2因此敵手能以可忽略的優勢區分密文C'和Zq上的均勻隨機分布，也就是說敵手若能以不可忽略的概率猜出b則可以以相同的優勢解決(Zq,n,)-LWE問題。

5.3 性能分析

將本文方案從訪問結構、公鑰長度、私鑰長度、密文長度、是否支持屬性撤銷以及是否支持屬性即時撤銷等方面與相關方案進行對比，如表1。其中q、n、m為格上的相關參數（根據引理1中定義規定，m≥5nlbq），s代表系統屬性總數量，Au代表用戶屬性的數量，Ac代表加密時使用的屬性數量。t表示解密時所需的最小屬性集合中屬性的個數，O表示計算復雜度。

從表1可以看出，本文方案比文獻[13-14]少了nmlbq，比文獻[15]少了4snmlbq+(2s-2m-1)nlbq，由于s代表系統屬性總數量，值較大，因此本文方案公鑰長度有了明顯的縮短。用戶私鑰長度方面，本文方案和文獻[13]保持一樣，是文獻[14-15]私鑰長度的50%。密文長度方面，文獻[13]僅和m相關，和加密訪問策略屬性無關，達到了最優的長度，但其功能方面并未考慮屬性撤銷。和文獻[15]相比，本文方案密文長度具有明顯的優勢，縮短了(Ac+1)lbq。與文獻[14]具有相同的密文長度，但本文方案支持屬性的即時撤銷。因此，結合公鑰長度、私鑰長度、密文長度等參數，本文方案在通信代價方面具有優勢。

Table 1 Comparison of related papers表1 相關方案對比

功能方面，文獻[13]不支持屬性撤銷，文獻[14-15]和本文方案支持屬性撤銷，但是文獻[14-15]不支持屬性的即時撤銷，本文方案支持屬性的即時撤銷。訪問結構上，文獻[13-14]都采用門限訪問結構，訪問結構表達不夠靈活。文獻[15]采用析取范式訪問結構，本文方案采用訪問樹結構，都支持更為靈活的訪問策略。

綜上，本文所提出的方案在性能方面得到了很大的提升，在功能方面更加完善，支持屬性的即時撤銷，更加滿足外包環境中的應用需求。

6 結束語

本文提出一種外包環境下格上可撤銷的密文策略屬性基加密方案。方案采用訪問樹結構，訪問策略更靈活。同時，方案實現了屬性即時撤銷，滿足社交網絡平臺等云環境的應用需求。方案被證明滿足選擇屬性及選擇明文攻擊下安全。基于理想格的加密方案具有更高的加解密效率，下一步將對構造基于理想格的高效可撤銷屬性基加密方案進行研究。