韓露露，何少芳，賀雅楠，李　春，伍晨迪

(湖南農(nóng)業(yè)大學(xué)理學(xué)院，湖南 長(zhǎng)沙 410128)

?

一種匿名的公鑰叛逆者追蹤方案

韓露露，何少芳*，賀雅楠，李春，伍晨迪

(湖南農(nóng)業(yè)大學(xué)理學(xué)院，湖南 長(zhǎng)沙 410128)

針對(duì)離散對(duì)數(shù)困難問(wèn)題，提出一種匿名的公鑰叛逆者追蹤方案.該方案通過(guò)多項(xiàng)式與過(guò)濾函數(shù)來(lái)構(gòu)建，能夠在不更新其他合法用戶私鑰的前提下，實(shí)現(xiàn)完全撤銷多個(gè)叛逆者或者完全恢復(fù)已撤銷用戶.當(dāng)繳獲盜版解碼器時(shí)，只需通過(guò)一次輸入輸出即可確定叛逆者.由性能分析可知，該方案不僅具有用戶的匿名安全性、不可否認(rèn)性、完全撤銷與恢復(fù)以及黑盒追蹤的特點(diǎn)，還滿足完全抗共謀性與抗線性組合攻擊.

離散對(duì)數(shù)問(wèn)題；叛逆者追蹤；完全撤銷性；完全可恢復(fù)性

加密數(shù)據(jù)(如付費(fèi)電視系統(tǒng)、網(wǎng)上金融信息廣播、在線數(shù)據(jù)庫(kù)等)的安全分發(fā)是現(xiàn)代信息社會(huì)的一個(gè)重要問(wèn)題.數(shù)據(jù)提供商DS通過(guò)廣播信道向授權(quán)用戶提供加密信息.授權(quán)用戶先用私鑰將加密數(shù)據(jù)包頭中的會(huì)話密鑰恢復(fù),再利用得到的會(huì)議密鑰解密數(shù)據(jù).如果惡意的授權(quán)用戶將自己的密鑰泄露給別的非法用戶使用,或者某些授權(quán)用戶合謀制造出密鑰給非法用戶使用,那么這些惡意的授權(quán)用戶就稱為叛逆者,而非法用戶稱為盜版者,通過(guò)盜版者的解碼器分析出叛逆者的工作稱為叛逆者追蹤.在這種應(yīng)用場(chǎng)合,叛逆者追蹤作為保障數(shù)據(jù)安全分發(fā)并保護(hù)數(shù)據(jù)提供商合法權(quán)益的手段,成為當(dāng)前研究的熱點(diǎn)[1].

叛逆者追蹤的概念首先由Chor等人[2]提出，之后許多叛逆者追蹤方案相繼被提出來(lái).從密碼學(xué)角度來(lái)看，叛逆者追蹤方案在加解密過(guò)程中可以運(yùn)用多種加密算法.Boneh和Franklin[3]首次提出公鑰叛逆者追蹤方案,它解決了對(duì)稱方案中存在的問(wèn)題，但其實(shí)現(xiàn)效率不高.此后，設(shè)計(jì)以公鑰為基礎(chǔ)的叛逆者追蹤方案成為研究的主要方向，各種以不同公鑰加密體制為基礎(chǔ)的叛逆者追蹤方案被提了出來(lái).文獻(xiàn)[4]提出門限值為k的抗共謀方案，而文獻(xiàn)[5]、[6]、[7]提出了具有完全抗共謀的叛逆者追蹤方案，也就是說(shuō)它不存在門限值的限制，但不能實(shí)現(xiàn)撤銷性.文獻(xiàn)[8]對(duì)文獻(xiàn)[9]進(jìn)行改進(jìn)，提出了具有完全抗共謀性、完全撤銷性和完全可恢復(fù)性的叛逆者追蹤方案.文獻(xiàn)[10]、[11]還分別提出了基于隨機(jī)序列的公鑰叛逆者追蹤方案和基于EIGamal加密算法的匿名叛逆者追蹤方案，它們都具有較好的安全性.

