一種基于時(shí)間約束的分層訪問控制方案

馬 駿 郭淵博 馬建峰 張 琦

1(西安電子科技大學(xué)計(jì)算機(jī)學(xué)院 西安 710071)2 (解放軍信息工程大學(xué) 鄭州 450001) (sijunhan@163.com)

一種基于時(shí)間約束的分層訪問控制方案

馬 駿1,2郭淵博2馬建峰1張 琦2

1(西安電子科技大學(xué)計(jì)算機(jī)學(xué)院 西安 710071)2(解放軍信息工程大學(xué) 鄭州 450001) (sijunhan@163.com)

提出一種時(shí)間約束條件下的分層訪問控制方案.根據(jù)用戶對(duì)感知節(jié)點(diǎn)資源的訪問控制需求，充分考慮感知節(jié)點(diǎn)計(jì)算、存儲(chǔ)能力受限且節(jié)點(diǎn)數(shù)海量的特點(diǎn)，從用戶掌握密鑰數(shù)、密鑰獲取時(shí)間和產(chǎn)生公共信息數(shù)3方面進(jìn)行優(yōu)化設(shè)計(jì)，以實(shí)現(xiàn)高效、安全的分層訪問控制. 與現(xiàn)有其他方案對(duì)比，該方案的優(yōu)勢(shì)在于：1)用戶對(duì)大量感知節(jié)點(diǎn)資源進(jìn)行的一次訪問，僅需要掌握單個(gè)密鑰材料；2)通過優(yōu)化設(shè)計(jì)，使用戶訪問節(jié)點(diǎn)資源密鑰的獲取時(shí)間與產(chǎn)生的公共信息數(shù)達(dá)到最佳平衡；3)提出的方案是可證明安全的.

時(shí)間約束;樹重心;分層訪問控制;泛在感知;密鑰獲取

隨著移動(dòng)互聯(lián)、物聯(lián)網(wǎng)等新興技術(shù)的不斷普及，金融、電子商務(wù)、醫(yī)療、軍事后勤、軍事情報(bào)等行業(yè)領(lǐng)域的產(chǎn)業(yè)結(jié)構(gòu)和服務(wù)模式已逐步向無所不在的泛在感知(ubiquitous sensing)方向演進(jìn).泛在感知即是5A(anytime, anywhere, anything, anyone, anydevice)情形下的信息獲取，現(xiàn)階段主要利用RFID、藍(lán)牙、紅外、GPS、音視頻等芯片，以傳感設(shè)備和智能移動(dòng)設(shè)備為載體，采集溫度、視頻、聲音、定位等各類數(shù)據(jù)，為用戶提供相應(yīng)的數(shù)據(jù)訪問[1].在一些典型的泛在感知應(yīng)用場景中，由傳感設(shè)備和智能移動(dòng)設(shè)備構(gòu)成的感知節(jié)點(diǎn)數(shù)以億計(jì)，且具有分布廣、計(jì)算和存儲(chǔ)能力受限、感知信息敏感等特點(diǎn)，使其為信息服務(wù)的泛在化應(yīng)用帶來巨大便利的同時(shí)，也對(duì)感知節(jié)點(diǎn)采集數(shù)據(jù)的安全高效訪問提出了嚴(yán)峻挑戰(zhàn)[2].

傳統(tǒng)的分層訪問控制方案[3]，通過方案設(shè)計(jì)可以實(shí)現(xiàn)用戶在掌握較少密鑰的同時(shí)，既能對(duì)節(jié)點(diǎn)v保護(hù)的資源進(jìn)行訪問，又能通過密鑰推導(dǎo)算法獲取與節(jié)點(diǎn)v構(gòu)成偏序關(guān)系的節(jié)點(diǎn)w的保護(hù)密鑰，進(jìn)而訪問節(jié)點(diǎn)w保護(hù)的資源.而引入時(shí)間因素之后，如果用戶想要在時(shí)刻ti訪問節(jié)點(diǎn)v及構(gòu)成偏序關(guān)系的下層節(jié)點(diǎn)w的資源，則需要獲取時(shí)刻ti層次節(jié)點(diǎn)v的密鑰材料kti；如果想要訪問時(shí)刻tj層次節(jié)點(diǎn)v及構(gòu)成偏序關(guān)系的下層節(jié)點(diǎn)w的資源，則必須另外獲取時(shí)刻tj層次節(jié)點(diǎn)v的密鑰材料ktj.依次類推，如果用戶想要訪問T=[ti,tj]一個(gè)時(shí)間段內(nèi)v的資源，不得不獲取ti≤t≤tj內(nèi)每個(gè)時(shí)刻對(duì)應(yīng)的密鑰材料.隨著T時(shí)間段的增大，用戶一次需要掌握大量的密鑰材料才能訪問，顯然無法滿足泛在感知環(huán)境下任何時(shí)間能夠訪問感知節(jié)點(diǎn)資源的實(shí)際應(yīng)用需求.如何在時(shí)間約束條件下，用戶盡可能掌握較少的密鑰材料并安全高效地訪問更多的資源，是泛在感知環(huán)境資源訪問必須要解決的實(shí)際問題，需要考慮適用于泛在感知環(huán)境下基于時(shí)間約束的分層訪問控制方案[4].

在時(shí)間約束條件下的分層訪問控制方案中，大多數(shù)方案都為了解決因時(shí)間分片帶來極大的密鑰計(jì)算和密鑰存儲(chǔ)消耗，往往忽視了分層訪問控制下的多用戶合謀攻擊的發(fā)生[5-8]；文獻(xiàn)[9-10]基于Akl和Taylor提出方案的擴(kuò)展，提出了時(shí)間約束條件下的安全方案構(gòu)造，但未考慮方案的安全問題；文獻(xiàn)[11]雖然給出了可證明安全的考慮時(shí)間約束條件下的分層訪問控制方案，但其方案是基于RSA的構(gòu)造，采用模數(shù)運(yùn)算的計(jì)算量，無法適用泛在感知環(huán)境感知節(jié)點(diǎn)計(jì)算能力受限的情況；文獻(xiàn)[12]提出了考慮時(shí)間約束條件下可證明安全的基于對(duì)稱密鑰算法的訪問控制方案，具有計(jì)算量較少的特點(diǎn)，但該方案導(dǎo)致較多的密鑰產(chǎn)生，會(huì)增大感知節(jié)點(diǎn)和用戶的密鑰存儲(chǔ)負(fù)擔(dān)，因此也不適用于泛在感知環(huán)境.

