一種基于隨機序列的公鑰叛逆者追蹤方案

何少芳

(湖南農(nóng)業(yè)大學 理學院,湖南 長沙　410128)

?

一種基于隨機序列的公鑰叛逆者追蹤方案

何少芳

(湖南農(nóng)業(yè)大學 理學院,湖南 長沙410128)

摘要基于離散對數(shù)困難問題,利用隨機序列提出一種公鑰叛逆者追蹤方案。該方案采用多項式與過濾函數(shù)來構(gòu)建,當繳獲盜版解碼器時,只需通過一次輸入輸出即可確定叛逆者。若需要撤銷或恢復多個叛逆者時,其能在不更新其他合法用戶私鑰的前提下,實現(xiàn)完全撤銷多個叛逆者或完全恢復已撤銷用戶。性能分析證明,該方案不僅存儲、計算和通信開銷低,還具有完全抗共謀性、完全撤銷性與完全恢復性以及黑盒追蹤的特點。

關(guān)鍵詞離散對數(shù)問題;叛逆者追蹤;完全撤銷性;完全可恢復性;黑盒追蹤

為了阻止未授權(quán)用戶得到網(wǎng)上提供的服務,數(shù)據(jù)提供商(DS)需要對將要發(fā)布的廣播信息進行加密處理,即通過廣播信道向授權(quán)用戶提供加密信息,并給每個授權(quán)用戶分發(fā)個人解密密鑰。若惡意的授權(quán)用戶將自身的密鑰泄露給別的非法用戶使用,或某些授權(quán)用戶合謀制造出密鑰給非法用戶使用,則這些惡意的授權(quán)用戶就稱為叛逆者,而非法用戶稱為盜版者,通過盜版者的解碼器分析出叛逆者的工作稱為叛逆者追蹤[1]。為了解決叛逆者引起的問題,Chor等人[2]在1994年提出了叛逆者追蹤的概念,其的基本思想為每個授權(quán)用戶分發(fā)不同的解密密鑰,若繳獲盜版解碼器,則通過輸入輸出之間的關(guān)系來確定解碼中包含的解密密鑰,從而確定叛逆者。這之后眾多叛逆者追蹤方案相繼被提出。從密碼學角度而言,叛逆者追蹤方案在加解密過程中可運用多種加密算法。Boneh和Franklin首次提出公鑰叛逆者追蹤方案[3],其解決了對稱方案中存在的問題,但其實現(xiàn)效率較低。此后,設計以公鑰為基礎(chǔ)的叛逆者追蹤方案成為研究的主要方向,各種以不同公鑰加密體制為基礎(chǔ)的叛逆者追蹤方案被提出。文獻[4]提出門限值為k的抗共謀方案,而文獻[5～6]提出了具有完全搞共謀的叛逆者追蹤方案,即其不存在門限值的限制,但不能實現(xiàn)撤銷性。文獻[7]對文獻[8]進行改進,提出了具有完全抗共謀性、完全撤銷性和完全可恢復性的叛逆者追蹤方案。具有短私鑰的基于身份的叛逆者追蹤(IBTT)結(jié)構(gòu)首先由Abdalla 等人提出[9],其提供了基于身份加密的追蹤能力。Boneh 等人則提出一種公鑰叛逆者追蹤方案,其能擴展成具有短密文的IBTT[10]。由于長私鑰會增加安全存儲的開銷,而長密文需要更大的通信開銷,Fuchun Guo等人提出一種同時具有短私鑰和短密文的IBTT[11]。此外,文獻[12]提出了基于消息的叛逆者追蹤方案,其構(gòu)建了一種具有最佳密文速率的消息可跟蹤加密方案。

叛逆者追蹤方案是打擊和威懾數(shù)字產(chǎn)品盜版的有效方法,而其的研究重點是抗共謀性、撤銷性、恢復性和追蹤性等多個方面?；陔S機序列并利用離散對數(shù)問題,本文提出一種公鑰叛逆者追蹤方案。該方案利用隨機序列構(gòu)建多個不同的多項式,并利用過濾函數(shù)實現(xiàn)多個用戶的完全撤銷與恢復,其不僅具有較低的存儲、計算和通信開銷,還滿足完全抗共謀性、可完全撤銷與恢復性以及黑盒追蹤等。

1方案描述

基于隨機序列、離散對數(shù)問題的叛逆者追蹤方案利用多項式與過濾函數(shù)來構(gòu)建。隨機序列由用戶注冊時選擇,基于其的DS可衍生出多個多項式,并由此計算生成注冊用戶的解密密鑰。當發(fā)現(xiàn)叛逆者需要撤銷這些用戶或者需要恢復已撤銷用戶時,該方案能在不更新合法用戶私鑰的前提下,實現(xiàn)安全撤銷多個叛逆者或者完全恢復已撤銷用戶。

1.1系統(tǒng)初始化

數(shù)據(jù)提供商在Zq上隨機選擇一個k次多項式

f(x)=a0+a1x+…+akxk,k>N

(1)

其中,N為最大用戶數(shù)。除另有說明,本文的所有算術(shù)運算都在Zq上。

1.2用戶注冊

(2)

1.3密鑰分發(fā)

1.4加密算法

1.5解密算法

用戶ui接收到廣播密文后,向解碼器輸入(C1(x),C2),解碼器利用其解密密鑰ki計算

(3)

C2/C1(ki)=(M(gA)α)/(gAα)=M

(4)

1.6追蹤算法

(5)

(6)

(7)

1.7撤銷算法

(8)

1.8恢復算法

2性能分析

