郭　韌，陳福集，程小剛

(1. 福州大學(xué)經(jīng)濟與管理學(xué)院　福州　350116；2. 華僑大學(xué)工商管理學(xué)院　福建 泉州　362021；3. 華僑大學(xué)計算機學(xué)院　福建 廈門　361021)

基于NP證據(jù)加密的可撤銷廣播加密方案構(gòu)建

郭韌1,2，陳福集1，程小剛3

(1. 福州大學(xué)經(jīng)濟與管理學(xué)院福州350116；2. 華僑大學(xué)工商管理學(xué)院福建 泉州362021；3. 華僑大學(xué)計算機學(xué)院福建 廈門361021)

NP(non-deterministic polynomial)證據(jù)加密(witness encryption,WE)是近來提出的一種新型的沒有密鑰生成過程的加密方案，可以用來構(gòu)建許多其他的密碼系統(tǒng)如公開密鑰加密、IBE(identity based encryption)、ABE(attribute based encryption)等。該文提出WE的一種新應(yīng)用：用WE構(gòu)建可撤銷廣播加密系統(tǒng)，并且所構(gòu)建的廣播加密方案能支持簡單的成員重加入功能(如付費電視)；在構(gòu)建的過程中指出以前的WE安全性定義不夠嚴格，對原WE安全性定義進行了增強，并基于原WE方案和子集成員分辨難題、ROM(random oracle model)模型提出了一個新方案。

廣播加密;子集成員分辨難題;成員撤銷;NP證據(jù)加密

WE是文獻[1]提出的一種新的沒有密鑰生成過程的加密系統(tǒng)，它以一個NP語言(NP語言是一個能在多項式時間內(nèi)被一臺非確定圖靈機所接受的語言)L的實例x作為公鑰對消息m進行加密。如果x∈L且解密者有相關(guān)的NP證據(jù)w，則可以對密文解密得到消息m；若x?L，則加密是語義安全的(semantic secure)。文獻[1]給出了WE的多種應(yīng)用，如公鑰加密方案、IBE和ABE等。

廣播加密(broadcast encryption,BE)[2]典型的應(yīng)用是付費電視，電視臺對視頻節(jié)目進行加密后廣播出去，任何人都可以收到加密后的視頻，但只有付過費的合法用戶(擁有相關(guān)密鑰)才能解密正常收看電視節(jié)目。

本文提出WE的另一個應(yīng)用，即用于構(gòu)建可撤銷的BE方案[3-4]，所構(gòu)建的可撤銷BE方案具有簡單的成員重新加入功能，此功能適合類似付費電視等相關(guān)的應(yīng)用：欠費的用戶被停機，而當用戶繳清欠費后又要恢復(fù)其成員資格。在構(gòu)建的過程中，指出了原來的WE安全性定義對本文的應(yīng)用來說不夠嚴格，為此對WE的安全性定義進行了加強。

基于WE來構(gòu)建BE方案的思想如下：BE系統(tǒng)中用戶的解密私鑰是電視臺頒發(fā)的一個簽名(如對其用戶名的簽名)，加密時使用WE方案進行視頻加密。在加密方案構(gòu)建中所基于的NP語言L是，其實例x是一個簽名方案的驗證公鑰PKSign，NP證據(jù)就是一合法的消息/簽名對(ID,δ)；對于合法的BE系統(tǒng)用戶，其擁有合法的消息/簽名對(即合法的NP證據(jù))能解密密文；對于非法用戶，由于其沒有相關(guān)NP證據(jù)就不能解密密文(要對原WE安全性進行加強，因原定義只對x?L的情況進行了規(guī)定，沒考慮到x∈L但解密者沒有相關(guān)NP證據(jù)w的情況)；這只是實現(xiàn)了BE的基本功能，為了撤銷某個用戶，系統(tǒng)還要維護一個撤銷列表(revocation list,RL)，保存所有被撤銷用戶的名單，并在每次有用戶被撤銷時，將原NP語言進行更新，即：

這樣被撤銷的用戶就不再擁有對此NP語言的合法證據(jù)(因其ID在撤銷列表RL中)，也就不能再對廣播密文進行解密；而假如某撤銷用戶要重新加入時(如其繳清欠費)，系統(tǒng)只要從RL中把該用戶的ID刪除即可。