針對(duì)用戶在時(shí)間約束條件下對(duì)泛在感知環(huán)境節(jié)點(diǎn)資源的分層訪問控制需求，本文利用有向無環(huán)圖的特性，設(shè)計(jì)了一種基于時(shí)間約束的分層訪問控制方案，與現(xiàn)有方案相比較，本文的優(yōu)勢(shì)主要體現(xiàn)在：1)用戶在一次訪問過程中僅需要掌握單個(gè)密鑰材料，通過簡單計(jì)算即能訪問相應(yīng)級(jí)別在某一時(shí)刻的資源及該級(jí)別以下相應(yīng)時(shí)刻的資源；2)在密鑰獲取時(shí)間與產(chǎn)生的公共信息之間達(dá)到最佳平衡；3) 提出的方案在標(biāo)準(zhǔn)模型下的可證明安全的.

1 時(shí)間約束條件下的分層訪問控制模型

設(shè)DAGG=(V,E,S)是一個(gè)有向無環(huán)圖，其中V={v1,v2,…,vn}，表示G的節(jié)點(diǎn)集合，每個(gè)節(jié)點(diǎn)vi代表一個(gè)層次節(jié)點(diǎn)；E={e1,e2,…,ek}，表示G的有向邊的集合，每條有向邊ei連接的2個(gè)層次節(jié)點(diǎn)之間具有覆蓋關(guān)系；S={s1,s2,…,sj}，表示當(dāng)前級(jí)別的層次節(jié)點(diǎn)包含數(shù)據(jù)資源的集合，可以用函數(shù)ξ：V→2S表示，并且存在?vi,vj∈V，如果vi和vj不構(gòu)成偏序或覆蓋關(guān)系，則ξ(vi)∩ξ(vj)=?.設(shè)T={t1,t2,…,tm}是一個(gè)時(shí)間序列，λ表示時(shí)間段，是T的一個(gè)子集，記作λ?T.由多個(gè)λ構(gòu)成的集合，表示時(shí)間段的集合，記作ζ={λ1,λ2,…,λn}.一個(gè)時(shí)間約束條件下的分層訪問控制模型描述如下：

給定DAGG=(V,E,S),T={t1,t2,…,tm},ζ={λ1,λ2,…,λn}和安全參數(shù){0,1}κ，在多項(xiàng)式時(shí)間內(nèi)，對(duì)?v∈V初始化產(chǎn)生密鑰材料kv,λ、保護(hù)密鑰skv,t及公共信息，其中v∈V,λ∈ζ,t∈λ.利用kv,λ和公共信息，通過計(jì)算可得到λ內(nèi)的任意skv,t，同時(shí)利用層次節(jié)點(diǎn)之間的偏序關(guān)系，可以在多項(xiàng)式時(shí)間內(nèi)計(jì)算得到kw,λ和skw,t，其中v≤w,w∈V.

在該模型下，用戶對(duì)泛在感知環(huán)境中資源的訪問過程為：當(dāng)用戶想要訪問時(shí)間段λ層次節(jié)點(diǎn)v的資源，首先需要通過安全通路從密鑰生成中心TA獲得合法的密鑰材料kv,λ，然后結(jié)合公開信息計(jì)算得到時(shí)間t的資源保護(hù)密鑰skv,t.接著利用公共邊信息E得到與v構(gòu)成偏序關(guān)系的層次節(jié)點(diǎn)集合，即可通過密鑰推導(dǎo)算法得到層次節(jié)點(diǎn)w在時(shí)間段λ的密鑰材料，進(jìn)而結(jié)合公共信息計(jì)算得到時(shí)間t的資源保護(hù)密鑰skw,t.只要存在e∈E滿足從授權(quán)層次節(jié)點(diǎn)開始到其他層次節(jié)點(diǎn)的有向路徑，均可通過公開的e利用重復(fù)的密鑰推導(dǎo)算法獲得下層密鑰，從而使該用戶的一次訪問過程中僅掌握單個(gè)密鑰材料kv,λ情況下，能夠訪問更多的節(jié)點(diǎn)資源，從而增加分層訪問控制的實(shí)用性.

通過前文分析，我們可以感受到在加入時(shí)間因素的分層訪問控制中，用戶獲取層次節(jié)點(diǎn)密鑰訪問節(jié)點(diǎn)資源的過程，相比較不考慮時(shí)間因素的情況，大大增加了密鑰存儲(chǔ)負(fù)擔(dān)和密鑰獲取時(shí)間.因此，在設(shè)計(jì)時(shí)間約束條件下的分層訪問控制方案時(shí)，要統(tǒng)一考慮以下3個(gè)實(shí)際需求：

1) 用戶在一次訪問過程盡可能掌握較少的密鑰數(shù)；

2) 具有較小的密鑰獲取時(shí)間；

3) 產(chǎn)生較少的公共信息.

從用戶的訪問角度考慮，第2節(jié)設(shè)計(jì)的方案中是在首要滿足需求1的情況下，通過對(duì)方案的設(shè)計(jì)在需求2和需求3之間達(dá)到一定的平衡.

2 基本方案構(gòu)造

Santis等人基于對(duì)稱密鑰學(xué)在文獻(xiàn)[13]中，提出一種建立2層加密構(gòu)造分層訪問控制方案(記作TLEBC).該方案需要將上層節(jié)點(diǎn)的λ與本層及下層的t建立對(duì)應(yīng)關(guān)系.隨著層次的增加，其建立的有向公共邊數(shù)會(huì)呈幾何級(jí)數(shù)的增長.針對(duì)TLEBC方案存在的問題，本文首先提出基于2類偏序關(guān)系的方案構(gòu)造(記作TLPOS)，其構(gòu)造思想為：上層節(jié)點(diǎn)vλ僅與下層節(jié)點(diǎn)wλ建立偏序關(guān)系，而λ和t僅在同層次之間建立偏序關(guān)系，從而形成2類偏序關(guān)系.

