基于廣播加密的多策略非對(duì)稱(chēng)叛逆者追蹤方案

康桂花

(成都東軟學(xué)院，成都，611844)

基于廣播加密的多策略非對(duì)稱(chēng)叛逆者追蹤方案

康桂花

(成都東軟學(xué)院，成都，611844)

雙線(xiàn)性映射叛逆者追蹤方案不能抵抗叛逆者攻擊，且計(jì)算量與用戶(hù)數(shù)量相關(guān)，計(jì)算效率很低。為了減少計(jì)算量、存儲(chǔ)量和通信量，提高安全性能，基于離散對(duì)數(shù)難題，提出多策略、多服務(wù)、非對(duì)稱(chēng)公鑰叛逆者追蹤方案，進(jìn)行了安全性證明和效率分析。該方案通過(guò)改變門(mén)限值t實(shí)現(xiàn)了多策略廣播，可靈活運(yùn)用于不同的網(wǎng)絡(luò)廣播領(lǐng)域。分析表明，方案具有更高的計(jì)算效率和更短的密文長(zhǎng)度，同時(shí)該方案被證明可實(shí)現(xiàn)面向多服務(wù)、抗共謀性、完全撤銷(xiāo)性、完全可恢復(fù)性和黑盒追蹤性。

叛逆者追蹤;安全性分析;多策略;面向多服務(wù);非對(duì)稱(chēng)公鑰

0 引 言

隨著計(jì)算機(jī)技術(shù)、數(shù)據(jù)通信技術(shù)和互聯(lián)網(wǎng)的快速發(fā)展，社會(huì)對(duì)通信網(wǎng)絡(luò)的依賴(lài)度越來(lái)越大，通過(guò)互聯(lián)網(wǎng)提供的服務(wù)也越來(lái)越多。大部分網(wǎng)絡(luò)應(yīng)用和服務(wù)都是通過(guò)廣播方式實(shí)現(xiàn)，如付費(fèi)電視、金融信息服務(wù)、衛(wèi)星通信、各行業(yè)內(nèi)敏感數(shù)據(jù)庫(kù)服務(wù)，比如銀行內(nèi)部的客戶(hù)信用卡信息等。為了防止非授權(quán)用戶(hù)非法竊取信息或得到服務(wù)，數(shù)據(jù)提供商(data supplier, DS)加密通過(guò)網(wǎng)絡(luò)廣播的消息，并將解密密鑰提供給合法的授權(quán)用戶(hù)。個(gè)別合法用戶(hù)或合法用戶(hù)們合謀(稱(chēng)為叛逆者)計(jì)算出新解密鑰，或者將自己的解密鑰，出售給非授權(quán)用戶(hù)(稱(chēng)為盜版者)以獲取利益。針對(duì)這種盜版行為，Chor等人[1]提出了叛逆者追蹤的概念：通過(guò)分析盜版者的解碼器追蹤到至少一個(gè)叛逆者。叛逆者追蹤可以有效打擊盜版行為，極大地保護(hù)數(shù)據(jù)提供商的經(jīng)濟(jì)利益。

自Chor后，叛逆者追蹤得到了更多學(xué)者的研究。其中具有風(fēng)向標(biāo)意義的是Boneh等人提出的公鑰叛逆者追蹤方案[2]，因?yàn)榉桨钢蠨S發(fā)送的廣播分組長(zhǎng)度與用戶(hù)數(shù)量無(wú)關(guān)。此后各種基于不同公鑰密碼體制的叛逆者方案被相繼提了出來(lái)[3-14]。但是這些方案絕大多數(shù)都不能同時(shí)滿(mǎn)足完全抗共謀性、黑盒追蹤性、完全撤消性、完全可恢復(fù)性，而且其中大多數(shù)是基于雙線(xiàn)性映射的[2-6,10,13-14]。相較與其他計(jì)算，雙線(xiàn)性映射所需的計(jì)算量是比較大的(據(jù)統(tǒng)計(jì)，一個(gè)對(duì)運(yùn)算大約相當(dāng)于8個(gè)有限域上模冪運(yùn)算的計(jì)算量[15])，而且這些方案中絕大多數(shù)都存在著計(jì)算量、密文長(zhǎng)度隨著用戶(hù)數(shù)量增加而增加的缺陷。相較而言，基于大整數(shù)分解問(wèn)題的叛逆者追蹤方案[7-9,11]還比較少。文獻(xiàn)[7-8]已經(jīng)被證明是不安全的，文獻(xiàn)[9]雖然可以實(shí)現(xiàn)完全抗共謀性，但不能實(shí)現(xiàn)可撤銷(xiāo)性。王云等[10]于2012年提出了一個(gè)基于身份和雙線(xiàn)性映射的、安全性基于有限域上離散對(duì)數(shù)問(wèn)題和判定性問(wèn)題的方案，但仍然無(wú)法克服一般基于身份密碼體制方案的固有缺陷。張學(xué)軍等[11]于2008年提出一個(gè)基于大整數(shù)分解難題的面向多服務(wù)的方案，該方案聲稱(chēng)滿(mǎn)足完全抗共謀性，且密文長(zhǎng)度、密鑰長(zhǎng)度與用戶(hù)數(shù)量無(wú)關(guān)，但2013年文獻(xiàn)[12]給出了針對(duì)該方案的一種共謀攻擊，證明了3個(gè)或3個(gè)以上合法用戶(hù)可以合謀生成一個(gè)新的解密鑰并逃避追蹤。2009年王青龍等提出了一個(gè)基于雙線(xiàn)性映射的具有完全抗共謀性、完全撤銷(xiāo)性、完全恢復(fù)性的叛逆者追蹤方案[13]，但被證明實(shí)際上該方案不能實(shí)現(xiàn)完全撤銷(xiāo)性，即被撤銷(xiāo)的用戶(hù)仍然能夠用原來(lái)的解密鑰正確解密出密文[14]。

