理想格上支持訪問樹的屬性基加密方案

于金霞，楊超超，楊麗偉，湯永利，閆璽璽

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

0 引 言

屬性基加密與傳統的公鑰加密相比，具有用戶的動態性、訪問策略的靈活性以及用戶身份的隱私性等優點。2005年，Sahai和Waters[1]在歐洲密碼學會上提出了屬性基加密的概念，它用一系列屬性來表示用戶的身份，由屬性集合和訪問結構之間的匹配關系確定其解密能力，并給出一個支持門限結構的屬性基加密(attribute-based encryption，ABE)方案。2006年，Goyal等[2]根據加密策略的不同，將ABE體制劃分為2類：①密鑰策略ABE(key-policy attribute based encryption，KP-ABE)，其特點是將訪問結構嵌入到密鑰中，密文中包含特定屬性集；②密文策略ABE(ciphertext-policy attribute based encryption，CP-ABE)，它是將訪問結構嵌入到密文中，密鑰中包含特定屬性集，當屬性集和訪問結構匹配時，即可解密。同時，作者提出支持樹形訪問策略的KP-ABE方案，和門限訪問結構相比較，樹形訪問結構更為精細，表達能力更為豐富，邏輯操作更具有現實意義。2007年，Bethencourt等[3]提出第一個CP-ABE方案，訪問結構采用門限結構。相對于密鑰策略屬性基加密機制而言，密文策略的屬性基加密體制更適用于動態場景，發送者可以設計訪問結構，控制接收者的范圍。同年，Ostrovshy[4]提出包含非門訪問結構的屬性基加密方案，更加豐富了訪問策略。2011年，Waters[5]利用線性秘密共享方案(linear secret sharing schemes，LSSS)提出了一種新的密文策略屬性基加密方案。和樹形訪問結構相比，LSSS擁有相同的功能，而樹形訪問結構更為直觀，LSSS中秘密分享矩陣設計較復雜。屬性基加密機制憑借其訪問控制的靈活性等特點成為研究熱點，同時，屬性基加密機制也被廣泛應用，各種相關ABE方案[6-8]相繼被提出。但是，上述方案大多是建立在雙線性對基礎上的，加解密過程中需要多次雙線性對運算，存在計算復雜度較高且無法抵抗量子攻擊等問題。

基于格的密碼體制被認為可以抵抗量子攻擊，而且格上多數運算屬于線性運算，所以運算效率高。因此，近年來基于格論構造的加密方案受到廣泛關注。格上存在許多困難問題，如最短向量問題(shortest vector problem，SVP)等。2012年，Boyen[9]基于標準格上LWE(learning with error)問題，將LSSS應用于格上屬性基加密方案中，提出第一個格上KP-ABE方案，滿足隨機預言模型下安全。同年，Zhang等[10]利用抽樣算法提取屬性私鑰，密文中嵌入門限訪問結構，提出第一個基于LWE難題的格上CP-ABE方案。2013 年，Wang[11]提出了標準模型下格上的密文策略的屬性基加密方案，該方案實現了多值屬性上的門限訪問結構，并在 LWE 假設下證明了方案的安全性。相較于標準格上的 LWE 密碼體制，基于理想格上R-LWE(learning with error over ring)的方案具有密鑰尺寸小、加密效率高的優勢。2014年，Zhu等[12]將門限訪問策略引入理想格上，提出理想格上基于R-LWE問題的KP-ABE方案，并證明其滿足選擇明文攻擊安全。2015年，Tan等[13]提出基于R-LWE問題的理想格上支持LSSS訪問策略的CP-ABE方案。2017年，Chen等[14]指出Zhu等[12]和Tan等[13]的方案安全性證明不能滿足選擇明文攻擊安全。閆璽璽等[15]采用LSSS訪問結構提出理想上的多機構CP-ABE方案。同年，Wang等[16]提出有效的基于R-LWE選擇密文安全的加密方案。

目前，格上屬性基加密方案的研究還不太完善，存在許多待解決的問題?，F有的一些方案僅支持單一的訪問策略，無法支持靈活的表達方式。本文利用訪問樹結構和理想格上R-LWE問題提出一種支持任意訪問結構的密文策略屬性基加密方案，主要創新在于：訪問樹結構構造簡單且支持與、或、門限操作，能實現靈活的訪問策略。本文將訪問樹結構作為訪問策略應用到格上屬性基加密方案中，使訪問結構更為靈活多樣。

1 相關知識

1.1 格

1.2 理想格

定義4環Zn的理想I又是格Zn的子格，稱這個格為格Zn的理想格。具體定義如下：多項式環Z[x]/(f(x))，若滿足以下3條性質。