1　理論知識

本節(jié)給出NP證據(jù)加密WE及其安全性的定義、廣播加密BE的定義及其安全模型。

定義1WE方案：針對NP語言L的WE方案有如下的多項式時間算法。

ENC(1λ,x,M)：輸入安全參數(shù)λ、字符串x和待加密的消息M，輸出密文CT；

DEC(CT,w)：輸入密文CT、字符串w，輸出消息M或特殊字符⊥。

并且這些算法滿足下面的性質(zhì)：

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

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

文獻[1]基于多線性映射[5]構(gòu)建了一個具體的WE方案，所基于的NP語言L為NP完全問題——子集覆蓋問題[6]，但其缺陷在于所基于的數(shù)學(xué)假設(shè)同此NP問題是緊密相關(guān)的；為此文獻[7]中提出了基于獨立于所用NP語言假設(shè)的WE構(gòu)建[7]，所用的技術(shù)是另一種基于整數(shù)的多線性映射方案[8]，但文獻[8]中的方案最近被完全攻破[9]，因此文獻[7]的構(gòu)建也是不安全的，構(gòu)建基于獨立于所用NP語言假設(shè)的WE方案仍是重要的公開問題。

另外在此定義中存在一種重要的情況沒有被安全定義，即敵手A知道x∈L，但A不知道相關(guān)的NP證據(jù)的情況。

下面給出可撤銷廣播加密方案的定義和安全模型定義。

定義2構(gòu)成BE的多項式算法如下：

1)setup: 生成系統(tǒng)的主公/私鑰對MPK/MSK，并初始將RL設(shè)置為空；

2)join: 標識為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)revo：系統(tǒng)管理員將欲撤銷的用戶的標識ID放入RL中去，標識其以后不再能收到消息；

6)re-join：系統(tǒng)管理員將用戶ID從RL中刪除，此后該用戶就能正常接收廣播消息。

定義3BE的抗明文攻擊安全性(indistinguishable against chosen plaintext attack,IND_CPA)：

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

2)ADV能自適應(yīng)地向challenger查詢?nèi)我粋€標識為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對mb進行加密得到密文CT，將密文發(fā)送給ADV；

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

2　構(gòu)建

2.1WE安全性增強與擴展

定義4增強的WE除了要滿足原來的正確性、公正性之外，還要滿足第三個安全性質(zhì)——特別公正性(special soundness)：即使敵手A知道x∈L，但他沒有相關(guān)的NP證據(jù)w，那么加密對他來說仍然是語義安全的，即：

下面基于原來的WE方案和子集成員分辨難題(hard subset membership problem,HSMP)來構(gòu)建一個滿足特別公正性的方案。

所用的NP語言L為一個HSMP問題，如DDH[10]、DLIN[11]或任一個矩陣DH[12]等，為簡單起見，下面的敘述以DDH為例，其他的HSMP問題也一樣可以。

著名的DDH問題就是要把元組(gr,hr)和分辨開來，NP語言是，NP證據(jù)是r；此語言的一個實例是兩個群元素，增強的WE構(gòu)建是利用原來的WE方案，并用此DDH語言作為所用的NP語言來加密消息。

WE. setup：把上述的DDH問題規(guī)約到一個子集精確覆蓋(exact cover)問題，因為精確覆蓋問題是一NP完全問題，此種規(guī)約一定存在，然后用原WE方案進行加解密操作；

WE.ENC：前面所得的精確覆蓋問題x，即若干子集Ti和全集[n]，對于給定的消息M，隨機選擇n個數(shù)，計算，此外對每個子集Ti生成，最后輸出密文

定理1 上述的基于DDH語言的WE方案除了滿足原來的WE安全性之外，如果DDH假設(shè)成立，那么還滿足增強的特別公正性。

2)公正性

3)特別公正性

假設(shè)存在敵手A此時能打破密文的語義安全性，證明利用此敵手A就能攻破DDH假設(shè)，歸約方法如下：