現(xiàn)有的叛逆者追蹤方案重點(diǎn)研究抗共謀、撤銷性、追蹤性、安全性等多個(gè)方面，但是缺少對(duì)用戶隱私性保護(hù)的考慮.保護(hù)用戶隱私和叛逆者追蹤不矛盾.事實(shí)上，平衡數(shù)字內(nèi)容價(jià)值鏈中普通合法用戶隱私性和盜版者的可追蹤性是數(shù)字版權(quán)保護(hù)機(jī)制中應(yīng)該考慮的另一個(gè)重要方面.受文獻(xiàn)[8，9，12]的啟發(fā)，本文基于離散對(duì)數(shù)問(wèn)題以及利用類EIGamal加密體制提出一種匿名的公鑰叛逆者追蹤方案.該方案在沒(méi)有可信第三方的參與下實(shí)現(xiàn)用戶的身份驗(yàn)證與追蹤，不僅具有用戶的匿名安全性、不可否認(rèn)性、防誣陷、可完全撤銷與恢復(fù)、黑盒追蹤等特點(diǎn)，還滿足完全抗共謀性與抗線性組合攻擊.

1　方案介紹

設(shè)p是一個(gè)大素?cái)?shù)，q也是一個(gè)素?cái)?shù)且滿足q|p-1,q>n, 其中n為用戶數(shù)目，g是Zq上的一個(gè)生成元.這樣在p中計(jì)算以g為底的離散對(duì)數(shù)被認(rèn)為是困難問(wèn)題，其中p予以公開(kāi).

基于離散對(duì)數(shù)問(wèn)題的叛逆者追蹤方案利用多項(xiàng)式與過(guò)濾函數(shù)來(lái)構(gòu)建.注冊(cè)用戶必須通過(guò)匿名驗(yàn)證以后才能得到私鑰.當(dāng)發(fā)現(xiàn)叛逆者或需要恢復(fù)已撤銷用戶時(shí)，它能夠在不更新合法用戶私鑰的前提下，實(shí)現(xiàn)安全撤銷多個(gè)叛逆者或者完全恢復(fù)已撤銷用戶.

1.1系統(tǒng)初始化

數(shù)據(jù)提供商在Zq上隨機(jī)選擇一個(gè)k次多項(xiàng)式f(x)=a0+a1x+…+akxk,k>N,N為最大用戶數(shù).稱f(x)上對(duì)應(yīng)的一個(gè)點(diǎn)(i,f(i)),i∈Zq{0}為一個(gè)份額.設(shè)Φ={(i‖f(i))|i∈Zq{0}}為已注冊(cè)用戶集合，且Φ滿足對(duì)任意i≠j有f(i)≠f(j).除了另有說(shuō)明，本文的所有算術(shù)運(yùn)算都在Zq上.

1.2用戶注冊(cè)

當(dāng)一個(gè)新用戶ui申請(qǐng)注冊(cè)時(shí)，DS隨機(jī)選擇一個(gè)沒(méi)有被使用的份額(i,f(i))傳送給用戶ui作為他擁有的份額，并記錄text=i‖f(i)‖ui，同時(shí)更新已注冊(cè)用戶集.用戶ui保存擁有份額(i,f(i)).

1.3用戶匿名驗(yàn)證

當(dāng)注冊(cè)用戶ui(擁有份額(i,f(i)))欲從DS處購(gòu)買信息產(chǎn)品時(shí),任選Ai∈RZq{0} 并執(zhí)行以下步驟進(jìn)行匿名驗(yàn)證[10]:

Step1 用戶ui計(jì)算gAi,gAif(i)，將訂購(gòu)單gAi‖gAif(i)發(fā)送給DS.

rj′*rj′-1= 1mod(q-1),rj*rj-1= 1mod(q-1)

(1)

并驗(yàn)證它們是否相等， 這是因?yàn)?/p>

((T1′)f2(i))r1′-1= (((gAi f(i))r1′)f2(i))r1′-1= gAi f3(i)(K(q-1) + 1)= gAi f3(i)K(q-1)*gAi f3(i)= gAi f3(i)

(2)

同理有：

(3)

若所有提取的部分通過(guò)相等的驗(yàn)證，則執(zhí)行下一節(jié)的操作.

Step5 DS任選Ω={x1,x2,…,xk}，滿足(xj,f(xj))?Φ,j=1,2,…,k，利用接收到的gAi‖gAif(i)計(jì)算gAif(xj),j=1,2,…,k，發(fā)送x1‖gAif(x1)‖x2‖gAif(x2)‖…‖xk‖gAif(xk)‖gAif(i)給用戶ui.

Step6 用戶ui利用收到的k組數(shù)據(jù)(xj,gAif(xj)),j=1,2,…,k以及(i,gAif(i))，由Lagrange插值法得到

(4)

用戶保存ki=gAif(0)并將其發(fā)送給DS.

Step7 DS計(jì)算gAif(0)=gAia0并將它與用戶發(fā)來(lái)的gAif(0)比較，若相等則通過(guò)驗(yàn)證，DS更新text=i‖f(i)‖ui‖ki，若不相等則訂購(gòu)終止.