給定G=(G1,G2)表示時(shí)間約束條件下的分層訪問控制模型，其中G1表示由層次節(jié)點(diǎn)V={v1,v2,…,vn}的級(jí)聯(lián)關(guān)系構(gòu)成的有向圖，G1中的節(jié)點(diǎn)表示層次節(jié)點(diǎn)，有向邊表示層次節(jié)點(diǎn)之間形成的偏序關(guān)系；G2表示由ζ={λ1,λ2,…,λn}的包含關(guān)系形成的有向圖，G2中節(jié)點(diǎn)表示λi，有向邊表示λi之間形成的偏序關(guān)系.通過將G按2類偏序關(guān)系進(jìn)行分解，TLPOS方案的構(gòu)造過程如下：

1) 對(duì)于每一個(gè)v∈V，每一個(gè)λ∈ζ，給出新的層次節(jié)點(diǎn)vλ，其中|λ| >1；

2)v∈V，每一個(gè)t∈T，給出新的層次節(jié)點(diǎn)vt；

3) 對(duì)于每一個(gè)v∈V，每一個(gè)λ∈ζ，每一個(gè)t∈T，給出新的有向邊eλt=〈vλ,vt〉；

4) 對(duì)于v,w∈V，每一個(gè)λ∈ζ，給出新的有向邊evw=〈vλ,wλ〉.

其中，我們只在|λ|>1的情形下給出新的層次節(jié)點(diǎn)；當(dāng)|λ|=1時(shí)，即λ={ti}，此種情況與t∈T中的情況相同，可認(rèn)為是同一層次節(jié)點(diǎn).

與文獻(xiàn)[13]給出的示例保持一致，假設(shè)ζ={λ1,λ2,λ3}，其中λ1={t1,t2}，λ2={t1,t2,t3}，λ3={t2,t3}.如果存在v,w∈V，且w·v，則按照TLPOS構(gòu)造過程形成的有向圖如圖1所示:

Fig. 1 Directed graph based on two kinds of partial order relation圖1 基于2類偏序關(guān)系的有向圖

通過圖1示例可以看出，在加入時(shí)間條件后，2個(gè)層次節(jié)點(diǎn)之間形成的偏序關(guān)系，會(huì)隨著時(shí)間集的變化構(gòu)成多個(gè)層次節(jié)點(diǎn)和多個(gè)偏序關(guān)系.為了能夠獲取下層節(jié)點(diǎn)在某一時(shí)刻的密鑰，需要做以下初始化構(gòu)造：

步驟1. 對(duì)于每個(gè)層次節(jié)點(diǎn)v，隨機(jī)選取密鑰材料kv,λ∈{0,1}κ，利用kv,λ和散列函數(shù)f計(jì)算得到保護(hù)密鑰skv,λ和推導(dǎo)密鑰dkv,λ；

步驟2. 對(duì)于每個(gè)層次節(jié)點(diǎn)v，隨機(jī)選取密鑰kv,t∈{0,1}κ，利用對(duì)稱密鑰加密方法ε的加密算法E，將保護(hù)密鑰skv,λ和kv,t建立映射關(guān)系，作為公共邊信息eλt；

步驟3. 對(duì)于每個(gè)層次節(jié)點(diǎn)v,w，w·v存在，隨機(jī)選取密鑰材料kw,λ∈{0,1}κ，利用對(duì)稱密鑰加密方法ε的加密算法E′將推導(dǎo)密鑰dkv,λ和kw,λ建立映射關(guān)系，作為公共邊信息evw.

通過以上初始化構(gòu)造，將公共信息發(fā)布到感知層網(wǎng)絡(luò)，私有信息由層次節(jié)點(diǎn)存儲(chǔ).

在該構(gòu)造方案下，用戶對(duì)感知環(huán)境資源進(jìn)行訪問的過程：首先通過TA獲取層次節(jié)點(diǎn)v在時(shí)間段λ內(nèi)的密鑰材料kv,λ，計(jì)算得到保護(hù)密鑰skv,λ和推導(dǎo)密鑰dkv,λ；利用保護(hù)密鑰skv,λ和公共信息eλt通過解密算法D(與加密算法E對(duì)應(yīng))，計(jì)算得到kv,t；同時(shí)，利用推導(dǎo)密鑰dkv,λ和公共信息evw通過解密算法D′ (與加密算法E′對(duì)應(yīng))，計(jì)算得到kw,λ；然后利用kw,λ，計(jì)算得到層次節(jié)點(diǎn)w在時(shí)間段λ內(nèi)的保護(hù)密鑰skw,λ和推導(dǎo)密鑰dkw,λ，并利用保護(hù)密鑰skw,λ按照相同步驟計(jì)算得到保護(hù)密鑰kw,t.需要說明的是，考慮到通用性，這里我們并未指出具體的密鑰推導(dǎo)算法，在實(shí)際應(yīng)用中為了防止同謀攻擊的發(fā)生，可參考本文作者在文獻(xiàn)[14]提出的密鑰推導(dǎo)算法，或其他具有同樣安全保障的密鑰推導(dǎo)算法.

通過上述步驟，我們可以看到，用戶在某一時(shí)間段λ，僅需要掌握單個(gè)密鑰材料kv,λ，通過簡單的單向散列計(jì)算和對(duì)稱加密運(yùn)算即能得到當(dāng)前層次或下層節(jié)點(diǎn)對(duì)應(yīng)某一時(shí)刻的保護(hù)密鑰，進(jìn)而訪問相應(yīng)資源.與文獻(xiàn)[13]中的TLEBC方案相比，TLPOS方案在同樣滿足需求1和需求2的同時(shí)，能夠更好地滿足需求3.

3 基于樹重心分解的分層訪問控制方案

在第2節(jié)提出的TLPOS方案中，我們可以看到在時(shí)間約束條件下的分層訪問控制本質(zhì)上是分成2部分進(jìn)行構(gòu)造：一部分是實(shí)際存在層次節(jié)點(diǎn)之間形成的分層訪問控制關(guān)系(空間維度形成的層次關(guān)系)，另一部分是由多個(gè)時(shí)間段與訪問時(shí)刻形成的層次關(guān)系(時(shí)間維度形成的層次關(guān)系).而在這2部分中，第2部分的分層訪問控制會(huì)因時(shí)間的增長(|T|→n)和時(shí)間段的增多(|λ|→n)，使初始化構(gòu)造時(shí)不得不產(chǎn)生大量的公共信息，以滿足用戶獲取時(shí)間t的密鑰，進(jìn)而能夠訪問對(duì)應(yīng)時(shí)刻的資源.雖然TLPOS方案相比文獻(xiàn)[13]中的TLEBC方案已經(jīng)明顯減少公共信息的產(chǎn)生，但產(chǎn)生的公共信息量仍給系統(tǒng)造成負(fù)擔(dān).如何減少大量公共信息的產(chǎn)生是需要進(jìn)一步解決的問題.

