群簽名與廣播加密的對偶性及應(yīng)用

程小剛， 郭韌， 陳永紅

(1. 華僑大學(xué) 計算機科學(xué)與技術(shù)學(xué)院， 福建 廈門 361021；2. 華僑大學(xué) 工商管理學(xué)院， 福建 泉州 362021)

群簽名與廣播加密的對偶性及應(yīng)用

程小剛1， 郭韌2， 陳永紅1

(1. 華僑大學(xué) 計算機科學(xué)與技術(shù)學(xué)院， 福建 廈門 361021；2. 華僑大學(xué) 工商管理學(xué)院， 福建 泉州 362021)

提出群簽名(GS)與廣播加密(BE)是一對關(guān)系密切的對偶密碼系統(tǒng)，類似公開加密與普通簽名的對偶關(guān)系，即基于GS方案可以構(gòu)建BE方案.而基于BE方案也可以構(gòu)建GS方案.文中給出實現(xiàn)這種對偶關(guān)系的具體構(gòu)建方法與步驟，即基于NP(non-deterministic polynomial)證據(jù)加密(WE)可把一個可撤銷群簽名方案轉(zhuǎn)換為一個可撤銷廣播加密方案，而基于非交互式零知識(NIZK)證明可把一個撤銷廣播加密方案轉(zhuǎn)換為一個可撤銷群簽名方案.最后，指出基于廣播加密的高效可撤銷群簽名方案可以納入文中所提出的框架中. 關(guān)鍵詞： 群簽名； 廣播加密； 對偶性； NP證據(jù)加密； 成員撤銷

群簽名(group signature，GS)是1991年由Chaum 和Heyst 在Crypto 密碼學(xué)會議上提出[1].由于結(jié)合了匿名與可追蹤的良好特性，群簽名迅速成為一種具有中心地位的密碼系統(tǒng)，到今天群簽名方案的構(gòu)建在安全性、效率等方面有了很大的提高[2]，并在電子投票[3]、電子貨幣[4]、可信計算[5]、網(wǎng)絡(luò)追蹤[6]與隱藏機構(gòu)內(nèi)部結(jié)構(gòu)等方面有廣泛的應(yīng)用[2].廣播加密(broadcast encryption，BE)[7]典型的應(yīng)用是付費電視的應(yīng)用中，電視臺對視頻節(jié)目進行加密后廣播出去，任何人可收到加密后的視頻，但只有付過費的合法用戶(擁有相關(guān)密鑰)才能解密而正常收看電視節(jié)目.GS與BE都是群組密碼系統(tǒng)，即是面向多人、多參與方，而不象普通的簽名或加密，通常是一個簽名方(發(fā)送方)，一個驗證方(接收方).對于此類密碼系統(tǒng)，研究的目的是發(fā)現(xiàn)他們之間非平凡的聯(lián)系(正如普通的簽名與公開加密之間的對偶關(guān)系)，從而彼此相互借鑒、利用各自領(lǐng)域中的技術(shù)互相促進，構(gòu)建出更好、更高效、更靈活、更通用的群組密碼系統(tǒng).Kiayias等[8]指出GS與叛逆者追蹤(traitor tracing，TT)之間有密切的對偶關(guān)系[9]，而相對GS與TT，GS與BE之間相似度更大,關(guān)系更密切.如GS與BE同時都有成員撤消問題[10-11].本文提出GS與BE是一對關(guān)系密切的對偶密碼系統(tǒng)，并給出了具體的相互構(gòu)建方法與步驟.

1 初步知識

定義1 群簽名一般由下面6個隨機多項式時間算法組成.

1) 設(shè)置(Setup).給定一安全參數(shù)K，群管理員(GM)生成一個群公鑰(GPK)可用于群簽名的驗證，和一群私鑰(GSK)可用于生成成員證書及簽名打開；安全性更好的是，負(fù)責(zé)納入成員的GM及負(fù)責(zé)打開簽名的GM角色是分開的(通過持有不同的密鑰).

2) 加入(Join).對于動態(tài)的群簽名，這是用戶和GM之間執(zhí)行的一個交互協(xié)議，完成后用戶加入群并獲得成員證書及一個私鑰，可用于群簽名的生成，GM獲得相關(guān)的追蹤信息，可用來打開此用戶的群簽名；而靜態(tài)的群簽名由GM直接生成成員的證書并秘密傳給成員，就沒有此交互過程.缺點是GM可冒充成員進行簽名.