2013年，王曉明等[14]提出了新的基于雙線(xiàn)性映射的叛逆者追蹤方案(以下簡(jiǎn)稱(chēng)WXM方案)，該方案使用多項(xiàng)式和過(guò)濾函數(shù)構(gòu)建，并具有完全抗共謀性、完全可恢復(fù)性、黑盒追蹤性和完全撤銷(xiāo)性。針對(duì)該方案提出一種攻擊方法，使得任何一個(gè)叛逆者可以通過(guò)自己的解密鑰構(gòu)造出新的解碼器提供給盜版者，但數(shù)據(jù)提供商無(wú)法通過(guò)追蹤算法找出叛逆者，從而逃避追蹤。

一般來(lái)說(shuō)，付費(fèi)電視、網(wǎng)絡(luò)服務(wù)、行業(yè)內(nèi)部數(shù)據(jù)庫(kù)等基于廣播的應(yīng)用系統(tǒng)，其用戶(hù)數(shù)量非常巨大，多則幾百萬(wàn)人，少則幾萬(wàn)人。但是，絕大多數(shù)典型追蹤方案，或者公鑰、密文長(zhǎng)度與用戶(hù)數(shù)成正比，或者構(gòu)造多項(xiàng)式的次數(shù)≥用戶(hù)數(shù)，這使得方案的計(jì)算量非常巨大，不能滿(mǎn)足實(shí)際需求。

基于如上所述的原因，并針對(duì)文獻(xiàn)[13-14]的安全性缺陷和大多數(shù)方案計(jì)算量過(guò)大的問(wèn)題，本文提出了一個(gè)基于離散對(duì)數(shù)問(wèn)題的、非對(duì)稱(chēng)公鑰的、面向多服務(wù)、多策略的叛逆者追蹤方案，進(jìn)行了安全性分析和效率對(duì)比。與大多數(shù)方案相比，本文方案的安全性能和計(jì)算效率更高，有以下突出的優(yōu)點(diǎn)：①多策略：通過(guò)改變門(mén)限值實(shí)現(xiàn)了多策略廣播，可靈活應(yīng)用于各種網(wǎng)絡(luò)廣播領(lǐng)域；②公鑰長(zhǎng)度、用戶(hù)解密鑰長(zhǎng)度、廣播密文長(zhǎng)度均與用戶(hù)數(shù)量無(wú)關(guān)；③方案采用二分法實(shí)現(xiàn)黑盒追蹤；④完全抗共謀性：無(wú)論多少數(shù)量的用戶(hù)共謀均不能構(gòu)造出新的解密鑰；⑤完全撤銷(xiāo)性：只需要修改廣播密文，不需要更新其他合法用戶(hù)的解密鑰，就可方便地撤銷(xiāo)叛逆者用戶(hù)，或者用戶(hù)取消訂閱服務(wù)；⑥完全可恢復(fù)性：對(duì)于已撤銷(xiāo)用戶(hù)，或取消訂閱服務(wù)的用戶(hù)，不需要更新其密鑰就可恢復(fù)其解密能力或恢復(fù)訂閱。在大多數(shù)應(yīng)用場(chǎng)景中(如付費(fèi)電視)，性質(zhì)⑤和⑥非常實(shí)用。

1 針對(duì)WXM方案的安全性攻擊

1.1 WXM方案

WXM方案的安全性基于離散對(duì)數(shù)難題和判定Diffie-Hellman難題[14]。方案簡(jiǎn)述如下。