3.1 基于λ分層的方案構(gòu)造

給定ζ={λ1,λ2,λ3}和T={t1,t2,…,tm}，在TLPOS方案構(gòu)造中，是將每個(gè)λ(λ∈ζ)與對(duì)應(yīng)的tj(tj∈T)直接利用公共邊建立對(duì)應(yīng)關(guān)系，如圖1中的vλ到vt的有向邊.這種構(gòu)造方式雖然對(duì)減小密鑰獲取時(shí)間有利(時(shí)間維度僅一次推導(dǎo)過程)，但會(huì)產(chǎn)生大量的公共邊信息.

如果利用集合λ之間具備的包含關(guān)系，首先將ζ中的λ建立層次關(guān)系，然后將部分λ與之包含的t建立層次關(guān)系，無疑會(huì)大大縮短λ與t之間的公共邊數(shù).ζ={λ1,λ2,…,λn}中的λ之間天然地具備包含與被包含的關(guān)系，從而可以利用該特征建立λ之間的偏序關(guān)系，形成有向無環(huán)圖.基于該構(gòu)造思想，本文在TLPOS方案的基礎(chǔ)上，為減少初始化構(gòu)造中產(chǎn)生的公共信息量，將提出基于樹重心分解的方案構(gòu)造(記作TCDS).

舉例來講，設(shè)T={t1,t2,t3,t4},|T|=4，ζ是由T構(gòu)成的全集：

λ1={t1},λ2={t2},λ3={t3},λ4={t4},
λ5={t1,t2},λ6={t2,t3},λ7={t3,t4},
λ8={t1,t2,t3},λ9={t2,t3,t4},
λ10={t1,t2,t3,t4}.

其中|ζ|=10.利用λi(i=1,2,…,10)之間的包含關(guān)系，可建立如圖2的有向無環(huán)圖.為表述更加直觀，我們將λi按時(shí)間區(qū)間方式表示，如λ1表示[1,1]，λ6表示[2,3]，λ9表示[2,4]等.

Fig. 2 DAG composed by λi圖2 λi構(gòu)成的有向無環(huán)圖

通過圖2我們可以看到，利用λi形成的偏序關(guān)系，當(dāng)|T|=4時(shí)，λ與t之間建立的公共邊僅為6(將|λ|=1的節(jié)點(diǎn)作為時(shí)間節(jié)點(diǎn))，與TLPOS方案構(gòu)造中同一層次節(jié)點(diǎn)內(nèi)λ與t之間建立的公共邊數(shù)(總計(jì)為16)相比，公共邊數(shù)得到大幅下降.即使將λ之間的公共邊數(shù)計(jì)算在內(nèi)，總的公共邊數(shù)也小于基本方案構(gòu)造建立的公共邊總數(shù)，且隨著|T|值的增大，公共邊數(shù)也會(huì)隨之大幅減少.

3.2 基于樹重心分解的優(yōu)化

上述構(gòu)造方案雖使公共邊數(shù)得以減少，但是當(dāng)用戶通過掌握的λ對(duì)應(yīng)密鑰，推導(dǎo)得到時(shí)刻t密鑰時(shí)，不得不需要經(jīng)過由λ與t(|λ|=1)建立的多條公共邊信息才能計(jì)算得到相應(yīng)密鑰，這無疑會(huì)增加用戶的密鑰獲取時(shí)間(不滿足具有較小密鑰獲取時(shí)間的需求)，且隨著|T|值的增大，λ形成的有向圖深度增加，用戶的密鑰獲取時(shí)間也會(huì)隨之增加，從而增大用戶獲取密鑰時(shí)間的負(fù)擔(dān).

為此，我們需要通過方案設(shè)計(jì)優(yōu)化用戶的密鑰獲取過程，即縮短用戶的密鑰獲取時(shí)間.這里我們引入樹重心的概念和特性.

1) 樹重心的定義.對(duì)于樹T中的任一節(jié)點(diǎn)k，若將它刪去(連同邊)后，樹T會(huì)變?yōu)槿舾煽米訕鋥T1,T2,…,Tn}，取這些子樹的節(jié)點(diǎn)數(shù)中最多的作為節(jié)點(diǎn)k的值.如果對(duì)應(yīng)樹T中所有節(jié)點(diǎn)中對(duì)應(yīng)的k值最小，則稱k為樹T的重心，記作c[15].

2) 樹重心分解的特性.設(shè)T的節(jié)點(diǎn)數(shù)為n，將以重心c為根的樹從T中刪除，T中剩余部分的節(jié)點(diǎn)數(shù)小于n2[16].

通過對(duì)樹重心的逐次分解，可將每次分解確定的樹重心依序兩兩通過有向邊進(jìn)行連接，進(jìn)而能夠縮短整個(gè)樹從樹根到葉子結(jié)點(diǎn)的距離(減小樹的深度).將重心之間連接的有向邊作為新添加的公共邊信息，則用戶可通過新增的公共邊信息進(jìn)行密鑰推導(dǎo)過程，從而減少用戶的密鑰獲取時(shí)間.

我們?cè)O(shè)計(jì)基于樹重心分解的構(gòu)造過程如下：

步驟1. 計(jì)算樹T的重心c[17]，并以樹T的根r作為起點(diǎn)，重心c為終點(diǎn)，建立一條有向邊作為新添加的公共邊，如果c·r已經(jīng)存在，則不需要添加新的有向邊.

步驟2.1. 以c為根建立的樹T1中，計(jì)算重心c1，并添加一條以c為起點(diǎn)、c1為終點(diǎn)的有向公共邊，如果c1·c存在，則不需要添加新的有向邊.

步驟2.2. 樹T除去樹T1的部分構(gòu)成新樹T2，計(jì)算T2的重心c2，并建立一條從r到c2的有向邊，如果c2·r存在，則不需要添加新的有向邊.

步驟3.1. 以c1為根建立的新樹T3，分別重復(fù)步驟2.1、步驟2.2的過程建立新的公共邊信息.

步驟3.2. 樹T1除去樹T3的部分構(gòu)成的新樹T4，分別重復(fù)步驟2.1、步驟2.2的過程建立新的公共邊信息.