3) 簽名(Sign).群成員可利用自己的成員證書和私鑰生成任一消息的群簽名.

4) 驗證(Verify).任何人獲得GPK和一個消息/簽名對，可驗證此群簽名是否合法，但對合法的群簽名他不能找出實際的簽名者，而且同一成員作的群簽名之間也是不可鏈接的.

5) 打開與證明(Open and Prove).對于合法的群簽名，GM能打開并找出實際的簽名者；最好GM也能給出證據(jù)，說明一群簽名的確是某成員簽的，同時,不會破壞此成員未來的簽名能力.

6) 撤銷(Revoke).GM可撤銷某成員的簽名權(quán)利，之后此用戶就再也不能生成合法的群簽名了.

群簽名的安全模型主要有如下兩個性質(zhì).

1) 匿名性.給定一個合法的群簽名，只有GM才能識別出真正的簽名者，其他任何人都不能打開簽名找出簽名者.

2) 可追蹤性.一群合謀者將他們的私鑰放在一起也不能生成一個合法的群簽名，使其打開至其他群成員.前述是成立的，即使合謀者知道GM打開簽名的私鑰.

定義2 廣播加密由如下7個多項式算法構(gòu)成.

1) 設(shè)置(Setup).生成系統(tǒng)的主公/私鑰對MPK/MSK，并初始將撤銷列表(revocation list，RL)設(shè)置為空.

2) 加入(Join).標(biāo)識為ID的用戶向系統(tǒng)申請加入，系統(tǒng)管理員審核后由(MSK，ID)生成用戶私鑰SKID并頒發(fā)給用戶.

3) 加密(ENC(MPK，m，RL)).用系統(tǒng)公鑰MPK及RL對消息m進行加密，得到密文CT.

4) 解密(DEC(CT，SKID)).任何合法的用戶(具有合法的私鑰SKID，并且其ID不在RL中)，可對密文CT進行解密得到消息m.

5) 撤銷(Revoke).系統(tǒng)管理員將欲撤消的用戶標(biāo)識ID放入RL中，標(biāo)識其以后不再能收到消息.

6) 重新加入(Re-Join).系統(tǒng)管理員將用戶ID從RL中刪除，此后該用戶就能正常接收廣播消息.

BE的IND_CPA(indistinguishable chosen plaintext attack)安全模型定義如下：

1) Challenger生成BE方案的MPK/MSK，并把MPK 發(fā)送給敵手ADV；

2) ADV能自適應(yīng)地向Challenger查詢?nèi)我粯?biāo)識為ID的用戶的私鑰，Challenger利用其掌握的MSK生成私鑰，發(fā)送給ADV，并將所有ADV查詢過的ID加入集合Q中；

3) ADV生成任意兩個長度相同,但內(nèi)容不同的消息m0，m1，并發(fā)給Challenger；

4) Challenger首先將集合Q中的所有用戶放入RL中去，再隨機選擇b=0或1，用MPK和RL對m,b進行加密,得到密文CT，將密文發(fā)給ADV；

5) ADV收到CT后，要猜測b=0還是1，BE是IND_CPA安全的，如果ADV的成功概率同1/2的差是可忽略的，即

|Pr[ADV(CT)→b′∶b′=b]-1/2|

2 對偶關(guān)系的構(gòu)建與步驟

2.1 基于GS及WE的 BE方案構(gòu)建

2.1.1 NP證據(jù)加密 該系統(tǒng)是Garg等[12]提出的一種新的沒有密鑰生成過程的加密系統(tǒng)，它以一個NP(non-deterministic polynomial)語言L的實例x做為公鑰,對消息m進行加密，如果x∈L且解密者有相關(guān)的NP證據(jù)w，則可以對密文解密,得到消息m；而如果x∈L，則加密是語義安全的.文獻[8]也給出了證據(jù)加密(witness encryption，WE)的多種應(yīng)用，如公鑰加密方案和IBE,ABE等.

文中給出WE的另一個應(yīng)用，即用于構(gòu)建可撤消的BE方案[10，13]，所構(gòu)建的可撤消BE方案具有簡單的成員重加入功能，很適合付費電視等的應(yīng)用，如欠費的用戶被停機，而當(dāng)用戶繳清欠費后又恢復(fù)其成員資格.

定義3 WE(NP證據(jù)加密).針對一NP語言L的WE方案有如下的多項式時間算法.

1) ENC(1λ，x，M).算法輸入為安全參數(shù)λ，一個字符串x和待加密的消息M，輸出為密文CT.