1.4密鑰分發(fā)

y0=(gA)a0,y1=(gA)a1,…,yk=(gA)ak

(5)

公開(kāi)pub={p,g,y0,…,yk}作為公鑰，用戶ui的私鑰為(i,f(i),ki).

1.5加密算法

(6)

然后計(jì)算

C2=(M(y0)α,(y1)α,…,(yk)α)

(7)

發(fā)送廣播消息(C1(x),C2).

1.6解密算法

(8)

(M×(y0)α×(y1)αi×…×(yk)αik)/(gAα)f(i)

=(M×(gAa0)α×(gAa1)αi×…×(gAak)αik)/(gAα)f(i)

=(M×(gAα)f(i))/(gAα)f(i)=M

(9)

1.7追蹤算法

(10)

向解碼器輸入(C1(x),C2)，則解碼器利用其解密密鑰(i,f(i),ki)按照解密過(guò)程計(jì)算:

(11)

M'=(M×(y0)2α×(y1)2αi×…×(yk)2αik)/(gAα)f(i)

=(M×(gAa0)2α×(gAa1)2αi×…×(gAak)2αik)/(gAα)f(i)

=(M×(gA2α)f(i))/(gAα)f(i)=M(gAα)f(i)

(12)

DS根據(jù)輸出的M'，計(jì)算M'×M-1=M(gAα)f(i)×M-1=(gAα)f(i)，對(duì)照保存的記錄text，找到與之相對(duì)應(yīng)的{i‖f(i)‖ui‖ki}，則可確定用戶ui是叛逆者，此時(shí)該用戶是不可否認(rèn)的.

1.8撤銷算法

(13)

然后計(jì)算

(14)

1.9恢復(fù)算法

2　性能分析

2.1用戶匿名安全與不可否認(rèn)性

DS要從訂購(gòu)單gAi‖gAif(i)中獲取代表用戶身份的的信息f(i)，其困難性相當(dāng)于求解離散對(duì)數(shù)困難問(wèn)題，因此用戶的匿名安全是有保障的.正因?yàn)镈S無(wú)法確定已訂購(gòu)的用戶身份f(i)，也就無(wú)法陷害誠(chéng)實(shí)用戶，因此該方案又具有防誣陷性.此外，由于用戶在訂購(gòu)信息產(chǎn)品時(shí)，需要隨機(jī)選取Ai∈RZqackslash 0 ，因此DS要從已經(jīng)保存的訂購(gòu)單中識(shí)別出屬于同一用戶的不同訂購(gòu)單，其困難性同樣相當(dāng)于求解離散對(duì)數(shù)問(wèn)題.另一方面,由于Ai是用戶ui私自選擇的，且ki=gAif(0)為其私鑰,一旦用戶被判定為叛逆者則不可否認(rèn).

2.2完全抗共謀性

根據(jù)Lagrange插值公式，一個(gè)t階多項(xiàng)式f(x)能利用t+1或大于t個(gè)的(xi,f(xi))重構(gòu).但在本文方案中，由于k次多項(xiàng)式f(x)=a0+a1x+…+akxk,k>N,N為最大用戶數(shù)，即使所有用戶合謀也不能重構(gòu)f(x)，因此它具有完全抗共謀性.

2.3完全撤銷性與完全恢復(fù)性

由加密算法與解密算法可知，若某些用戶已通過(guò)撤銷算法被撤銷，則其ki不再包含于廣播消息的C1(x)中，被撤銷用戶無(wú)法利用其密鑰正確恢復(fù)明文，而其他用戶利用原有私鑰即可恢復(fù)明文.此外，由撤銷算法可知，它不存在撤銷門限，可一次完成對(duì)所有叛逆者的撤銷，具有完全撤銷性.另一方面，若要恢復(fù)被撤銷用戶，由恢復(fù)算法可知，只須將他們的kj加入C1(x)即可，其它用戶不需更新私鑰，因此該方案也具有完全恢復(fù)性.

2.4抗線性組合(凸組合)攻擊

設(shè)f(i1),f(i2),…,f(ik)是k個(gè)用戶的私鑰，w=[u,w0,w1,…,wk]是向量v1,v2…,vk的任一線性組合，其中

v1=[f(i1),1,i1,i2,…,ik]

…

(15)

2.5黑盒追蹤性

由追蹤算法可知，當(dāng)收繳到一個(gè)盜版解碼器，不用打開(kāi)它，只需通過(guò)一次輸入輸出即可確定出該盜版解碼器所對(duì)應(yīng)的叛逆者，即它具有黑盒追蹤性.