步驟4. 對(duì)整個(gè)樹T重復(fù)以上的步驟，直至構(gòu)成新樹T′的根r′與T′的重心c′滿足r′=c′，則樹初始化過程結(jié)束.

以上構(gòu)造過程，每添加一條公共邊均需要進(jìn)行公共邊增加的操作.增加有向公共邊的操作過程，可參見本文作者在文獻(xiàn)[14]提出的操作步驟，能夠使新增公共邊信息的過程無需更改原層次節(jié)點(diǎn)的私有信息，只需要調(diào)用原層次節(jié)點(diǎn)的私有信息計(jì)算即可生成新的公共邊信息.

通過分析我們可以得到，上述添加新公共邊的過程，本質(zhì)上是重復(fù)利用樹重心向量的分解來進(jìn)行初始化構(gòu)造.而每次基于樹重心向量的分解剩余部分的層次節(jié)點(diǎn)數(shù)均小于原樹層次節(jié)點(diǎn)數(shù)的一半.這樣，以樹T的根節(jié)點(diǎn)r和所有計(jì)算出的重心節(jié)點(diǎn)集合{c1,c2,…,ci}(i

Fig. 3 Binary tree based on the decomposition of the centroid of tree圖3 基于重心分解的2叉樹

圖3中父節(jié)點(diǎn)與左兒子節(jié)點(diǎn)之間的有向邊是真正添加的公共邊，表示的是重心節(jié)點(diǎn)之間的偏序關(guān)系；父節(jié)點(diǎn)與右兒子之間的連接用虛線表示，表示的是樹Ti在去除重心ci之前的根節(jié)點(diǎn)與去除重心ci之后的根節(jié)點(diǎn)之間的連線(即虛線2端為同一層次節(jié)點(diǎn)，如r=r1=r2=r3).

3.3 基于樹重心分解的方案構(gòu)造

由于3.1節(jié)λi構(gòu)成的層次關(guān)系并不符合樹的特征(層次節(jié)點(diǎn)存在一個(gè)以上的父節(jié)點(diǎn))，因此，如果想要利用3.2節(jié)的優(yōu)化方案，首先需要將有向無環(huán)圖轉(zhuǎn)換成有向樹.

仍以T={t1,t2,t3,t4},|T|=4為例，我們將圖2轉(zhuǎn)換成有向樹如圖4所示.

自此，我們可以基于樹重心的特性，利用3.2節(jié)的樹重心分解優(yōu)化，展開基于樹重心分解的構(gòu)造.在現(xiàn)有節(jié)點(diǎn)中挑選特殊的節(jié)點(diǎn)(利用樹重心分解算法找樹的重心)，依次添加有向邊建立連接關(guān)系，從而利用特殊節(jié)點(diǎn)建立一條有向路徑.

Fig. 4 The direct tree composed by λi圖4 λi構(gòu)成的有向樹

通過以上分析，我們建立基于樹重心分解的方案構(gòu)造.

給定G=(G1,G2)表示時(shí)間約束條件下的分層訪問控制模型，其中G1表示由層次節(jié)點(diǎn)V={v1,v2,…,vn}的級(jí)聯(lián)關(guān)系構(gòu)成的有向圖，圖中節(jié)點(diǎn)表示層次節(jié)點(diǎn)，圖中的有向邊表示層次節(jié)點(diǎn)之間形成的偏序關(guān)系；G2表示由ζ={λ1,λ2,…,λn}的包含關(guān)系形成的有向樹，樹中節(jié)點(diǎn)表示λi，樹中的有向邊表示λi之間形成的偏序關(guān)系.通過將G按2類偏序關(guān)系進(jìn)行分解，整個(gè)方案的構(gòu)造過程如下：

1) 對(duì)于每一個(gè)v∈V，每一個(gè)λ∈ζ，給出新的層次節(jié)點(diǎn)vλ，其中|λ|>1；

2) 對(duì)于每一個(gè)v∈V，每一個(gè)t∈T，給出新的層次節(jié)點(diǎn)vt；

3) 對(duì)于每一個(gè)v∈V，λi,λj∈ζ,λj·λi，給出新的有向邊eλiλj=〈vλi,vλj〉；

4) 對(duì)于每一個(gè)v∈V，λci,λcj∈ζ(多次樹重心分析指定的特殊節(jié)點(diǎn)),λcj·λci，給出新的有向邊eλciλcj=〈vλci,vλcj〉，其中|λ|>1；

5) 對(duì)于每一個(gè)v∈V，每一個(gè)λ∈ζ且|λ|=2，每一個(gè)t∈T，給出新的有向邊eλt=〈vλ,vt〉；

6) 對(duì)于v,w∈V，每一個(gè)λ∈ζ，給出新的有向邊evw=〈vλ,wλ〉.

其中，我們只在|λ|>1的情形下給出新的層次節(jié)點(diǎn)；當(dāng)|λ|=1時(shí)，即λ={ti}，此種情況，與t∈T中的情況相同，我們認(rèn)為其可表示為同一層次節(jié)點(diǎn).

3.4 優(yōu)化后的分層訪問控制方案

分層訪問控制方案的初始化過程通過以下步驟進(jìn)行構(gòu)造：

步驟1. 對(duì)于每個(gè)層次節(jié)點(diǎn)v，對(duì)于每個(gè)時(shí)間層次節(jié)點(diǎn)λ(|λ|>1)，隨機(jī)選取密鑰材料kv,λ∈{0,1}κ與之對(duì)應(yīng)，并利用kv,λ和散列函數(shù)f計(jì)算得到保護(hù)密鑰skv,λ和推導(dǎo)密鑰dkv,λ.

步驟2. 對(duì)于每個(gè)層次節(jié)點(diǎn)v，對(duì)于構(gòu)成覆蓋關(guān)系的層次節(jié)點(diǎn)λi,λj(λj·λi)，利用對(duì)稱密鑰加密方法ε的加密算法E，將保護(hù)密鑰skv,λi和skv,λj建立映射關(guān)系，作為公共邊信息eλiλj.

步驟3. 對(duì)于每個(gè)層次節(jié)點(diǎn)v，隨機(jī)選取密鑰kv,t∈{0,1}κ，利用對(duì)稱密鑰加密方法ε的加密算法E，將保護(hù)密鑰skv,λ和kv,t建立映射關(guān)系，其中|λ|=2，作為公共邊信息eλt.