2) DEC(CT，w).算法輸入為一密文CT，一個字符串w，輸出為一個消息M或一特殊字符⊥.

這些算法滿足下面2個主要性質(zhì).

1) 正確性.如果x∈L且w是相應(yīng)的NP證據(jù)，那么,解密算法總能正確解密得到消息M，即

Pr[DEC(ENC(1λ，x，M)，w)=M]=1.

2) 公正性.如果x?L，那么對于任何的多項式時間敵手A來說，除了可忽略概率之外，對兩個不同消息加密的密文分布是相同的，即

|Pr[A(ENC(1λ，x，m0))=1]-Pr[A(ENC(1λ，x，m1))=1]|

2.1.2 BE方案構(gòu)建 方案構(gòu)建的思想是：成員加入所獲得的證書私鑰就是GM頒發(fā)的數(shù)字簽名，之后BE時用WE來加密，GM的簽名驗證公鑰是公開的，所用的NP關(guān)系是存在一個消息m及一個合法的簽名(相對GM簽名驗證公鑰)，并且此消息m不在RL中.

基于GS和WE的BE方案構(gòu)建如下：

BE.Setup，就是GS.Setup；

BE.Join，就是GS.Join，完成后成員獲得成員私鑰(此私鑰在GS中是用來生成群簽名，而在BE中是用來進行廣播消息的解密)；

BE.Encrypt,用如下的NP語言利用WE對消息m進行加密,即

NP={GS.GPK|?Usk是合法的∧Usk未被撤消}

BE.Decrypt，顯然擁有合法Usk的成員能利用其NP證據(jù)利用WE的Decrypt算法對廣播消息進行解密；

BE.Revo，就是GS.Revo，撤銷后成員的Usk就不再是合法的NP證據(jù)，所以也就無法對之后的廣播消息進行解密.

2.2 基于BE的GS方案構(gòu)建

基于BE的GS方案構(gòu)建的思想是：GS中成員的私鑰就是BE中成員的解密私鑰，簽名時利用NIZK證明系統(tǒng)證明自己是合法的成員(即擁有合法的解密私鑰).在此應(yīng)指出Libert等[14-15]的高效可撤銷GS方案構(gòu)建可看作是此思想的具體實現(xiàn).

2.2.1 NNL廣播撤銷[10]NNL廣播方案中把所有用戶對應(yīng)到樹的葉子節(jié)點，每個用戶對應(yīng)一個葉子節(jié)點，進行撤銷時，把合法的廣播接收成員劃分成若干個子集.每個子集SKi，Ui的含義，如圖1所示.

圖1 NNL廣播撤銷示意圖Fig.1 NNL broadcast revocation schematic

從圖1可以看出：Ui是Ki的子孫節(jié)點，SKi，Ui表示合法的用戶是Ki的后代葉子節(jié)點，而不是Ui的后代葉子節(jié)點.如圖1中葉子節(jié)點1，2的用戶為合法的接收者，而3，4不是.這被稱為SD(subset sifference)方法，并證明了只要O(R)個集合就可支持任意的撤銷，R為被撤銷用戶數(shù)量，且用戶不用更新自己的私鑰，因而效率較高.

RL就是上述NNL廣播加密中的{SK1，U1，SK2，U2，…,SKm，Um}和GM對每個子集的SPS簽名.進行群簽名是合法的群成員首先要RL中找到自己位于哪個子集(注意被撤銷的群成員是找不到這樣的子集的，所以他沒有簽名的權(quán)利)中，如SKi，Ui；然后，群成員要以匿名的方式證明自己的合法性(因其證書是SPS簽名，而RL中的也是SPS簽名，所以可用Groth-Sahai證明系統(tǒng)來做)，即自己的群證書中的路徑I1，I2，…，Il(保存在Cv中)是符合子集SKi，Ui的.即在φi層上(Ki所位于的層)Cv中的節(jié)點編號是Ki，而在ψi層上(Ui所位于的層)Cv中的節(jié)點編號≠Ui，從而證明了自己是合法的群成員.

注意Cv采用的技術(shù)是簡潔向量承諾(concise vector commitment，CVC)方案[16]，即承諾方可對一個向量(有多個坐標(biāo))進行承諾，在此就是從根到某個葉子節(jié)點的一條路徑(I1，I2，…,Il)，然后,可對向量中的任一個坐標(biāo)進行高效打開(即證據(jù)的大小不依賴于向量大小).CVC可與NNL廣播加密方案很好地結(jié)合,實現(xiàn)高效群成員合法性證明，即成員在證明自己的合法性時，只要先對從根到自己所在的葉子結(jié)點的一條路徑進行承諾為Cv，然后,證明承諾中的值第φi個坐標(biāo)是等于Ki的，而第ψi個坐標(biāo)是不等于Ui的，這樣就證明了自己的合法性.