1)f(x)的首相(最高次的項)系數為1；

2)在Z上是不可約的；

3)n的多項式函數用poly(n)表示，對環Z[x]上的任意多項式g(x)和h(x)，都有‖g(x)h(x)·modf(x)‖

1.3 樹形訪問結構

樹形訪問結構T，根節點記為root，非葉子節點記為node。樹中節點node的子節點個數記為numnode，節點node的父節點表示為parent(node)。樹中每個非葉子節點都有門限值knode∈(0,numnode]。當knode=1時，該節點代表或門；當knode=numnode時，該節點代表與門。樹中葉子節點node代表一個真實的屬性，記為attr(node)。樹中非葉子節點node的所有子節點用1到numnode進行編號，用index(node)返回。

Troot代表根節點為root的訪問樹，Tnode代表根節點為node的訪問樹。設置布爾函數Tnode(γ)，其中,γ代表屬性集合，當且僅當屬性集合γ滿足訪問樹Tnode時，有Tnode(γ)=1。若node為非葉子節點，令node′為node的子節點，當且僅當有knode以上個子節點的Tnode′(γ)=1時，節點node的Tnode(γ)=1。若node為葉子節點，當且僅當attr(node)∈γ時，Tnode(γ)=1。

圖1為訪問樹結構的例子，圖1中,節點a的門限值ka=2與子節點個數相同表示與門，節點c的門限值kc=1，即當有一個子節點滿足即可，表示或門。樹中葉子節點b，f和c分別代表屬性1、屬性2和屬性3，當具有屬性1和屬性2或者屬性1和屬性3時才滿足上述訪問樹。在方案中，根據訪問樹的設計可以實現靈活的訪問策略。

1.4 環上誤差學習問題

圖1 訪問樹實例Fig.1 Instance of tree-access structure

Os：輸出帶噪聲的偽隨機采樣樣本(a,b)=(a,as+e)∈Rq×Rq，其中，a為環多項式，e是系數取自離散分布χ的噪聲，s∈Rq是一均勻分布的密鑰。

2 方案模型和安全模型

2.1 方案模型

本方案包括如下4個算法。

1)系統初始化Setup(λ,U)：授權機構初始化系統，輸入系統安全參數λ和屬性集合U，輸出系統主私鑰MSK，公布系統公共參數PP；

2)密鑰生成KeyGen(MSK,ω′)：授權機構執行密鑰生成算法，輸入主私鑰MSK，根據用戶屬性集合ω′計算得到用戶私鑰K；

3)加密Encrypt(PP,M,T)：該算法由發送方執行。發送者獲取公共參數PP，采用訪問樹T作為訪問策略，對消息M進行加密，計算出密文CT；

4)解密Decrypt(PP,CT,K)：用戶獲取公共參數PP及密文CT，用自己的私鑰K對其進行解密，得到明文M。

2.2 安全模型

方案安全游戲模型為選擇訪問結構及選擇明文攻擊下的不可區分性。游戲方案由一個模擬器和一個敵手組成，具體如下。

Init：敵手提交給模擬器要挑戰訪問結構T*；

Setup：模擬器運行初始化算法生成系統公共參數PP以及系統主私鑰MSK，然后將PP發送給敵手；

Phase 1：敵手可以詢問任何不滿足訪問樹T*的屬性集合的私鑰。模擬器根據敵手詢問的屬性集合生成私鑰K，并將其發送給敵手；

Challenge：敵手選擇明文M發送給模擬器；模擬器擲一枚硬幣b，如果b=0，則模擬器在密文空間中隨機選擇挑戰密文C*；如果b=1，則模擬器生成挑戰密文為C*=Encrypt(PP,M,T*)，并將其發送給敵手；

Phase 2：重復Phase 1；

Guess：敵手提交對b的猜想b′。

3 方案構造

3.1 系統初始化

Setup(λ,U):輸入系統安全參數λ和屬性集合U={u1,u1,…,un}。選擇一個有效的大素數q=1mod(2λ)和一個小的正整數p，滿足p<表示模f(x)和q的整數多項式環，χ是在Rq上的誤差分布。

1)隨機均勻地選擇主密鑰SK0←Rq和元素a←Rq，計算PK0=a·SK0+pe0∈Rq；

3.2 密鑰生成

3.3 加密

Encrypt(PP,M,T)：輸入公共參數PP，消息M和樹形訪問結構T，樹中屬性集合記為ω。隨機選擇s∈Rq。自上而下為樹中的每一個非葉子節點node選擇一個dnode=knode-1階多項式qnode(x)，其中，qroot(0)=s，其他每個節點的多項式要滿足qnode(x)=qparent(index(node))，記qnode(0)=snode。根據葉節點的父節點取得葉子節點node的值，記為si∈Rq,i=attr(node)。