1)系統(tǒng)設(shè)置。

設(shè)p,q是2個(gè)大素?cái)?shù)，q|(p-1)，G1為q階加法循環(huán)群，G為p-1階乘法循環(huán)群，G2是G中階為q的循環(huán)子群，P是G1上的本原元。e:G1×G1→G2是G1到G2的雙線(xiàn)性映射，記g=e(P,P)。

DS隨機(jī)選擇α,X={x1,x2,…,xn}(n是已注冊(cè)用戶(hù)數(shù),n

2)用戶(hù)注冊(cè)。

設(shè)用戶(hù)Ui申請(qǐng)加入系統(tǒng)。DS為Ui任選一個(gè)未被分配的xi，計(jì)算

(1)

(xi,ki)就是Ui的解密鑰，DS將其發(fā)送給Ui。

DS再隨機(jī)選擇一個(gè)多項(xiàng)式

(2)

DS利用(xi,f(xi))和(wi,f′(wi))(i=1,2,…,t)構(gòu)造多項(xiàng)式

(3)

(3)式中，aij是fi(x)的系數(shù)。DS記錄Ui和e(P,P)fi(x0)作為用戶(hù)Ui的注冊(cè)信息存放在身份數(shù)據(jù)庫(kù)中。如果e(P,P)fi(x0)與某個(gè)已注冊(cè)用戶(hù)的對(duì)應(yīng)記錄相等則重新選擇f′(x)。

3)加密算法。

c2=rP,c3=Me(P,rf(x0)P)

(4)

然后DS廣播(c1(x),c2,c3)。

4)解密算法。

用戶(hù)Ui接收到廣播密文后，向解碼器輸入(c1(x),c2,c3)和公鑰pub。

解碼器使用解密鑰(xi,ki)計(jì)算

c1(ki)=rα-1

(5)

記Lj為用{xi,w1,w2,…,wt}計(jì)算出f(x0)時(shí)點(diǎn)wj的Lagrange插值系數(shù)，則

(6)

(7)

(8)

5)追蹤算法。

當(dāng)DS收繳到一個(gè)盜版解碼器后，設(shè)其解密鑰為(xi,ki)，DS任選(xr,Mr,r)并計(jì)算

(9)

c2=rP,c3=Mre(P,rf(xr)P)

(10)

然后向盜版解碼器輸入(c1(x),c2,c3)和{x0,(wi,e(P,P)αf′(wi))(i=1,2,…,t)}，則解碼器進(jìn)行以下計(jì)算并輸出M′

c1(ki)=rα-1，

(11)

(12)

(13)

(14)

DS根據(jù)M′計(jì)算

e(P,P)fi(x0)=[M′-1Mre(P,rf(xr)P)]r-1

(15)

將計(jì)算出的e(P,P)fi(x0)與數(shù)據(jù)庫(kù)中記錄相比較，找到對(duì)應(yīng)的Ui，則Ui就是叛逆者。

6)撤銷(xiāo)算法。

如果要撤銷(xiāo)某些用戶(hù)，DS只需要在廣播消息時(shí)，將過(guò)濾函數(shù)c1(x)中與這些撤銷(xiāo)用戶(hù)Ui相對(duì)應(yīng)的(x-ki)從乘積項(xiàng)中移除即可。

7)恢復(fù)算法。

如果需要恢復(fù)某些已撤銷(xiāo)用戶(hù)，DS只需要做撤銷(xiāo)算法的逆操作，即將欲恢復(fù)用戶(hù)Ui對(duì)應(yīng)的(x-ki)再加入到c1(x)的乘積項(xiàng)中。

1.2 針對(duì)WXM方案的安全性攻擊

WXM方案[14]聲稱(chēng)至少可以追蹤到一個(gè)叛逆者。本文給出一種攻擊方法，可以使其無(wú)法追蹤到叛逆者。

設(shè)用戶(hù)Ui的解密鑰為(xi,ki)。Ui進(jìn)行如下操作。

1)利用某次接收到的廣播消息(c1(x),c2,c3)，結(jié)合解密鑰ki可以算出：rα-1=c1(ki)

通過(guò)比較多項(xiàng)式c1(x)的系數(shù)，可以得到其最高次項(xiàng)系數(shù)λ，通過(guò)把x=0代入多項(xiàng)式可以求出

(16)

2)重復(fù)自己接收到廣播消息(c1(x),c2,c3)的解密過(guò)程，可以算出Lj，bi和

e(P,rf(x0)P)=e(P,kic2)bi=grf(x0)

(17)

因此：gαf(x0)=(grf(x0))(rα-1)-1modp

(18)

(19)

(20)

3.2)同正常解碼器方法計(jì)算bi

(21)

(22)