2.3 安全性與性能分析

在上述基于GS方案的BE方案構(gòu)建中，合法的群成員能提供出合法的未被撤銷的簽名私鑰，即下述NP語言的證據(jù)：

NP={GS.GPK|?Usk是合法的∧Usk未被撤消}.

因而根據(jù)WE方案的定義，此成員能夠?qū)E密文進行解密，從而得到加密的廣播消息；而不合法的成員(如沒有證書，或其證書被撤消，即在RL中)由于沒有NP證據(jù)就不能對密文進行解密，得不到廣播的消息.

上述基于BE的GS方案的安全性分析與證明可參見文獻[15].其基本思想如下：合法的成員用NIZK證明自己具有BE的解密私鑰且未被撤銷，此NIZK可作為GS簽名，即自己是合法的群成員.

在性能方面，文獻[15]中的GS方案效率很高，是迄今撤銷效率最高的標(biāo)準(zhǔn)模型下可撤銷群簽名方案.同以前的撤銷方案相比，其優(yōu)勢在于：公鑰大小為O(logN)，簽名和驗證的復(fù)雜度都為O(1)，撤銷成員時用戶不需要更新自己的私鑰，此種撤銷效率超越了以前的任何一種方案.

上述的基于GS和WE的BE方案構(gòu)建，效率不是很高，是因為構(gòu)建中要把用到的NP語言歸約到WE方案中的NP完全問題(如文獻[12]中的構(gòu)建用到的是精確覆蓋問題)，而這種規(guī)約通常效率較低.

3 結(jié)論

提出群簽名與廣播加密之間有密切的對偶關(guān)系，并給出了如何具體實現(xiàn)這種對偶關(guān)系.即基于WE可把一個可撤銷群簽名方案轉(zhuǎn)換為一個可撤銷廣播加密方案，而基于NIZK可把一個撤銷廣播加密方案轉(zhuǎn)換為一個可撤銷群簽名方案.同時，指出基于廣播加密的高效可撤銷群簽名方案可以納入文中所提出來的框架中.

文中提出這種非平凡的對偶關(guān)系對各自方案的構(gòu)建提供了新的思路與方法，但基于GS和WE的BE方案僅僅是理論上的方案構(gòu)建，還不能夠應(yīng)用于實際，其價值體現(xiàn)在理論上.文中提出了BE的構(gòu)建的另一種思想，未來如果出現(xiàn)高效的直接的WE方案構(gòu)建，那么理論方案也就可應(yīng)用于實際.

本研究工作應(yīng)該說只是一個開始，還有大量的研究工作有待進行.即探索大量面向群組的密碼系統(tǒng)(如群簽名、群加密[17]、廣播加密、叛逆者追蹤、環(huán)簽名[18]、秘密分享和門限簽名[19]等)之間的非平凡關(guān)系，以及高效的相互轉(zhuǎn)換的理論與方法.

[1] CHAUM D,HEYST E.Group signatures[C]∥DAVIES D.Advances in Cryptology： EUROCRYPT′91.Heidelberg:Springer-Verlag,1991:257-265.

[2] 程小剛,王箭,杜吉祥.群簽名綜述[J].計算機應(yīng)用研究,2013,30(10):2881-2886.

[3] 陳曉峰,王育民.基于匿名通訊信道的安全電子投票方案[J].電子學(xué)報,2003,31(3):390-393.

[4] 李夢東,楊義先,馬春光,等.由群簽名實現(xiàn)的可撤銷匿名性的電子現(xiàn)金方案[J].北京郵電大學(xué)學(xué)報,2005,28(2):30-33.

[5] BRICKELL E,LI J.Enhanced privacy ID: A direct anonymous attestation scheme with enhanced revocation capabilities[J].IEEE Transactions on Dependable and Secure Computing,2012,9(3):345-360.

[6] AFANASYEV M,KOHNO T,MA J,et al.Privacy-preserving network forensics[J].Commun ACM,2011,54(5):78-87.

[7] FIAT A,NAOR M.Broadcast encryption[C]∥STINSON D R.Advances in Cryptology: CRYPTO′93.Heidelberg: Springer-Verlag,1994:480-491.

