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

程小剛， 郭韌， 陳永紅

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

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

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

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

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

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

1 初步知識(shí)

定義1 群簽名一般由下面6個(gè)隨機(jī)多項(xiàng)式時(shí)間算法組成.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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)識(shí)為ID的用戶的私鑰，Challenger利用其掌握的MSK生成私鑰，發(fā)送給ADV，并將所有ADV查詢過(guò)的ID加入集合Q中；

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

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

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

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

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

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

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

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

定義3 WE(NP證據(jù)加密).針對(duì)一NP語(yǔ)言L的WE方案有如下的多項(xiàng)式時(shí)間算法.

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

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

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

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

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

2) 公正性.如果x?L，那么對(duì)于任何的多項(xiàng)式時(shí)間敵手A來(lái)說(shuō)，除了可忽略概率之外，對(duì)兩個(gè)不同消息加密的密文分布是相同的，即

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

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

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

BE.Setup，就是GS.Setup；

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

BE.Encrypt,用如下的NP語(yǔ)言利用WE對(duì)消息m進(jìn)行加密,即

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

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

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

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

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

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

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

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

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

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

2.3 安全性與性能分析

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

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

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

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

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

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

3 結(jié)論

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

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

本研究工作應(yīng)該說(shuō)只是一個(gè)開(kāi)始，還有大量的研究工作有待進(jìn)行.即探索大量面向群組的密碼系統(tǒng)(如群簽名、群加密[17]、廣播加密、叛逆者追蹤、環(huán)簽名[18]、秘密分享和門(mén)限簽名[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].計(jì)算機(jī)應(yīng)用研究,2013,30(10):2881-2886.

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

[4] 李夢(mèng)東,楊義先,馬春光,等.由群簽名實(shí)現(xiàn)的可撤銷匿名性的電子現(xiàn)金方案[J].北京郵電大學(xué)學(xué)報(bào),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] 張德棟,馬兆豐,楊義先,等.群簽名中成員撤銷問(wèn)題解決方案[J].通信學(xué)報(bào),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] 韓金廣,亢保元,王慶菊.面向群通信的門(mén)限簽名方案的密碼學(xué)分析[J].華僑大學(xué)學(xué)報(bào)(自然科學(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.

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

TP 309

A

1000-5013(2017)02-0207-05