2)輸出密文CT=(C0,{Ci}i∈ω,T)。

3.4 解密

Decrypt(PP,CT,K)：獲取公共參數PP，用戶的私鑰K及密文CT。若用戶屬性集合ω′與訪問結構T能夠匹配，則可成功解密。定義遞歸解密算法DecNd(CT,K,node)，其中，CT為密文，K為用戶的私鑰，node為樹上的一個節點。通過遞歸算法DecNd(CT,K,root)對訪問樹T的根節點root解密，并加以處理計算得到明文M。遞歸解密算法DecNd(CT,K,node)具體如下。

1)如果node是葉子節點，則

DecNd(CT,K,node)=Ci·Ki=

2)如果node是非葉子節點，選擇Inode，它是由節點node下滿足訪問樹的最少子節點構成的集合，記節點node的子節點為z，則

4 方案分析

4.1 正確性分析

利用本方案的加密算法將明文M進行加密，如果可以利用本方案的解密算法解密成功，得到明文M，則可證明本方案的正確性。

解密算法輸出如下。

M*=C0-K0b=

PK0rs+M+pe′-arts(SK0t-1+pe″)-

PK0rs+M+pe′-ars·SK0-

(a·SK0+pe0)rs+M+pe′-ars·SK0-

pe0rs+M+pe′-arts·pe″-

M=M*modp。

證畢。

4.2 安全性證明

定理1如果敵手能夠以優勢ε贏得2.2節中安全模型游戲，則模擬器可以有優勢ε/2解決判定R-LWE問題。

Init：敵手提交給模擬器要挑戰訪問結構T*；

Challenge：敵手發送給模擬器隨機選擇的明文串M。模擬器擲一枚硬幣b，若b=0，則模擬器隨機選擇x0←Rq，計算C0=px0∈Rq和Ci=pxi∈Rq；若b=1，計算C0=pv0+M∈Rq和Ci=pvi∈Rq。然后將其發送給敵手；

Phase 2：重復Phase 1；

4.3 性能分析

表1 相關方案對比

文獻[10-11，13]和本文方案中都是格上ABE方案，且這些方案加解密運算是線性運算，比傳統的基于雙線性對的ABE方案運算效率較高。從表1可以看出，文獻[10-11]是基于標準格上的LWE難題，加密明文大小為1。文獻[13]和本文方案是基于理想格上R-LWE難題，加密明文大小為n。文獻[10-11，13]都是CP-ABE方案，分別支持門限、門限和LSSS訪問結構。本文方案是基于理想格上R-LWE難題的CP-ABE方案，采用訪問樹結構支持任意的訪問策略。在私鑰尺寸上，文獻[10-11]由級聯矩陣利用左抽樣算法進行密鑰抽取，私鑰大小和用戶屬性個數相關。本文方案與文獻[13]的私鑰是通過對環多項式計算得到的，由于m≥5nlogq，所以私鑰大小遠遠小于文獻[10-11]。在密文尺寸上，密文大小和格上相關方案[10-11]都與加密時訪問策略中包含的屬性個數相關，但由于m≥5nlogq，本文方案遠遠小于文獻[10-11]，與文獻[13]保持一致。在密文膨脹率方面，本文方案遠小于文獻[10-11]。在計算效率方面，文獻[10-11]中在計算密文時使用了n×m的矩陣以及m×m的矩陣，使得加密時的計算復雜度較高，加密效率低，加解密運行時間長。而本文方案和文獻[13]在計算密文時，使用的是大小為n的環元素，計算復雜度較低，運算效率高，加解密運行時間短。從表2可以明顯看出，本文方案的加解密效率與文獻[13]的加解密效率相當，加解密效率遠高于文獻[10-11]。本文方案與文獻[13]為密文策略屬性基加密方案，且都基于理想格R-LWE難題，私鑰大小、密文大小等性能相同。然而，文獻[13]采用LSSS訪問結構，構造相對復雜，而本文方案采用樹形訪問結構，靈活性較高，表達更為直觀。

表2 加解密效率對比

5 結束語

本文利用理想格上的R-LWE問題構造了支持訪問樹結構的CP-ABE方案，證明滿足選擇訪問結構和選擇明文攻擊下的安全性。方案采用樹形訪問結構，靈活性較高，同時利用理想格上的R-LWE問題可以加密n個比特的明文，系統效率較高。在實際應用中，屬性基加密系統的屬性會發生改變，這會引起屬性的失效和變更等情況，下一步將對格上屬性基加密機制中屬性撤銷問題進行研究。