步驟4. 對(duì)于每個(gè)層次節(jié)點(diǎn)v,w，v·w存在，隨機(jī)選取密鑰材料kw,λ∈{0,1}κ，|λ|>1，利用對(duì)稱密鑰加密方法ε的加密算法E′將推導(dǎo)密鑰dku,λ和kw,λ建立映射關(guān)系，作為公共邊信息evw.

經(jīng)過以上初始化構(gòu)造，將公共信息發(fā)布到感知層網(wǎng)絡(luò)，私有信息由層次節(jié)點(diǎn)存儲(chǔ).

在該構(gòu)造方案下，當(dāng)用戶想要訪問感知層節(jié)點(diǎn)資源，首先通過TA獲取層次節(jié)點(diǎn)v在時(shí)間段λ內(nèi)的密鑰材料skv,λi，通過計(jì)算得到保護(hù)密鑰skv,λi和推導(dǎo)密鑰dkv,λi.利用保護(hù)密鑰skv,λi獲取kv,t的過程按下列3種情形進(jìn)行：

情形1. 如果|λi|=2，則利用eλi t?eλt，通過解密算法D(與加密算法E對(duì)應(yīng))，計(jì)算得到kv,t；

情形2. 如果λi∈λc，則利用ecicj，通過解密算法D(與加密算法E對(duì)應(yīng))，計(jì)算得到skv,λj，其中|λj|=2；然后繼續(xù)進(jìn)行情形1的操作，最終得到kv,t；

情形3. 如果λi?λc，則按以下步驟進(jìn)行操作.

步驟1. 找到特殊層次節(jié)點(diǎn)ci，ci∈{c1,c2,…,cn}，滿足v≤ci，且不存在ck，使得v≤ck≤ci存在;然后利用解密算法D(與加密算法E對(duì)應(yīng))推導(dǎo)得到ci對(duì)應(yīng)密鑰.

步驟2. 找到特殊層次節(jié)點(diǎn)cj，cj∈{c1,c2,…,cn}，滿足cj≤w，且不存在ck′，使得ci≤ck′≤w存在;然后利用解密算法D(與加密算法E對(duì)應(yīng))，由ci的私有信息和〈ci,cj〉的公共邊信息，至多經(jīng)過lblbn輪推導(dǎo)得到cj的密鑰.進(jìn)而利用cj的密鑰和〈cj,w〉的公共邊信息，采用解密算法D(與加密算法E對(duì)應(yīng))最終得到w的密鑰信息.由于以ci為根構(gòu)成的樹中ci∈{c1,c2,…,cn}，2個(gè)相鄰的特殊層次節(jié)點(diǎn)將樹中包含的層次節(jié)點(diǎn)保持在常量級(jí)，因此，〈w,ci〉和〈cj,w〉的推導(dǎo)過程經(jīng)過常數(shù)級(jí)的推導(dǎo)輪數(shù)，設(shè)〈w,ci〉的推導(dǎo)輪數(shù)為a1，〈cj,w〉的推導(dǎo)輪數(shù)為a2，則整個(gè)推導(dǎo)過程的密鑰推導(dǎo)輪數(shù)至多為a1+a2+lblbn.

4 方案的性能分析

為了便于和其他相關(guān)文獻(xiàn)進(jìn)行比較，我們假設(shè)一個(gè)時(shí)間約束條件下的分層訪問控制方案G=(G1,G2)，其中G1包含的節(jié)點(diǎn)數(shù)|V|=m，G2包含的時(shí)刻數(shù)|T|=n，且G1為有向樹(該假設(shè)的目的是便于統(tǒng)計(jì)公共邊數(shù)，如果|V|=m，則|E|=m-1).我們將從3個(gè)方面比較：1)用戶的一次訪問過程要盡可能地考慮掌握較少的密鑰；2)具有較小的密鑰獲取時(shí)間；3)產(chǎn)生較少的公共信息，與其他相關(guān)方案進(jìn)行比較.

對(duì)于本文提出的基于樹重心分解的方案構(gòu)造TCDS，一次用戶訪問過程僅需要掌握單個(gè)密鑰(材料)，即能進(jìn)行訪問；而獲取訪問資源密鑰時(shí)間，在|T|=n的情況下，一個(gè)層次節(jié)點(diǎn)經(jīng)過樹型構(gòu)造后總的時(shí)間節(jié)點(diǎn)數(shù)為2(2n-1)，則用戶獲取訪問資源的密鑰最多經(jīng)過lblb 2(2n-1)+1次操作，達(dá)到O(lblbn)級(jí)；對(duì)于產(chǎn)生的公共邊，每個(gè)層次節(jié)點(diǎn)包括的公共邊數(shù)為2(2n-1)+lblb 2(2n-1)+1，m個(gè)層次節(jié)點(diǎn)包含公共邊數(shù)為m×2(2n-1)+lb 2(2n-1)，m個(gè)層次節(jié)點(diǎn)之間包含公共邊數(shù)為m-1，總共產(chǎn)生的公共邊數(shù)為m×(2(2n-1)+lb 2(2n-1))+(m-1)，則TCDS的公共邊數(shù)達(dá)到O(m×n+lbn).

本文最終設(shè)計(jì)的方案TCDS與現(xiàn)有文獻(xiàn)設(shè)計(jì)方案進(jìn)行比較，如表1所示:

Table 1 Comparison of Our Scheme with Previous Work

Note:diam(G)=diam(G1)+diam(G2) represents the depth sum of graphG1andG2.

通過比較可以看到，在綜合考慮用戶掌握私鑰數(shù)、用戶密鑰獲取時(shí)間和產(chǎn)生的公共信息數(shù)3方面的整體優(yōu)化情況下，本文設(shè)計(jì)的方案與現(xiàn)有其他方案比均具有明顯的優(yōu)勢(shì).

5 方案的安全性證明

下面我們針對(duì)TCDS方案(TLPOS方案是TCDS方案的特例)，利用標(biāo)準(zhǔn)模型進(jìn)行安全性證明.

5.1 方案分析

