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

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

(湖南農業大學理學院，湖南 長沙 410128)

?

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

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

(湖南農業大學理學院，湖南 長沙 410128)

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

離散對數問題；叛逆者追蹤；完全撤銷性；完全可恢復性

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

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

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

1　方案介紹

設p是一個大素數，q也是一個素數且滿足q|p-1,q>n, 其中n為用戶數目，g是Zq上的一個生成元.這樣在p中計算以g為底的離散對數被認為是困難問題，其中p予以公開.

基于離散對數問題的叛逆者追蹤方案利用多項式與過濾函數來構建.注冊用戶必須通過匿名驗證以后才能得到私鑰.當發現叛逆者或需要恢復已撤銷用戶時，它能夠在不更新合法用戶私鑰的前提下，實現安全撤銷多個叛逆者或者完全恢復已撤銷用戶.

1.1系統初始化

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

1.2用戶注冊

當一個新用戶ui申請注冊時，DS隨機選擇一個沒有被使用的份額(i,f(i))傳送給用戶ui作為他擁有的份額，并記錄text=i‖f(i)‖ui，同時更新已注冊用戶集.用戶ui保存擁有份額(i,f(i)).

1.3用戶匿名驗證

當注冊用戶ui(擁有份額(i,f(i)))欲從DS處購買信息產品時,任選Ai∈RZq{0} 并執行以下步驟進行匿名驗證[10]:

Step1 用戶ui計算gAi,gAif(i)，將訂購單gAi‖gAif(i)發送給DS.

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

(1)

并驗證它們是否相等， 這是因為

((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)

若所有提取的部分通過相等的驗證，則執行下一節的操作.

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

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

(4)

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

Step7 DS計算gAif(0)=gAia0并將它與用戶發來的gAif(0)比較，若相等則通過驗證，DS更新text=i‖f(i)‖ui‖ki，若不相等則訂購終止.

1.4密鑰分發

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

(5)

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

1.5加密算法

(6)

然后計算

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

(7)

發送廣播消息(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)按照解密過程計算:

(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根據輸出的M'，計算M'×M-1=M(gAα)f(i)×M-1=(gAα)f(i)，對照保存的記錄text，找到與之相對應的{i‖f(i)‖ui‖ki}，則可確定用戶ui是叛逆者，此時該用戶是不可否認的.

1.8撤銷算法

(13)

然后計算

(14)

1.9恢復算法

2　性能分析

2.1用戶匿名安全與不可否認性

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

2.2完全抗共謀性

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

2.3完全撤銷性與完全恢復性

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

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

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

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

…

(15)

2.5黑盒追蹤性

由追蹤算法可知，當收繳到一個盜版解碼器，不用打開它，只需通過一次輸入輸出即可確定出該盜版解碼器所對應的叛逆者，即它具有黑盒追蹤性.

3　總結

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

[1]張學軍,周利華,王育民.一種抗共謀的非對稱公鑰叛逆者追蹤方案[J].計算機科學,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].通信學報,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]王曉明,姚國祥,廖志委.一個叛逆者追蹤方案分析和改進[J].計算機研究與發展,2013,(10)：2092-2099.

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

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

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

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

(責任編校：晴川)

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

湖南農業大學大學生創新性實驗計劃項目(批準號：XCX1572).

韓露露(1995— )，女，湖南長沙人，湖南農業大學理學院學生.研究方向：統計學.

TP393

A

1008-4681(2016)05-0062-04