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

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

(河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，河南 焦作 454000)

0 引 言

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

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

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

1 相關(guān)知識

1.1 格

1.2 理想格

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

1)f(x)的首相(最高次的項(xiàng))系數(shù)為1；

2)在Z上是不可約的；

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

1.3 樹形訪問結(jié)構(gòu)

樹形訪問結(jié)構(gòu)T，根節(jié)點(diǎn)記為root，非葉子節(jié)點(diǎn)記為node。樹中節(jié)點(diǎn)node的子節(jié)點(diǎn)個(gè)數(shù)記為numnode，節(jié)點(diǎn)node的父節(jié)點(diǎn)表示為parent(node)。樹中每個(gè)非葉子節(jié)點(diǎn)都有門限值knode∈(0,numnode]。當(dāng)knode=1時(shí)，該節(jié)點(diǎn)代表或門；當(dāng)knode=numnode時(shí)，該節(jié)點(diǎn)代表與門。樹中葉子節(jié)點(diǎn)node代表一個(gè)真實(shí)的屬性，記為attr(node)。樹中非葉子節(jié)點(diǎn)node的所有子節(jié)點(diǎn)用1到numnode進(jìn)行編號，用index(node)返回。

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

圖1為訪問樹結(jié)構(gòu)的例子，圖1中,節(jié)點(diǎn)a的門限值ka=2與子節(jié)點(diǎn)個(gè)數(shù)相同表示與門，節(jié)點(diǎn)c的門限值kc=1，即當(dāng)有一個(gè)子節(jié)點(diǎn)滿足即可，表示或門。樹中葉子節(jié)點(diǎn)b，f和c分別代表屬性1、屬性2和屬性3，當(dāng)具有屬性1和屬性2或者屬性1和屬性3時(shí)才滿足上述訪問樹。在方案中，根據(jù)訪問樹的設(shè)計(jì)可以實(shí)現(xiàn)靈活的訪問策略。

1.4 環(huán)上誤差學(xué)習(xí)問題

圖1 訪問樹實(shí)例Fig.1 Instance of tree-access structure

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

2 方案模型和安全模型

2.1 方案模型

本方案包括如下4個(gè)算法。

1)系統(tǒng)初始化Setup(λ,U)：授權(quán)機(jī)構(gòu)初始化系統(tǒng)，輸入系統(tǒng)安全參數(shù)λ和屬性集合U，輸出系統(tǒng)主私鑰MSK，公布系統(tǒng)公共參數(shù)PP；

2)密鑰生成KeyGen(MSK,ω′)：授權(quán)機(jī)構(gòu)執(zhí)行密鑰生成算法，輸入主私鑰MSK，根據(jù)用戶屬性集合ω′計(jì)算得到用戶私鑰K；

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

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

2.2 安全模型

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

Init：敵手提交給模擬器要挑戰(zhàn)訪問結(jié)構(gòu)T*；

Setup：模擬器運(yùn)行初始化算法生成系統(tǒng)公共參數(shù)PP以及系統(tǒng)主私鑰MSK，然后將PP發(fā)送給敵手；

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

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

Phase 2：重復(fù)Phase 1；

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

3 方案構(gòu)造

3.1 系統(tǒng)初始化

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

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

3.2 密鑰生成

3.3 加密

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

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

3.4 解密

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

1)如果node是葉子節(jié)點(diǎn)，則

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

2)如果node是非葉子節(jié)點(diǎn)，選擇Inode，它是由節(jié)點(diǎn)node下滿足訪問樹的最少子節(jié)點(diǎn)構(gòu)成的集合，記節(jié)點(diǎn)node的子節(jié)點(diǎn)為z，則

4 方案分析

4.1 正確性分析

利用本方案的加密算法將明文M進(jìn)行加密，如果可以利用本方案的解密算法解密成功，得到明文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如果敵手能夠以優(yōu)勢ε贏得2.2節(jié)中安全模型游戲，則模擬器可以有優(yōu)勢ε/2解決判定R-LWE問題。

Init：敵手提交給模擬器要挑戰(zhàn)訪問結(jié)構(gòu)T*；

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

Phase 2：重復(fù)Phase 1；

4.3 性能分析

表1 相關(guān)方案對比

文獻(xiàn)[10-11，13]和本文方案中都是格上ABE方案，且這些方案加解密運(yùn)算是線性運(yùn)算，比傳統(tǒng)的基于雙線性對的ABE方案運(yùn)算效率較高。從表1可以看出，文獻(xiàn)[10-11]是基于標(biāo)準(zhǔn)格上的LWE難題，加密明文大小為1。文獻(xiàn)[13]和本文方案是基于理想格上R-LWE難題，加密明文大小為n。文獻(xiàn)[10-11，13]都是CP-ABE方案，分別支持門限、門限和LSSS訪問結(jié)構(gòu)。本文方案是基于理想格上R-LWE難題的CP-ABE方案，采用訪問樹結(jié)構(gòu)支持任意的訪問策略。在私鑰尺寸上，文獻(xiàn)[10-11]由級聯(lián)矩陣?yán)米蟪闃铀惴ㄟM(jìn)行密鑰抽取，私鑰大小和用戶屬性個(gè)數(shù)相關(guān)。本文方案與文獻(xiàn)[13]的私鑰是通過對環(huán)多項(xiàng)式計(jì)算得到的，由于m≥5nlogq，所以私鑰大小遠(yuǎn)遠(yuǎn)小于文獻(xiàn)[10-11]。在密文尺寸上，密文大小和格上相關(guān)方案[10-11]都與加密時(shí)訪問策略中包含的屬性個(gè)數(shù)相關(guān)，但由于m≥5nlogq，本文方案遠(yuǎn)遠(yuǎn)小于文獻(xiàn)[10-11]，與文獻(xiàn)[13]保持一致。在密文膨脹率方面，本文方案遠(yuǎn)小于文獻(xiàn)[10-11]。在計(jì)算效率方面，文獻(xiàn)[10-11]中在計(jì)算密文時(shí)使用了n×m的矩陣以及m×m的矩陣，使得加密時(shí)的計(jì)算復(fù)雜度較高，加密效率低，加解密運(yùn)行時(shí)間長。而本文方案和文獻(xiàn)[13]在計(jì)算密文時(shí)，使用的是大小為n的環(huán)元素，計(jì)算復(fù)雜度較低，運(yùn)算效率高，加解密運(yùn)行時(shí)間短。從表2可以明顯看出，本文方案的加解密效率與文獻(xiàn)[13]的加解密效率相當(dāng)，加解密效率遠(yuǎn)高于文獻(xiàn)[10-11]。本文方案與文獻(xiàn)[13]為密文策略屬性基加密方案，且都基于理想格R-LWE難題，私鑰大小、密文大小等性能相同。然而，文獻(xiàn)[13]采用LSSS訪問結(jié)構(gòu)，構(gòu)造相對復(fù)雜，而本文方案采用樹形訪問結(jié)構(gòu)，靈活性較高，表達(dá)更為直觀。

表2 加解密效率對比

5 結(jié)束語

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