3.3)修改解密密文計(jì)算公式

(23)

1.3 對(duì)WXM方案的分析

WXM方案同許多典型方案一樣，存在相同效率上的缺陷。

2 新的多策略叛逆者追蹤方案

針對(duì)目前大多數(shù)方案的計(jì)算量和通信量過(guò)大，計(jì)算效率低下的缺陷，提出多策略、多服務(wù)、非對(duì)稱(chēng)公鑰的追蹤方案。

現(xiàn)實(shí)社會(huì)中，不同廣播系統(tǒng)的用戶(hù)數(shù)量和用戶(hù)重要性相差很大，需要區(qū)別對(duì)待。有些付費(fèi)電視系統(tǒng)，用戶(hù)量數(shù)以萬(wàn)計(jì)，有些廣播系統(tǒng)、收費(fèi)查詢(xún)系統(tǒng)的安全性要求特別高。當(dāng)用戶(hù)數(shù)量特別大時(shí)，可以把他們按照地理位置再細(xì)分為若干個(gè)廣播子系統(tǒng)，比如北京市的收費(fèi)電視，可以再按宣武區(qū)、朝陽(yáng)區(qū)等進(jìn)一步劃分為多個(gè)子區(qū)，每個(gè)子區(qū)分別發(fā)送不同廣播密文的電視廣播，而對(duì)安全性要求特別高的系統(tǒng)(如軍事、金融系統(tǒng))，則可以通過(guò)加大門(mén)限值，增大密鑰長(zhǎng)度、廣播密文長(zhǎng)度等方法，提供更高的安全保障。也就是說(shuō)，不同廣播系統(tǒng)需要采取不同的廣播策略。

現(xiàn)有的許多方案都是對(duì)稱(chēng)公鑰的，即DS知道被授權(quán)用戶(hù)的解密鑰，這樣一來(lái)，即使發(fā)現(xiàn)叛逆者，DS也無(wú)法提供有效證據(jù)進(jìn)行控訴，證明叛逆行為不是自己所為。本文利用不經(jīng)意多項(xiàng)式估值協(xié)議(oblivious polynomial evaluation protocol, OPE)，提出一種非對(duì)稱(chēng)公鑰方案，即用戶(hù)的解密鑰只有自己一方知道，從而方案具有不可否認(rèn)性，使追蹤更具有效力。

方案的參與者由三方組成：系統(tǒng)管理者SM、數(shù)據(jù)提供者DS、用戶(hù)。方案由以下幾個(gè)部分組成。

2.1 系統(tǒng)初始化

設(shè)廣播系統(tǒng)將用戶(hù)按區(qū)域劃分為e個(gè)區(qū)(根據(jù)實(shí)際需要確定e，比如e=10)，每區(qū)采用一個(gè)廣播策略，不同區(qū)域的廣播策略是不同的，或者系統(tǒng)按照安全性要求的高低采用e個(gè)廣播策略中的某一個(gè)策略，并定期變換策略。t1,t2,…,te是不同策略時(shí)的門(mén)限值，不妨設(shè)t1

系統(tǒng)管理者SM確定系統(tǒng)參數(shù)：

a0≡d1modq1,a0≡d2modq2, … ,

a0≡demodqe

4)SM構(gòu)造te次多項(xiàng)式

f(x)=a0+a1x+…+atextemodQ

再計(jì)算每個(gè)策略l對(duì)應(yīng)的tl次多項(xiàng)式

fl(x)=f(x)modql

5)在執(zhí)行策略l的子系統(tǒng)，SM公布該策略的公鑰(tl為策略l的門(mén)限)

下面以策略l為例說(shuō)明方案。

2.2 服務(wù)注冊(cè)

DS為服務(wù)W向SM注冊(cè)：設(shè)W的說(shuō)明文字為IDW，DS計(jì)算bW=h(IDW)作為對(duì)服務(wù)W的授權(quán)值并秘密發(fā)送給SM，bW必須由SM秘密保存，不能泄露。SM生成多項(xiàng)式Fl,W(x,y)=fl(x) +bWy。

2.3 用戶(hù)注冊(cè)

2.4 用戶(hù)訂閱服務(wù)

Ui向SM訂閱服務(wù)W：Ui和SM執(zhí)行OPE協(xié)議，得到自己訂閱服務(wù)W的服務(wù)解密鑰Ki,W=Fl,W(xi,σi)=fl(xi)+bWσi(modql)。因?yàn)閳?zhí)行OPE協(xié)議，SM得不到σi和Ki,W的任何信息。

當(dāng)用戶(hù)首次加入系統(tǒng)時(shí)，必須先注冊(cè)再訂閱服務(wù)，當(dāng)他已訂閱了一項(xiàng)服務(wù)再訂閱另一項(xiàng)服務(wù)時(shí)，就不需再注冊(cè)，只需執(zhí)行2.4節(jié)算法即可。