本文提出的基于時(shí)間約束的分層訪問控制方案在空間維度上，可看作是利用層次節(jié)點(diǎn)v和w之間構(gòu)成的偏序關(guān)系w≤v，使用戶獲取上層節(jié)點(diǎn)v的密鑰材料kv通過計(jì)算推導(dǎo)出下層層次節(jié)點(diǎn)w的密鑰材料kw；在時(shí)間維度上，則是利用了λ到t的包含與被包含關(guān)系，建立了時(shí)間維度上的偏序關(guān)系，即存在vt≤vλ.利用λ和t形成的偏序關(guān)系，用戶在掌握kv,λ的情況下，可通過設(shè)計(jì)安全的密鑰推導(dǎo)算法獲得kv,t，進(jìn)而能夠訪問由kv,t保護(hù)的節(jié)點(diǎn)資源.

因此，TCDS方案可利用偏序關(guān)系w≤v和偏序關(guān)系vt≤vλ，在空間和時(shí)間維度采用文獻(xiàn)[14]提出的密鑰推導(dǎo)算法或其他安全算法，建立適用于泛在感知環(huán)境的密鑰推導(dǎo)過程，將方案的安全性規(guī)約到單向散列函數(shù)的不可逆性和對(duì)稱密碼選擇明文攻擊的安全性上. 如果存在敵手A攻陷方案的概率等價(jià)于存在敵手A′攻陷方案采用的一個(gè)多項(xiàng)式時(shí)間的計(jì)算復(fù)雜難題上，那我們認(rèn)為該方案是可證明安全的.

5.2 敵手模型與系統(tǒng)目標(biāo)

我們將敵手A的攻擊能力分為3種類型.

5.3 證明過程

為了便于描述，令ζ(Setup,Derivation)表示本文提出的TCDS方案，其中Setup表示方案的初始化構(gòu)造過程，Derivation表示密鑰推導(dǎo)獲取過程.根據(jù)敵手類型的不同，分別提出命題并進(jìn)行安全性證明.

證明. 定義一系列的Game0,Game1,…,Gameh，其中Game0是敵手真正發(fā)起的游戲.每個(gè)游戲Gamei對(duì)應(yīng)任意的拓?fù)湫蛄兄泄?jié)點(diǎn)vi t展開密鑰恢復(fù)的操作.我們通過Gamei之間演變的不可區(qū)分性，從而證明敵手A1進(jìn)行Game0攻陷方案的概率是可忽略的.

1)Game0：

2)Game1：

Game1的過程與Game0基本相似，其唯一區(qū)別在于推導(dǎo)過程獲取得到的v1t所需要的公共參數(shù)e0t,1t是由真正隨機(jī)數(shù)來替代，即e0t,1t≈Ee′(sk1t). 利用Game1和Game0之間的可區(qū)分性，能構(gòu)造一個(gè)多項(xiàng)式時(shí)間算法，以不可忽略的優(yōu)勢(shì)攻陷偽隨機(jī)函數(shù)fv和對(duì)稱加密方案E.因此有

|ε1-ε0|

(1)

存在.

3) 不失一般性，對(duì)Gamei(i=1,2,…,h)進(jìn)行同樣操作.

Gamei的過程與Gamei-1相同，唯一的區(qū)別在于推導(dǎo)得到v1t密鑰材料需要的公共參數(shù)e(i-1)t,it是由另外一個(gè)隨機(jī)產(chǎn)生的值來替代，即e′≈R′(ID0),e(i-1)t,it≈Ee′(ski t)，其中R′←{0,1}κ. 利用Gamei和Gamei-1之間的可區(qū)分性，能用于構(gòu)造一個(gè)多項(xiàng)式時(shí)間算法，以不可忽略的優(yōu)勢(shì)攻陷偽隨機(jī)函數(shù)fv和對(duì)稱加密方案E.即

|εi-εi-1|

(2)

存在.

(3)

將式(1)～(3)進(jìn)行合并得到：ε0

證畢.

證明. 仍然定義一系列的Game0,Game1,…,其中Game0是敵手真正發(fā)起的游戲.每個(gè)Gamei對(duì)應(yīng)任意的拓?fù)湫蛄兄泄?jié)點(diǎn)vi t展開密鑰獲取的操作，敵手的優(yōu)勢(shì)在于能夠成功區(qū)分挑戰(zhàn)者字節(jié)流是真實(shí)密鑰還是等長隨機(jī)串.我們通過Gamei之間的不可區(qū)分性，從而證明敵手A2攻陷方案的概率是可忽略的.

1)Game0：

|ε1-ε0|

(4)

存在.

|ε1-ε0|<2negl(fv)+negl(E)

(5)

存在.

3) 不失一般性，我們對(duì)Gamei(i=1,2,…)作同樣描述.

Gamei的過程與Gamei-1相同，唯一的區(qū)別在于生成ki t的密鑰推導(dǎo)算法由隨機(jī)值代替.利用Gamei和Gamei-1之間的可區(qū)分性，能用于構(gòu)造一個(gè)多項(xiàng)式時(shí)間算法，以不可忽略的優(yōu)勢(shì)攻陷偽隨機(jī)函數(shù)fv和對(duì)稱加密方案E.即

|εi-εi-1|<2negl(fv)+negl(E)

(6)

存在.

4)Gameh：

(7)

將式(4)～(7)結(jié)論進(jìn)行合并，可得，ε0

證畢.

6 總 結(jié)

泛在感知環(huán)境下感知節(jié)點(diǎn)數(shù)量多，計(jì)算、存儲(chǔ)能力受限的特點(diǎn)，使用戶在對(duì)節(jié)點(diǎn)資源訪問過程中，需要在盡可能掌握較少密鑰、并通過較短的密鑰獲取時(shí)間和產(chǎn)生較少量的公共信息情況下，安全高效地訪問更多感知節(jié)點(diǎn)資源.而加入時(shí)間因素的情況下，使?jié)M足該實(shí)際應(yīng)用需求的分層訪問控制方案設(shè)計(jì)變得更加困難.本文在提出TLPOS方案的基礎(chǔ)上，創(chuàng)新性地利用樹重心的特性，提出基于樹重心分解的分層訪問控制方案TCDS.相比較現(xiàn)有其他方案，方案能夠滿足在用戶掌握單個(gè)密鑰的前提下，使密鑰獲取時(shí)間和產(chǎn)生的公共信息之間達(dá)到最佳平衡，從而更好地適用于泛在感知環(huán)境的實(shí)際訪問控制需求.

[1]Want R. Enabling ubiquitous sensing with RFID[J]. Computer, 2004, 37(4): 84-86