[8] CHOR B,FIAT A,NAOR M.Tracing traitors[C]∥DESMEDT Y G.Advances in Cryptology: CRYPTO′94.Heidelberg:Springer-Verlag,1994:257-270.

[9] KIAYIAS A,YUNG M.Extracting group signatures from traitor tracing schemes[C]∥BJHAM E.Advances in Cryptology: EUROCRYPT 2003.Heidelberg:Springer-Verlag,2003:630-648.

[10] NAOR D,NAOR M,LOTSPIECH J.Revocation and tracing schemes for stateless receivers[C]∥KILIAN J.Advances in Cryptology: CRYPTO 2001.Heidelberg:Springer-Verlag,2001:41-62.

[11] 張德棟,馬兆豐,楊義先,等.群簽名中成員撤銷問題解決方案[J].通信學(xué)報,2014,35(3):193-200.

[12] GARG S,GENTRY C,SAHAI A,etal.Witness encryption and its applications[C]∥Proceedings of the Annual Acm Symposium on Theory of Computing.New York:[s.n.],2013:467-476.doi:10.1145/2488608.2488667.

[13] DODIS Y,FAZIO N.Public key broadcast encryption for stateless receivers[C]∥Digital Rights Management.Heidelberg:Springer-Verlag,2003:61-80.

[14] LIBERT B,PETERS T,YUNG M.Scalable group signatures with revocation[C]∥POINTCHEVAL D,JOHANSSON T.Advances in Cryptology: EUROCRYPT 2012.Heidelberg:Springer-Verlag,2012:609-627.

[15] LIBERT B,PETERS T,YUNG M.Group signatures with almost-for-free revocation[C]∥SAFAVI-NAINI R,CANETTI R.Advances in Cryptology: CRYPTO 2012.Heidelberg:Springer-Verlag,2012:571-589.

[16] LIBERT B,YUNG M.Concise mercurial vector commitments and independent zero-knowledge sets with short proofs[C]∥International Conference on Theory of Cryptography.Heidelberg:Springer-Verlag,2010:499-517.

[17] CATHALO J,LIBERT B,YUNG M.Group encryption: Non-interactive realization in the standard model[C]∥MATSUI M.Advances in Cryptology:ASIACRYPT 2009.Heidelberg: Springer-Verlag,2009:179-196.

[18] RIVEST R L,SHAMIR A,TAUMAN Y.How to leak a secret[C]∥BOYD C.Advances in Cryptology:ASIACRYPT 2001.Heidelberg: Springer,2001:552-565.

[19] 韓金廣,亢保元,王慶菊.面向群通信的門限簽名方案的密碼學(xué)分析[J].華僑大學(xué)學(xué)報(自然科學(xué)版),2008,29(2):213-217.doi:10.11830/ISSN.1000-5013.2008.02.0213.

(責(zé)任編輯： 黃仲一 英文審校： 吳逢鐵)

Duality Between Group Signature and Broadcast Encryption and Its Applications

CHENG Xiaogang1， GUO Ren2， CHEN Yonghong1

(1. College of Computer Science and Technology， Huaqiao University， Xiamen 361021， China；2. College of Business Administration， Huaqiao University， Quanzhou 362021， China)

Group signature (GS) and broadcast encryption (BE) are shown to be dual with each other， similar with the duality between public key encryption (PKE) and digital signature. Namely， BE can be transformed to a GS scheme and vice versa. Concrete construction methods and procedures are given i.e., a revocable GS scheme can be transformed to a BE scheme based on NP (non-deterministic polynomial) witness encryption (WE) and a revocable BE can be transformed to a GS based on non-interactive zero knowledge (NIZK) proof. Finally, it point out that an efficient revocable GS scheme based on BE is also shown to be one incarnation of our framework. Keywords： group signature； broadcast encryption； duality； NP witness encryption； membership revocation

10.11830/ISSN.1000-5013.201702014

2016-05-22

程小剛(1973-)，男，講師，博士，主要從事信息安全、密碼學(xué)的研究.E-mail:cxg@hqu.edu.cn.

國家自然科學(xué)基金資助項目(61370007)； 福建省自然科學(xué)基金資助項目(2016J01336)； 福建省社會科學(xué)規(guī)劃項目(FJ2016B090); 華僑大學(xué)高層次人才科研啟動項目(16BS309)

TP 309

A

1000-5013(2017)02-0207-05