給定兩個群元素(G,H)，要判定其是否為DDH元組，只要利用此元組作為一個NP語言實例x來加密從m0、m1中隨機選擇的消息mb，然后將密文發(fā)給敵手A，那么基于A猜測的正確性，就能知道(G,H)是否為DDH元組。如果A的猜測是正確的，那么(G,H)是DDH元組，因為此時恰為而A沒有相應(yīng)NP證據(jù)的情況，根據(jù)A的定義他猜測正確的概率較大；如果A的猜測是錯誤的，那么顯然，因為此時根據(jù)原來的WE方案的安全性(即x?L的情況)，任何人都不能打破密文的語義安全性。

上述構(gòu)建的一個缺陷是通常HSMP問題都不是NP完全問題(如DDH、DLIN等)，而理論上不能把任一NP問題都歸結(jié)為HSMP問題，這就制約了WE的許多應(yīng)用。實現(xiàn)針對一個NP完全問題的具有特殊公正性的WE方案是一個有趣的公開問題。

對上述構(gòu)建進行擴展，使其能直接用于構(gòu)建BE方案。所用的NP語言是基于ROM模型[13]的一個簽名方案(或稱為Fiat-Shamir轉(zhuǎn)換[14]，把交互式零知識證明系統(tǒng)轉(zhuǎn)換為非交互式知識簽名(signature of proof of knowledge,SPK)[15])。該簽名方案的公鑰(G,H)=(gr,hr)，簽名，實現(xiàn)方法如下：

此擴展的WE方案滿足特別公正性的證明基本上同定理1的證明是相同的，即如果存在打破特別公正性的敵手，那么能利用敵手來攻破DDH假設(shè)。

2.2基于增強WE的BE方案構(gòu)建

下面基于增強的WE方案來構(gòu)建可撤銷的BE方案：

1)KeyGen：生成上述基于SPK簽名方案的PK/SK作為MPK/MSK，即公鑰(,)(r,r)G H=g h ，私鑰為r，初始時將撤銷列表RL設(shè)置為空，即沒有用戶被撤銷。

2)UserKeyGen(ID)：對名為ID的用戶頒發(fā)證書為ID的簽名，即，用戶可以檢查其證書是否合法，即Verify(ID,δ)=1是否成立。

3)ENC(m)：對消息m進行加密是用前述的WE方案加密得到的密文CT，所用的NP語言L為：

針對驗證公鑰MPK存在一合法的消息/簽名對(ID,)δ，其中消息ID不在撤銷列表RL中(RL開始為空，每撤銷一個用戶就把其ID加入RL中去)。

4)DEC(CT)：對于合法的用戶其擁有合法的消息/簽名對(ID,)δ，且其ID不在RL中，也即其擁有針對上述NP語言合法的NP證據(jù)，則顯然可以利用WE方案的解密算法對密文CT進行解密得到消息m；對于非法的用戶，其沒有消息/簽名對，或者其ID已在RL中，都沒有合法的NP證據(jù)，也就不能對用WE方案加密的密文進行解密。

5)Revo：撤銷某用戶時，只要將其ID加入到RL中，同時也要更新此后要發(fā)廣播消息時用的NP語言L，在L中要使用最新的撤銷列表，來排除剛撤銷的用戶。

6)Re-join：假如RL中某被撤銷用戶要重新加入(如用戶繳清欠費等)，系統(tǒng)管理員只要從RL中將其ID刪除即可。

2.3性能與比較

上述BE和WE方案構(gòu)建中，由于要把DDH語言的實例規(guī)約為NP完全問題——精確覆蓋問題，這種規(guī)約通常效率較低，所以本文提出的基于WE的BE方案是理論上的方案構(gòu)建，還不能夠應(yīng)用于實際；目前已有一些高效的BE方案：如文獻[16]中提出的基于多線性映射的高效BE方案，實現(xiàn)了密文大小、公私鑰大小等都比較短(對數(shù)級大小)、而且也支持基于身份的BE；因此本文BE方案更大意義的在于理論價值：提出了WE的另一個應(yīng)用——BE的構(gòu)建，進一步拓展了WE方案的應(yīng)用領(lǐng)域，未來如果出現(xiàn)高效直接的WE方案構(gòu)建，本文的理論方案就可應(yīng)用于實際。

3　安全性證明