[2]Puccinelli D, Haenggi M. Wireless sensor networks: Applications and challenges of ubiquitous sensing[J]. IEEE Circuits & Systems Magazine, 2010, 5(3): 19-31

[3]Akl S, Taylor P. Cryptographic solution to a problem of access control in a hierarchy[J]. ACM Trans on Computer Systems, 1983, 1(3): 239-248

[4]Tzeng W G. A time-bound cryptographic key assignment scheme for access control in a hierarchy[J]. IEEE Trans on Knowledge and Data Engineering, 2002, 14(1): 182-188

[5]Chan H, Perrig A, Song D. Random key predistribution schemes for sensor networks[C] //Proc of IEEE Symp on Security and Privacy. Piscataway, NJ: IEEE, 2003: 197-213

[6]Santis A D, Ferrara A L, Masucci B. Enforcing the security of a time-bound hierarchical key assignment scheme[J]. Information Sciences, 2006, 176(12): 1684-1694

[7]Tang Q, Mitchell C J. Comments on a cryptographic key assignment scheme[J]. Computer Standards & Interfaces, 2005, 27(3): 323-326

[8]Yi X. Security of Chien’s efficient time-bound hierarchical key assignment scheme[J]. IEEE Trans on Knowledge and Data Engineering, 2005, 17(9): 1298-1299

[9]Wang S Y, Laih C S. Merging: An efficient solution for a time-bound hierarchical key assignment scheme[J]. IEEE Trans on Dependable and Secure Computing, 2006, 3(1): 91-100

[10]Tzeng W G. A secure system for data access based on anonymous authentication and time-dependent hierarchical keys[C] //Proc of ACM Symp on Computer and Communications Security. New York: ACM, 2006: 223-230

[11]Dacro P, De Santis A, Ferrara A L, et al. Variations on a theme by Akl and Taylor: Security and tradeoffs[J]. Theoretical Computer Science, 2010, 411(1): 213-227

[12]Ateniese G, Santis A D, Ferrara A L, et al. Provably-secure time-bound hierarchical key assignment schemes[J]. Journal of Cryptology, 2012, 25(2): 243-270

[13]Santis A D, Ferrara A L, Masucci B. New constructions for provably-secure time-bound hierarchical key assignment schemes[C] //Proc of the 12th ACM Symp on Access Control Models and Technologies. New York: ACM, 2007: 133-138

[14]Ma Jun, Guo Yuanbo, Ma Jianfeng, et al. A hierarchical access control scheme for perceptual layer of IoT[J]. Journal of Computer Research and Development, 2013, 50(6): 1267-1275 (in Chinese)(馬駿, 郭淵博, 馬建峰, 等. 物聯(lián)網(wǎng)感知層一種分層訪問控制方案[J]. 計(jì)算機(jī)研究與發(fā)展, 2013, 50(6): 1267-1275)

[15]Steeb W H. Sorting and searching[J]. Art of Computer Programming, 2005, 15(5): 27-41

[16]Kang A N C, Ault D A. Some properties of a centroid of a free tree[J]. Information Processing Letters, 1975, 4(1): 18-20

[17]Alstrup S, Holm J, Lichtenberg K D, et al. Maintaining information in fully dynamic trees with top trees[J]. ACM Trans on Algorithms, 2005, 1(2): 243-264

[18]Santis A D, Ferrara A L, Masucci B. Efficient provably-secure hierarchical key assignment schemes[J]. Theoretical Computer Science, 2011, 412(41): 5684-5699

Ma Jun, born in 1981. PhD candidate at Xidian University. His main research interests include wireless network security, key assignment.

Guo Yuanbo, born in 1975. PhD, professor and master supervisor. His main research interests include wireless network security, cryptography, computer network and information security (yuanbo_g@hotmail.com).

Ma Jianfeng, born in 1963. PhD, professor and PhD supervisor. Senior member of CCF. His main research interests include cryptography, computer network and information security (jfma@mail.xidian.edu.cn).

Zhang Qi, born in 1983. Master from Wuhan University of Technology. His main research interests include wireless network security, computer network and information security (zhangqi_qian@163.com).

A Time-Bound Hierarchical Access Control Scheme for Ubiquitous Sensing Network

Ma Jun1,2, Guo Yuanbo2, Ma Jianfeng1, and Zhang Qi2

1(SchoolofComputerScienceandTechnology,XidianUniversity,Xi’an710071)2(PLAInformationEngineeringUniversity,Zhengzhou450001)

In order to realize an effective access control of sensitive data captured by sensor nodes, researchers have made great achievements on secure and efficient hierarchical access control to satisfy the features of widespread distribution, large universe, limited computation and storage capacity of sensor nodes in ubiquitous sensing network. However, time is the main factor that makes the requirements of hierarchical access control scheme in ubiquitous sensing network different from that in traditional Internet networks, leading to the limited actual application scenario. According to the users’ requirement on the nodes for gathering resources, an efficient and secure time-bound hierarchical access control scheme is presented in this paper. Based on the characteristics of perception node in ubiquitous sensing network, including the limited power and computation capability, as well as the storage resource, the scheme optimizes the key storage of user, key derivation time, and public information. The advantages of our scheme include that 1) only one key material is required in each users’access; 2) the balance can be achieved between the time for key acquisition and the amount of public information and 3) the scheme is provably secure without random oracle model. Theoretical analysis indicates that our proposed schedule adapts to user’ access control requirement of ubiquitous sensing network.

time-bound; centroid of tree; hierarchical access control; ubiquitous sensing; key derivation

2015-10-19；

2016-04-11

長江學(xué)者和創(chuàng)新團(tuán)隊(duì)發(fā)展計(jì)劃基金項(xiàng)目(IRT1078)；中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(JY10000903001)；國家自然科學(xué)基金項(xiàng)目(61602515);河南省科技攻關(guān)項(xiàng)目(2016170162)；信息保障重點(diǎn)實(shí)驗(yàn)室開放課題(KJ-15-103) This work was supported by the Program for Changjiang Scholars and Innovative Research Team in University (IRT1078), the Fundamental Research Funds for the Central Universities (JY10000903001), the National Natural Science Foundation of China (61602515), the Science and Technology Research Project of Henan Province (2016170162), and the Foundation of Science and Technology on Information Assurance Laboratory (KJ-15-103).

TP309