3　總結(jié)

本文基于離散對(duì)數(shù)問(wèn)題，提出一種匿名的公鑰叛逆者追蹤方案.該方案在沒(méi)有可信第三方的參與下，實(shí)現(xiàn)了用戶的身份驗(yàn)證與追蹤.它利用多項(xiàng)式與過(guò)濾函數(shù)構(gòu)建叛逆者追蹤方案，當(dāng)發(fā)現(xiàn)叛逆者或需要恢復(fù)已撤銷用戶時(shí)，它能夠在不更新其他用戶私鑰的前提下，實(shí)現(xiàn)安全撤銷多個(gè)叛逆者或者完全恢復(fù)已撤銷用戶.當(dāng)繳獲盜版解碼器時(shí)，不用打開(kāi)它，只要通過(guò)一次輸入輸出即可確定叛逆者.通過(guò)性能分析可知，該方案不僅具有用戶匿名安全性與不可否認(rèn)性，還具有完全可撤銷與恢復(fù)性、黑盒追蹤性，且還滿足完全抗共謀性與抗線性組合攻擊.

[1]張學(xué)軍,周利華,王育民.一種抗共謀的非對(duì)稱公鑰叛逆者追蹤方案[J].計(jì)算機(jī)科學(xué),2006,(8):118-120.

[2]Chor B, Fiat A, Naor M. Tracing traitors[J]. IEEE Transactions on Information Theory, 1994, (6):257-270.

[3]Boneh D, Franklin F. An efficient public key traitor tracing scheme[A]. Proc. of CRYPTO’99, LNCS[C]. Springer-Verlag, 1999.

[4]Yuji W, Goichiro H, Hideki I. Efficient public key traitor tracing scheme [A]. Proc of CT-RSA 2001 [C].Berlin: Springer, 2001.

[5]Boneh D, Sahai A, Waters B. Ful collusion resistant traitor tracing with short ciphertexts and private keys[A].Proc of the 13thACM Conf on Computer and Communications Security[C]. New York: ACM, 2006.

[6]王青龍,楊波,韓臻,等.免共謀公鑰叛逆者追蹤方案[J].通信學(xué)報(bào),2006,(12):6-9.

[7]Ya-Li Qi. An improved traitors tracing scheme against convex combination attack[A]. WISM 2011, CCIS 238[C]. Springer-Verlag, 2011.

[8]王曉明,姚國(guó)祥,廖志委.一個(gè)叛逆者追蹤方案分析和改進(jìn)[J].計(jì)算機(jī)研究與發(fā)展,2013,(10)：2092-2099.

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

[10]何少芳.一種基于隨機(jī)序列的公鑰叛逆者追蹤方案[J]. 電子科技, 2016, (4):180-182.

[11]何少芳. 基于EIGamal加密算法的匿名叛逆者追蹤方案[J]. 電子科技, 2016,(6):44-46.

[12]王青龍,楊波. 一種無(wú)第三方參與的匿名指紋方案[J].電子學(xué)報(bào), 2005,(11):2063-2065.

(責(zé)任編校：晴川)

An Anonymous Public Key Traitor Tracing Scheme

HAN Lulu, HE Shaofang*, HE Yanan, LI Chun, WU Chendi

(College of Science, Hunan Agricultural University, Changsha Hunan 410128, China)

Based on the discrete log representation problem, an anonymous public key traitor tracing scheme is presented in this paper. This scheme employs the polynomial function and the filter function as the basic means of constructing the traitor tracing procedures, and it can safely revoke or recover the private keys of traitors without updating the private keys of other receivers. When a pirate decoder is confiscated, it only requires single input and output to decide the traitor. The analysis of performance shows that the proposed scheme has many advantages, such as anonymous safety of users, non-repudiation, full revocability, black-box traceability and full recoverability. Moreover, the scheme is able to achieve full collusion resistance and anti-linear-attack.

discrete log representation problem; traitor tracing; full revocability; full recoverability.

2016-09-11

湖南農(nóng)業(yè)大學(xué)大學(xué)生創(chuàng)新性實(shí)驗(yàn)計(jì)劃項(xiàng)目(批準(zhǔn)號(hào)：XCX1572).

韓露露(1995— )，女，湖南長(zhǎng)沙人，湖南農(nóng)業(yè)大學(xué)理學(xué)院學(xué)生.研究方向：統(tǒng)計(jì)學(xué).

TP393

A

1008-4681(2016)05-0062-04