定理2基于原WE方案的安全性、DDH假設(shè)和ROM模型，上述基于增強WE方案構(gòu)建的BE方案是IND_CPA安全的。

證明：如果存在能攻破BE方案的IND_CPA敵手A，利用A就可以解決DDH難題。歸約如下：

給定一對群元素(G,H)，要判斷其是否是 DDH元組，挑戰(zhàn)者把(G,H)作為公鑰生成上述的 BE方案，并把MPK=(G,H)發(fā)給A，交互如下：

1)用戶私鑰查詢：當A發(fā)出對標識為ID的用戶的私鑰查詢時，挑戰(zhàn)者可按如下方式模擬簽名(基于ROM模型及證明的零知識特性)：

挑戰(zhàn)者選擇隨機的s和c，并設(shè)置scG′=g G 和，控制隨機預(yù)言器(random oracle)對查詢返回值c，并返回簽名。注意即使(G,H)不是DDH元組，此模擬簽名仍能通過驗證方程，而如果(G,H)是DDH元組，此模擬簽名和實際簽名的概率分布是一樣的。敵手A查詢的所有ID都放入集合Q中。

2)挑戰(zhàn)階段：敵手A生成兩個長度相同內(nèi)容不同的消息m0和m1，并發(fā)給挑戰(zhàn)者，挑戰(zhàn)者先把集合Q中的所有ID放入RL中，并隨機地選b=0或1，對mb用WE進行加密，所用的NP語言為式(7)中的NP語言。

然后把密文CT發(fā)給敵手A。

3)敵手A要根據(jù)CT來猜測b=0還是1，根據(jù)敵手A回答的正確性，挑戰(zhàn)者就能解決DDH問題：如果A回答正確，則(G,H)是DDH元組，上述模擬是完美的，根據(jù)A的IND_CPA的定義其成功率較高；而如果A的回答是錯誤的，則(G,H)不是DDH元組，此時對敵手A來說合法簽名是不存在的(因其沒有對隨機預(yù)言器的控制能力)，即上述WE定義中x?L的情況，根據(jù)原WE方案的安全性，A的成功概率是可以被忽略的。

為敘述簡單起見，上述的證明只能實現(xiàn)IND_CPA的安全性，在安全性定義的博弈中沒有解密的Oracle，但注意上述的理論方案也可以實現(xiàn)IND_CCA的安全性，此時只需要模擬一個解密的Oracle，挑戰(zhàn)者擁有對隨機預(yù)言器的控制能力，對任意ID都能生成合法的“偽造”簽名，這個“偽造”簽名就是一個合法的NP證據(jù)，利用此證據(jù)挑戰(zhàn)者可對任意的消息進行解密，從而模擬解密Oracle。

4　結(jié) 束 語

本文提出了WE一種新的應(yīng)用，可用于構(gòu)建可撤銷的廣播加密方案，所構(gòu)建的廣播加密方案具有非常簡單的成員重加入功能；在構(gòu)建過程中，指出原來的WE方案的安全性定義不夠強，沒有考慮一種非常重要的情況：即敵手知道x∈L，但沒有相關(guān)的NP證據(jù)，為此提出的一種增強的WE安全性，即“特別公正性”；并基于HSMP和原來的WE方案構(gòu)建了一個符合此安全性要求的WE方案，并在此增強WE方案的基礎(chǔ)之上來構(gòu)建可撤銷的廣播加密方案。

本文增強的WE方案構(gòu)建是基于HSMP問題的，而HSMP問題(如DDH、DLIN等)通常不是NP完全問題，因此不是所有NP問題都能歸約到HSMP問題，這可能會限制其應(yīng)用領(lǐng)域。所以一個重要的公開問題就是如何基于NP完全問題來構(gòu)建增強的WE方案。

[1]GARG S,GENTRY C,SAHAI A,et al. Witness encryption and its applications[C]//The 45th ACM Symposium on Theory of Computing (STOC 2013). New York,USA: ACM,2013: 467-476.

[2]FIAT A,NAOR M. Broadcast encryption[C]// Advances in Cryptology-CRYPTO’ 93. California,USA: Springer Berlin Heidelberg,1994: 480-491.