2.5 廣播加密

(24)

2.6 解密

1)用戶(hù)Ui利用自己的解密鑰(xi,σi,Ki,W)和數(shù)據(jù)頭，先計(jì)算出

(25)

(26)

(26)式中：λj,λi是Lagrange插值系數(shù)。

易證，對(duì)于給定消息頭和密文，任何合法的授權(quán)用戶(hù)都可以正確解密出密文。

2.7 黑盒追蹤

可以采用二分法確定叛逆者或叛逆者集合，且是黑盒追蹤。

先將用戶(hù)劃分為若干個(gè)用戶(hù)子集，每個(gè)子集的用戶(hù)數(shù)≤門(mén)限tl，依次對(duì)用戶(hù)子集進(jìn)行追蹤。不妨設(shè)被懷疑的用戶(hù)子集U={U1,U2,…,Um1}(m1≤tl)。

2)將輸入盜版解碼器，其中，E(.)是對(duì)稱(chēng)加密算法，Es(M)是用密鑰s對(duì)消息M進(jìn)行加密。

3)如果輸出的是消息M，則U中沒(méi)有叛逆者，否則U中有叛逆者，這時(shí)可以將U按二分法劃分為2個(gè)子集后進(jìn)一步追查，直到找出叛逆者或叛逆者集合為止。

由追蹤算法可知，本方案的門(mén)限值tl可以遠(yuǎn)遠(yuǎn)小于用戶(hù)數(shù)，加上將用戶(hù)分區(qū)，每區(qū)采用不同策略，就可以使廣播多項(xiàng)式fl(x)的次數(shù)維持在一個(gè)相當(dāng)小的整數(shù)值，從而大大減少了計(jì)算量，提高了效率。

2.8 用戶(hù)撤銷(xiāo)

如果要撤銷(xiāo)某些用戶(hù)的接收權(quán)，DS只需要將這些用戶(hù)的身份信息xi加入到廣播點(diǎn)集Y中，即

2.9 用戶(hù)取消訂閱

如果用戶(hù)Ui要取消對(duì)服務(wù)W的訂閱，類(lèi)似于用戶(hù)撤銷(xiāo)算法，DS將用戶(hù)的身份信息xi添加到廣播點(diǎn)集Y中，用戶(hù)就無(wú)法接收服務(wù)W的廣播了。

2.10 恢復(fù)用戶(hù)和用戶(hù)恢復(fù)訂閱

2.11 叛逆者人數(shù)超過(guò)門(mén)限時(shí)的撤銷(xiāo)

當(dāng)叛逆者人數(shù)超過(guò)門(mén)限值時(shí)，DS只需要重新選擇一個(gè)門(mén)限值超過(guò)叛逆者人數(shù)的策略l′，即選擇策略l′使其滿(mǎn)足tl′>叛逆者人數(shù)，再按正常方式廣播。此時(shí)SM要重新計(jì)算、公布公鑰PK。

由2.8,2.9,2.10,2.11節(jié)可知，方案具有完全可恢復(fù)性、完全撤銷(xiāo)性。

3 安全性分析和效率對(duì)比

3.1 安全性分析

定理1(安全性) 在離散對(duì)數(shù)困難問(wèn)題假設(shè)下，方案能被攻擊者正確解密的概率為(1/p+1/q)，是可以忽略的。方案是安全的。

證明假設(shè)非合法用戶(hù)的攻擊者，能從消息頭解密出sW。設(shè)他的解密鑰為(z1,z2,z3)，則有

z3=fl(z1) +bWz2(modql)

(27)

定理2(抗共謀性) 共謀用戶(hù)數(shù)為k(k≥1)的某些合法用戶(hù)通過(guò)共謀構(gòu)造出一個(gè)新解密鑰在計(jì)算上是不可行的，其計(jì)算復(fù)雜度等價(jià)于求解離散對(duì)數(shù)問(wèn)題。方案具有完全抗共謀性。

證明先考慮k=1的情況。

假設(shè)有2個(gè)用戶(hù)Ui,Uj合謀構(gòu)造新解密鑰。一方面，由解密鑰等式構(gòu)成的方程組為

有2個(gè)方程3個(gè)變量，無(wú)法解方程組從而求出fl(xi),fl(xj)。另一方面，如上所述，由公鑰PK或廣播密文構(gòu)造新解密鑰，等價(jià)于求解離散對(duì)數(shù)問(wèn)題，在計(jì)算上是不可行的。

定理3黑盒追蹤算法可以追蹤到任何盜版者。