2.1正確性

引理1若DS正確執(zhí)行加密算法,給定廣播密文(C1(x),C2),則所有合法用戶均能成功恢復明文信息。

引理2若輸入正確的廣播信息(C1(x),C2),結(jié)合解碼器中的解密密鑰ki,則追蹤算法可追蹤任何叛逆者。

2.2存儲、計算和通信開銷

就存儲開銷而言,每個用戶只需存儲一個常量大小的個人解密密鑰ki,存儲開銷較小。在加密算法中,方案的主要計算量為乘法和模指數(shù)計算,計算開銷較低。而在通信開銷方面,方案只需廣播密文(C1(x),C2),通信開銷也較少。因此,提出的方案在存儲、計算和通信方面的開銷均較低。

2.3完全抗共謀性

根據(jù)Lagrange插值公式,一個t階多項式f(x)能利用t+1或>t個的(xi,f(xi))重構(gòu)。但在本方案中,由于k次多項式

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

(9)

k>N,N為最大用戶數(shù),且DS利用用戶選擇的隨機序列重新構(gòu)建多項式fi(x),計算ki=gfi(i)并將其作為用戶ui的個人解密密鑰,用戶ui要得到fi(i),其困難性相當于求解離散對數(shù)問題。因此,即使所有用戶合謀也不能重構(gòu)f(x),該方案具有完全抗共謀性。

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

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

2.5黑盒追蹤性

由追蹤算法可知,當收繳到一個盜版解碼器時,無需將其打開,只需通過一次輸入輸出即可確定出該盜版解碼器所對應的叛逆者,因此其具有黑盒追蹤性。

2.6用戶密鑰的耐用性

用戶密鑰具有耐用性指的是當恢復用戶或撤銷用戶時,無需改變原有用戶的個人解密密鑰。在本文方案中,公鑰也無須改變,只需修改廣播消息中的過濾函數(shù)即可。

假設用戶集合Δ={ui1,ui2,…,uim},1≤m≤n已被撤銷,其中的用戶可能是叛逆者或是自愿離開系統(tǒng),其持有的私鑰對應為{ki1,ki2,…,kim},則DS只需進行如下操作:

(10)

計算

(11)

3結(jié)束語

本文基于隨機序列與離散對數(shù)問題,提出一種公鑰叛逆者追蹤方案。該方案利用用戶選擇的隨機序列構(gòu)建新多項式,并利用該多項式計算生成用戶個人解密密鑰;在廣播信息中,利用過濾函數(shù)實現(xiàn)叛逆者追蹤、撤銷和恢復用戶。當需要撤銷多個叛逆者或恢復已撤銷的多個用戶時,其能在不更新其他用戶私鑰的前提下,實現(xiàn)一次性安全撤銷多個叛逆者或完全恢復已撤銷用戶。若繳獲一個盜版解碼器,無需將其打開,只需通過一次輸入輸出即可確定叛逆者。由性能分析可知,該方案不僅具有較低的存儲、計算和通信開銷,還具有完全撤銷性、完全恢復性、黑盒追蹤性以及完全抗共謀性。

參考文獻

[1]Duong Hieu Phan,Viet Cuong Trinh.Identity-based trace and revoke schemes[C].Berlin Heidelberg:ProvSec 2011,LNCS 6980,2011.

[2]Chor B,Fiat A,Naor M.Tracing traitors[C].Germany:Advances in Cryptology-CRYPT’94,LNCS,Springer-Verlag,1994.

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

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

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

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

[7]王曉明,姚國祥,廖志委.一個叛逆者追蹤方案分析和改進[J].計算機研究與發(fā)展,2013,50(10):2092-2099.

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

[9]Abdalla M,Dent A W,Malone-Lee J,et al.Identity-based traitor tracing[C].Heidelberg:PKC 2007,LNCS,Springer,2007.

[10]Boneh D,Naor M.Traitor tracing with constant size ciphertext[C].Sydney:ACM CCS 2008,2008.

[11]Guo Fuchun,Mu Yi,Willy Susilo.Identity-based traitor tracing with short private key and short ciphertext[C].Berlin Heidelberg:ESORICS 2012,LNCS 7459,Springer-Verlag,2012.

[12]Duong Hieu Phan,David Pointcheval,Mario Stefler.Message-based traitor tracing with optimal ciphertext rate[C].Berlin Heidelberg:LATINCRYPT 2012,LNCS 7533,Springer-Verlag,2012.

A Public Key Traitor Tracing Scheme Based on Random Sequence

HE Shaofang

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

AbstractBased on the discrete log representation problem and employing random sequence,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.When a pirate decoder is confiscated,single input and output suffices to decide the traitor.If it is necessary to revoke or recover traitors,the scheme can safely revoke or recover the private keys of traitors without updating the private keys of other receivers.The performance analysis shows that the proposed scheme not only has low cost of secure storage,calculation and communication,but also is capable of full collusion resistance,full revocability,full recoverability and black-box traceability.

Keywordsdiscrete log representation problem;traitor tracing;full revocability;full recoverability;black-box traceability

中圖分類號TN918.4;TP393

文獻標識碼A

文章編號1007-7820(2016)04-180-04

doi:10.16180/j.cnki.issn1007-7820.2016.04.048

作者簡介:何少芳(1980—),女,碩士,講師。研究方向:信息安全。

基金項目:湖南省教育廳基金資助項目(13C394);湖南農(nóng)業(yè)大學“大學生創(chuàng)新性實驗計劃基金資助項目”(XCX1572)

收稿日期:2015- 09- 07