[3]DODIS Y,FAZIO N. Public key broadcast encryption for stateless receivers[C]//Digital Rights Management 2002. Washington,USA: Springer,2003: 61-80.

[4]NAOR D,NAOR M,LOTSPIECH J. Revocation and tracing schemes for stateless receivers[C]// Advances in Cryptology-CRYPTO 2001. California,USA: Springer Berlin Heidelberg,2001: 41-62.

[5]GARG S,GENTRY C,HALEVI S. Candidate multilinear maps from ideal lattices[C]//Advances in Cryptology-EUROCRYPT 2013. Athens,Greece: Springer,2013:1-17.

[6]GAREY M,JOHNSON D. Computers and intractability: a guide to the theory of NP-completeness[M]. San Francisco,USA: W. H. Freeman and Co,1979.

[7]GENTRY C,LEWKO A,WATERS B. Witness encryption from instance independent assumptions[C]//Advances in Cryptology-CRYPTO 2014. California,USA: Springer,2014: 426-443.

[8]CORON J,LEPOINT T,TIBOUCHI M. Practical multilinear maps over the integers[C]//Advances in cryptology-CRYPTO 2013. California,USA: Springer,2013: 476-493.

[9]CHEON J,HAN K,LEE C,et al. Cryptanalysis of the multilinear map over the integers[C]//Advances in Cryptology-EUROCRYPT 2015. Sofia,Bulgaria: Springer,2015: 3-12.

[10]DIFFIE W,HELLMAN M. New directions in cryptography[J]. IEEE Transactions on Information Theory 2006,22(6): 644-654.

[11]BONEH D,BOYEN X,SHACHAM H. Short group signatures[C]//Advances in Cryptology-CRYPTO 2004. California,USA: Springer,2004: 41-55.

[12]ESCALA A,HEROLD G,KILTZ E,et al. An algebraic framework for diffie-hellman assumptions[C]//Advances inCryptology-CRYPTO 2013. California,USA: Springer,2013: 129-147.

[13]BELLARE M,ROGAWAY P. Random oracles are practical: a paradigm for designing efficient protocols[C]//ACM Conference on Computer and Communications Security 1993. New York,USA: ACM,1993: 62-73.

[14]FIAT A,SHAMIR A. How to prove yourself: Practical solutions to identification and signature problems[C]// Advances in Cryptology-CRYPTO’ 86. California,USA: Springer,1987: 186-194.

[15]CAMENISCH J,STADLER M. Efficient group signature schemes for large groups[C]//Advances in Cryptology-CRYPTO '97. California,USA: Springer,1997: 410-424.

[16]BONEH D,WATERS B,ZHANDRY M,et al. Low overhead broadcast encryption from multilinear maps[C]// Advances in Cryptology-CRYPTO 2014. California,USA: Springer,2014: 206-223.

編輯葉芳

Construction of Revocable Broadcast Encryption Based on Witness Encryption

GUO Ren1,2,CHEN Fu-ji1,and CHENG Xiao-gang3
(1. School of Economic and Management,Fuzhou UniversityFuzhou350116; 2. College of Business Administration,Huaqiao UniversityQuanzhou Fujian362021; 3. College of Computer Science and Technology,Huaqiao UniversityXiamen Fujian361021)

Witness encryption (WE)is a new type of encryption scheme without key generation.It can be used for construction of many other cryptosystems such as public key encryption,IBE,ABE,etc. A new WE application is presented,i.e.,the construction of revocable broadcast encryption (BE)based on WE. The constructed BE scheme also supports a simple re-membership function,which is suitable for applications like pay-TV etc. In the construction,we also point out that the original security definition of WE is not strong enough. So we strengthen the original WE security definition and construct a WE scheme satisfying this new definition based on the original WE scheme,hard subset membership problem and random oracle model.

broadcast encryption;hard subset membership problem;membership revocation;NP witness encryption

TP309

A

10.3969/j.issn.1001-0548.2016.06.016

2016 ? 3 ? 14；

2016 ? 6 ? 16

國家自然科學(xué)基金(71271056)，福建省自然科學(xué)基金(2016J01336)

郭韌(1975 ? )，女，博士生，主要從事信息系統(tǒng)、信息安全方面的研究.