反之，如果U中沒(méi)有叛逆者，盜版解碼器的解密鑰與U的份額{x1,x2,…,xm1}無(wú)關(guān)，那么就算測(cè)試消息頭C中選用了點(diǎn)x1,x2,…,xm1，依然可以正確解密出密文M。當(dāng)正確解密出M時(shí)，可以證明U中沒(méi)有叛逆者。

在確定叛逆者所在子集后，運(yùn)用二分法進(jìn)一步縮小范圍，可找出叛逆者集合。二分法的計(jì)算次數(shù)為lbm1(m1是集合U中元素的個(gè)數(shù))，因此查找速度是非?？斓?。

3.2 效率對(duì)比

本文方案是多策略的，即在不同廣播系統(tǒng)應(yīng)用領(lǐng)域或不同用戶(hù)區(qū)域，選用不同的門(mén)限值tl、素?cái)?shù)ql、生成元gl。相比于一般方案，本方案的多項(xiàng)式次數(shù)tl(即門(mén)限值)是一個(gè)固定的常量，可以遠(yuǎn)遠(yuǎn)小于用戶(hù)數(shù)n，且本文方案不含對(duì)運(yùn)算。反觀(guān)其他典型方案，包含O(n)個(gè)對(duì)運(yùn)算，多項(xiàng)式的次數(shù)也為n。如果用戶(hù)數(shù)n=10 000，則包含約10 000個(gè)對(duì)運(yùn)算，多項(xiàng)式的次數(shù)為10 000次，計(jì)算效率非常低下。因此，本文方案明顯地降低了計(jì)算量、存儲(chǔ)量、通信量，大大提高了效率。

表1、表2列出了本文方案和其他3種典型方案的計(jì)算量和性能對(duì)比。表1只統(tǒng)計(jì)了加密和解密過(guò)程中(其他過(guò)程不經(jīng)常發(fā)生)的對(duì)運(yùn)算、模冪運(yùn)算的次數(shù)，因?yàn)楹退鼈兿啾?，其他運(yùn)算的耗時(shí)量可忽略不計(jì)。同等安全級(jí)別下，雙線(xiàn)性對(duì)運(yùn)算相對(duì)于其他運(yùn)算(如模冪運(yùn)算)是最耗時(shí)的，1個(gè)對(duì)運(yùn)算約等于8個(gè)模冪運(yùn)算[15]，因此應(yīng)當(dāng)盡量減少對(duì)運(yùn)算的個(gè)數(shù)。設(shè)Pa表示1次對(duì)運(yùn)算，E表示1次模冪運(yùn)算，n，N，s分別表示用戶(hù)數(shù)、最大用戶(hù)數(shù)、大于N的一個(gè)整數(shù)，t,m,k為與用戶(hù)數(shù)無(wú)關(guān)的整數(shù)，t是門(mén)限值，Y=pq為RSA中的模。|M|為整數(shù)M的比特位長(zhǎng)度，len(G)為群G中元素的比特位長(zhǎng)度。

由表1可知，由于本文方案沒(méi)有對(duì)運(yùn)算，其計(jì)算量遠(yuǎn)遠(yuǎn)小于文獻(xiàn)[13-14]方案，略高于文獻(xiàn)[11]。除了計(jì)算量上的優(yōu)勢(shì)，再考慮到密鑰長(zhǎng)度、廣播密文長(zhǎng)度、黑盒追蹤效率，以及多策略、多服務(wù)、非對(duì)稱(chēng)密鑰、完全可撤銷(xiāo)性、完全可恢復(fù)性等安全性能，本文方案相比于其他方案都具有明顯的優(yōu)勢(shì)。

表1 4種方案的計(jì)算量

表2 4種方案的性能對(duì)比

通過(guò)在Visual C++ 6.0中調(diào)用OpenSSL 1.0.0密碼函數(shù)庫(kù)，可以編程實(shí)現(xiàn)對(duì)本文方案的仿真實(shí)驗(yàn)。

仿真測(cè)試平臺(tái)為Windows7, Intel Core4 CPU 4 GHz, 4 GB內(nèi)存。不失一般性，設(shè)最大用戶(hù)數(shù)N=200,用戶(hù)數(shù)n=100,e=3,t1=5,t2=9,t3=12,s=202,會(huì)話(huà)密鑰sW為128位。方案中的各項(xiàng)數(shù)據(jù)p,ql,gl,xi,σi,yi,sW等均隨機(jī)生成。表3給出了方案運(yùn)行5次的平均運(yùn)行時(shí)間統(tǒng)計(jì)。

表3 本文方案主要階段平均耗時(shí)統(tǒng)計(jì)(t3=12) (單位：s)

可以看出，方案在初始化階段耗時(shí)較多，在廣播加密和解密階段耗時(shí)較少。由于初始化階段在系統(tǒng)生命周期中只需運(yùn)行一次，不會(huì)影響方案的后期運(yùn)行效率，此外，其他階段只在有需要時(shí)才運(yùn)行，平時(shí)不會(huì)運(yùn)行。因此表3的仿真結(jié)果表明方案是高效可行的。

不考慮其他階段，只對(duì)廣播加密、解密2個(gè)階段統(tǒng)計(jì)運(yùn)行時(shí)間并求和，本文方案與文獻(xiàn)[14]的平均運(yùn)行時(shí)間對(duì)比如表4所示(運(yùn)行5次)。

表4 本文方案與文獻(xiàn)[14]平均耗時(shí)對(duì)比(單位：s)

實(shí)驗(yàn)結(jié)果表明，相較于文獻(xiàn)[14]，本文方案的計(jì)算時(shí)間顯著減少，計(jì)算效率大幅提升。另外，從表4可以看出，門(mén)限值tl對(duì)方案運(yùn)行時(shí)間有一定影響，門(mén)限值越大運(yùn)行時(shí)間越長(zhǎng)，但增加的運(yùn)行時(shí)間可以接受(特別是CPU運(yùn)算速度進(jìn)一步提高的情況下)。在兼顧保障安全性、提高運(yùn)行效率的情況下，tl的最佳值選取在[7,15]。

4 結(jié)束語(yǔ)

本文對(duì)WXM方案[14]進(jìn)行了詳細(xì)分析，發(fā)現(xiàn)該方案存在著無(wú)法追蹤到叛逆者的安全性缺陷，用戶(hù)只要對(duì)解密鑰和解密算法進(jìn)行簡(jiǎn)單改造即可逃避追蹤，同時(shí)該方案和許多典型方案一樣，計(jì)算量過(guò)大，計(jì)算效率很低。針對(duì)這些問(wèn)題，本文提出了一個(gè)多策略可靈活應(yīng)用于各種領(lǐng)域、面向多服務(wù)、非對(duì)稱(chēng)公鑰叛逆者追蹤方案。方案不僅克服了WXM方案的缺陷，還同時(shí)滿(mǎn)足完全抗共謀性、黑盒追蹤性、完全撤銷(xiāo)性和完全可恢復(fù)性等安全性要求，采用二分法實(shí)現(xiàn)黑盒追蹤，并通過(guò)非常簡(jiǎn)單的方法，實(shí)現(xiàn)了在撤銷(xiāo)用戶(hù)及恢復(fù)用戶(hù)(或用戶(hù)撤銷(xiāo)及恢復(fù)服務(wù))時(shí)的公鑰、其他合法用戶(hù)解密鑰均不受影響的優(yōu)點(diǎn)。與大多數(shù)方案相比，方案的計(jì)算效率更高，更靈活，并可廣泛應(yīng)用在不同領(lǐng)域，例如對(duì)計(jì)算效率和安全性要求更高的應(yīng)用場(chǎng)景。

[1] CHOR B, FIAT A, NAOR M. Tracing traitors[C]∥Advances in Cryptology-CRYPT’94, Lecture Notes in Computer Science. Berlin: Springer, 1994, 257-270.

[2] BONEH D, FRANKLIN M. An efficient public key traitor tracing scheme[C] //Proc of CRYPTO’99. Berlin: Springer, 1999: 338-353.

[3] BONEH D, WATERS B. A fully collusion resistant broadcast, trace, and revoke system[C] //Proc of the 13th ACM Conference on Computer and Communications Security. Berlin: Springer, 2006, 211-220.

[4] FURUKAWA J, ATTRAPADUNG N. Fully collusion resistant black box traitor tracing revocable broadcast encryption with short private keys[C] //Proc of the 34th International Colloquium on Automata, Languages and Programming. Berlin: Springer, 2007: 496-508.

[5] GARG S, KUMARASUBRAMANIAN A, SAHAI A, et al. Building efficient fully collusion-resilient traitor tracing and revocation schemes[EB/OL]. [2012-06-01]. http://eprint.iacr.org/2009/532.pdf.

[6] PARK J H, LEE D H. Fully collusion-resistant traitor tracing scheme [EB/OL]. [2010-12-09]. http://protocol.korea.ac.kr/publication/Fully collusion-resistant traitor tracing scheme with shorter ciphertexts.pdf.

[7] 馬華,曹正文.基于RSA加密算法的叛逆者追蹤方案[J].西安電子科技大學(xué)學(xué)報(bào),2004,31(4):611-613. MA Hua, CAO Zhengwen. A traitor tracing scheme based on RSA[J]. Journal of Xidian University, 2004, 31(4):611-613.

[8] 馮慧娟,馬華,楊波.一種新的基于RSA加密算法的叛逆者追蹤方案[J].計(jì)算機(jī)應(yīng)用研究,2007,24(5):135-137. FENG Huijuan, MA Hua, YANG Bo. New traitor tracing scheme based on RSA[J]. Application Research of Computers, 2007, 24(5):135-137.

[9] 王青龍,楊波,韓臻，等.免共謀公鑰叛逆者追蹤方案[J].通信學(xué)報(bào),2006, 27(12):6-9 WANG Qinglong, YANG Bo, HAN Zhen, et al. Collusion-free public-key traitor tracing scheme[J]. Journal on Communications, 2006, 27(12):6-9.

[10] 王云,蘆殿軍,張秉儒.基于身份的公鑰叛逆者追蹤方案[J].青海師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2012(1): 31-35. WANG Yun, LU Dian jun, Zhang bing ru. A traitor tracing scheme based on bilinear map[J]. Journal of Qinghai Normal University：Natural Science, 2012(1): 31-35.

[11] 張學(xué)軍.新的面向多服務(wù)的叛逆者追蹤方案[J].電子科技大學(xué)學(xué)報(bào), 2008, 37(3):404-407. ZHANG Xuejun. A new multi-services oriented traitor tracing scheme[J]. Journal of University of Electrical Science and Technology of China, 2008, 37(3):404-407.

[12] 王青龍,徐麗.兩個(gè)叛逆者追蹤方案的安全性分析[J].計(jì)算機(jī)工程與科學(xué).2013, 35(6):78-81. WANG Qinglong, XU Li. Security analysis of two traitor tracing schemes[J]. Computer Engineering and Science, 2013, 35(6):78-81.

[13] 王青龍,韓臻,楊波.基于雙線(xiàn)性映射的叛逆者追蹤方案[J].計(jì)算機(jī)研究與發(fā)展,2009,46(3):384-389.

WANG Qinglong,HAN Zhen,YANG Bo.A traitor tracing scheme based on bilinear map[J].Journal of Computer Research and Development,2009,46(3):384-389.

[14] 王曉明,姚國(guó)祥,廖志委.一個(gè)叛逆者追蹤方案分析和改進(jìn)[J].計(jì)算機(jī)研究與發(fā)展,2013,50(10):2092-2099. WANG Xiaoming, YAO Guoxiang, LIAO Zhiwei, Cryptanalysis and Modification of a Traitor Tracing Scheme[J]. Journal of Computer Research and Development, 2013, 50(10): 2092-2099.

[15] KAWAHARA Y, TAKAGI T, OKAMOTO E. Efficient implementation of Tate Pairing on a Mobile Phone Using Java[C]∥Lecture Notes in Computer Science. Berlin: Springer-Verlag, 2007: 396-405.

康桂花(1962-)，女，浙江東陽(yáng)人，副教授，主要研究方向?yàn)樾畔踩?、網(wǎng)絡(luò)協(xié)議和計(jì)算機(jī)應(yīng)用。E-mail: 841936744@qq.com。

(編輯：張 誠(chéng))

A multi-policy asymmetric traitor tracing scheme based on broadcast encryption

KANG Guihua

(Chengdu Neusoft University, Chengdu 611844, P.R. China)

It was found that the scheme could not resist collusion attack and is similar to most schemes, its efficiency is very low because of relating to the quantity of users. In order to improve safety performance and to reduce the amount of computation, storage, communication, based on discrete logarithm problem, a new multi-policy multi-service asymmetric public-key traitor tracing scheme is proposed. The new scheme can be used flexibly in all kinds of domain because multi-policy broadcast has been realized by using different threshold value t. Compared to most typical schemes, the scheme has higher computation efficiency and shorter cipher text length, it also has stronger safety features since multi-service oriented, collusion resistance, full revocation, full recoverability, and black-box traceability can be realized.

traitor tracing; security analysis; multi-policy; multi-service oriented; asymmetric public-key

10.3979/j.issn.1673-825X.2016.06.022

2016-02-18

2016-10-05

康桂花 841936744@qq.com

2015年度電子信息類(lèi)專(zhuān)業(yè)教指委研究課題(2015-Y13)；四川省教育廳2014年度重點(diǎn)科研項(xiàng)目(14ZA0346；SCJG2014-741)；四川省教育廳2013年度科研項(xiàng)目(13ZB0483)

Foundation Items：The Research Project for Electronics and Information of Education Steering Committee (2015-Y13); The Key Research Project of Sichuan Education Department 2014(14ZA0346， SCJG2014-741); The Research Project of Sichuan Iducation Department 2013(132B0483)

TP309

A

1673-825X(2016)06-0883-09