-
WE是文献[1]提出的一种新的没有密钥生成过程的加密系统,它以一个NP语言(NP语言是一个能在多项式时间内被一台非确定图灵机所接受的语言)L的实例x作为公钥对消息m进行加密。如果x L且解密者有相关的NP证据w,则可以对密文解密得到消息m;若x L,则加密是语义安全的(semantic secure)。文献[1]给出了WE的多种应用,如公钥加密方案、IBE和ABE等。
广播加密(broadcast encryption, BE)[2]典型的应用是付费电视,电视台对视频节目进行加密后广播出去,任何人都可以收到加密后的视频,但只有付过费的合法用户(拥有相关密钥)才能解密正常收看电视节目。
本文提出WE的另一个应用,即用于构建可撤销的BE方案[3-4],所构建的可撤销BE方案具有简单的成员重新加入功能,此功能适合类似付费电视等相关的应用:欠费的用户被停机,而当用户缴清欠费后又要恢复其成员资格。在构建的过程中,指出了原来的WE安全性定义对本文的应用来说不够严格,为此对WE的安全性定义进行了加强。
基于WE来构建BE方案的思想如下:BE系统中用户的解密私钥是电视台颁发的一个签名(如对其用户名的签名),加密时使用WE方案进行视频加密。在加密方案构建中所基于的NP语言L是$\{ {\rm{P}}{{\rm{K}}_{{\rm{Sign}}}}:\exists ({\rm{ID}}, \delta ), {\rm{Verify}}({\rm{ID}}, \delta, {\rm{P}}{{\rm{K}}_{{\rm{Sign}}}}) = 1\} $,其实例x是一个签名方案的验证公钥PKSign,NP证据就是一合法的消息/签名对$({\rm{ID}}, \delta )$;对于合法的BE系统用户,其拥有合法的消息/签名对(即合法的NP证据)能解密密文;对于非法用户,由于其没有相关NP证据就不能解密密文(要对原WE安全性进行加强,因原定义只对$x \notin L$的情况进行了规定,没考虑到$x \in L$但解密者没有相关NP证据w的情况);这只是实现了BE的基本功能,为了撤销某个用户,系统还要维护一个撤销列表(revocation list, RL),保存所有被撤销用户的名单${\rm{RL}} = \{ {\rm{I}}{{\rm{D}}_1}, {\rm{I}}{{\rm{D}}_2}, \cdots, {\rm{I}}{{\rm{D}}_R}\} $,并在每次有用户被撤销时,将原NP语言进行更新,即:
$$ \{ {\rm{P}}{{\rm{K}}_{{\rm{Sign}}}}:\exists ({\rm{ID}}, \delta ), {\rm{Verify}}({\rm{ID}}, \delta, {\rm{P}}{{\rm{K}}_{{\rm{Sign}}}}) = 1 \wedge {\rm{ID}} \notin RL\} $$ (1) 这样被撤销的用户就不再拥有对此NP语言的合法证据(因其ID在撤销列表RL中),也就不能再对广播密文进行解密;而假如某撤销用户要重新加入时(如其缴清欠费),系统只要从RL中把该用户的ID删除即可。
-
本节给出NP证据加密WE及其安全性的定义、广播加密BE的定义及其安全模型。
定义1 WE方案:针对NP语言L的WE方案有如下的多项式时间算法。
ENC (1λ, x, M):输入安全参数λ、字符串x和待加密的消息M,输出密文CT;
DEC (CT, w):输入密文CT、字符串w,输出消息M或特殊字符⊥。
并且这些算法满足下面的性质:
正确性:如果$x \notin L$且w是相应的NP证据,那么解密算法总能正确解密得到消息M,即:
$$ \Pr [{\rm{DEC}}({\rm{ENC}}({1^\lambda }, x, M), w) = M] = 1 $$ (2) 公正性:如果$x \notin L$,那么对于任何的多项式时间敌手A来说,除了可忽略概率之外,对两个不同消息m0和m1加密的密文分布是相同的,即:
$$ \begin{array}{l} \;\;\;\;\;\;\;\;|\Pr [A({\rm{ENC}}({1^\lambda }, x, {m_0})) = 1] - \\ \Pr [A({\rm{ENC}}({1^\lambda }, x, {m_1})) = 1]| < {\rm{negligible}}(\lambda ) \end{array} $$ (3) 文献[1]基于多线性映射[5]构建了一个具体的WE方案,所基于的NP语言L为NP完全问题--子集覆盖问题[6],但其缺陷在于所基于的数学假设同此NP问题是紧密相关的;为此文献[7]中提出了基于独立于所用NP语言假设的WE构建[7],所用的技术是另一种基于整数的多线性映射方案[8],但文献[8]中的方案最近被完全攻破[9],因此文献[7]的构建也是不安全的,构建基于独立于所用NP语言假设的WE方案仍是重要的公开问题。
另外在此定义中存在一种重要的情况没有被安全定义,即敌手A知道$x \in L$,但A不知道相关的NP证据的情况。
下面给出可撤销广播加密方案的定义和安全模型定义。
定义2 构成BE的多项式算法如下:
1) setup:生成系统的主公/私钥对MPK/MSK,并初始将RL设置为空;
2) join:标识为ID的用户向系统申请加入,系统管理员审核后由(MSK, ID)生成用户私钥SKID并颁发给用户;
3) ENC (MPK, m, RL):用系统公钥MPK及RL对消息m进行加密,得到密文CT;
4) DEC (CT, SKID):任何合法的用户(具有合法的私钥SKID,且其${\rm{ID}} \notin {\rm{RL}}$),可对密文CT进行解密得到消息m;
5) revo:系统管理员将欲撤销的用户的标识ID放入RL中去,标识其以后不再能收到消息;
6) re-join:系统管理员将用户ID从RL中删除,此后该用户就能正常接收广播消息。
定义3 BE的抗明文攻击安全性(indistinguishable against chosen plaintext attack, IND_CPA):
1) challenger生成BE方案的MPK/MSK,并把MPK发送给敌手ADV;
2) ADV能自适应地向challenger查询任一个标识为ID的用户的私钥,challenger利用其掌握的MSK生成私钥,并发送给ADV,并将所有ADV查询过的ID加入到集合Q中;
3) ADV生成任意两个长度相同但内容不同的消息m0、m1,并发送给challenger;
4) challenger首先将集合Q中的所有用户放入RL中去,再随机选择b=0或1,用MPK和RL对mb进行加密得到密文CT,将密文发送给ADV;
5) ADV收到CT后,要猜测b=0还是1,称BE是IND_CPA安全的,如果ADV的成功概率同1/2的差是可忽略的,即:
$$ |\Pr [{\rm{ADV}}({\rm{CT}}) \to b':b' = b] - 1/2| < {\rm{negligible}}(\lambda ) $$ (4) -
在前文中提到,本文所用的NP语言L为:$\{ {\rm{P}}{{\rm{K}}_{{\rm{Sign}}}}:\exists ({\rm{ID}}, \delta ), {\rm{Verify}}({\rm{ID}}, \delta, {\rm{P}}{{\rm{K}}_{{\rm{Sign}}}}) = 1\} $,对于该语言其NP证据有无穷多(因任一合法的消息/签名对就是NP证据),任何敌手都知道有无穷多证据,即$x \in L$总是成立的。正常情况下不会出现$x \notin L$的情况,而WE原有的安全性定义中对此情况(即敌手知道$x \in L$,但没有相关的NP证据)没有任何规定,不适合本文的应用,文献[1]也指出此种基于“知识”的安全性定义更加难以处理,是下一步值得研究的方向,因此为WE引入新的增强的安全性定义。
定义4 增强的WE除了要满足原来的正确性、公正性之外,还要满足第三个安全性质--特别公正性(special soundness):即使敌手A知道$x \in L$,但他没有相关的NP证据w,那么加密对他来说仍然是语义安全的,即:
$$ \begin{array}{c} |\Pr [A({\rm{ENC}}({1^\lambda }, x, {m_0})) = 1|x \in L] - \Pr [A({\rm{ENC}}\\ ({1^\lambda }, x, {m_1})) = 1|x \in L]| < {\rm{negligible}}(\lambda ) \end{array} $$ (5) 下面基于原来的WE方案和子集成员分辨难题(hard subset membership problem, HSMP)来构建一个满足特别公正性的方案。
所用的NP语言L为一个HSMP问题,如DDH[10]、DLIN[11]或任一个矩阵DH[12]等,为简单起见,下面的叙述以DDH为例,其他的HSMP问题也一样可以。
著名的DDH问题就是要把元组$({g^r}, {h^r})$和$({g^{{r_1}}}, {h^{{r_2}}}:{r_1} \ne {r_2})$分辨开来,NP语言是$L = \{ (G, H):{\log _g}G = {\log _h}H = r\} $,NP证据是r;此语言的一个实例是两个群元素$x = (G, H)$,增强的WE构建是利用原来的WE方案,并用此DDH语言作为所用的NP语言来加密消息。
WE. setup:把上述的DDH问题规约到一个子集精确覆盖(exact cover)问题,因为精确覆盖问题是一NP完全问题,此种规约一定存在,然后用原WE方案进行加解密操作;
WE.ENC:前面所得的精确覆盖问题x,即若干子集Ti和全集[n],对于给定的消息M,随机选择n个数$({a_1}, {a_2}, \cdots, {a_n})$,计算$C = Mg_n^{{a_1}{a_2} \cdots {a_n}}$,此外对每个子集Ti生成${C_i} = g_{|{T_i}|}^{\prod\nolimits_{i \in {T_i}} {{a_i}} }$,最后输出密文${\rm{CT}} = (C, {C_1}, {C_2}, \cdots, {C_l})$;
WE.DEC:如果$x \in L$且w是相应的NP证据,即$w \subset [l] \wedge \bigcup\limits_{i \in w} {{T_i}} = [n]$,那么可由$({C_1}, {C_2}, \cdots, {C_l})$利用多线性映射得到$g_n^{{a_1}{a_2} \cdots {a_n}}$:
$$ e({C_{{i_1}}}, {C_{{i_2}}}, \cdots, {C_{{i_{|w|}}}}) = g_n^{{a_1}{a_1} \cdots {a_n}}, {i_j} \in w $$ (6) 由$g_n^{{a_1}{a_2} \cdots {a_n}}$可简单地从C中解密出原消息M。
下面证明此简单的构建就能满足上述的WE的增强的“特别公正性”。
定理1 上述的基于DDH语言的WE方案除了满足原来的WE安全性之外,如果DDH假设成立,那么还满足增强的特别公正性。
证明:1)正确性
如果$x = (G{\rm{, }}H) \in L$,且解密者知道相应的NP证据r,那么基于原WE方案的正确性解密者就能正确解密得到消息;
2)公正性
如果$x = (G{\rm{, }}H) \notin L$,那么基于原WE方案的公正性,对任何敌手来说密文是语义安全的;
3)特别公正性
新的情况是如果$x = (G{\rm{, }}H) \in L$,但解密者没有相关的NP证据r,下面证明此时密文对他来说仍是语义安全的(如果DDH假设成立)。
假设存在敌手A此时能打破密文的语义安全性,证明利用此敌手A就能攻破DDH假设,归约方法如下:
给定两个群元素${\rm{(}}G{\rm{, }}H{\rm{)}}$,要判定其是否为DDH元组,只要利用此元组作为一个NP语言实例x来加密从m0、m1中随机选择的消息mb,然后将密文发给敌手A,那么基于A猜测的正确性,就能知道${\rm{(}}G{\rm{, }}H{\rm{)}}$是否为DDH元组。如果A的猜测是正确的,那么${\rm{(}}G{\rm{, }}H{\rm{)}}$是DDH元组,因为此时恰为$x = (G{\rm{, }}H) \in L$而A没有相应NP证据的情况,根据A的定义他猜测正确的概率较大;如果A的猜测是错误的,那么显然$x = (G{\rm{, }}H) \notin L$,因为此时根据原来的WE方案的安全性(即$x \notin L$的情况),任何人都不能打破密文的语义安全性。
上述构建的一个缺陷是通常HSMP问题都不是NP完全问题(如DDH、DLIN等),而理论上不能把任一NP问题都归结为HSMP问题,这就制约了WE的许多应用。实现针对一个NP完全问题的具有特殊公正性的WE方案是一个有趣的公开问题。
对上述构建进行扩展,使其能直接用于构建BE方案。所用的NP语言是基于ROM模型[13]的一个签名方案(或称为Fiat-Shamir转换[14],把交互式零知识证明系统转换为非交互式知识签名(signature of proof of knowledge, SPK)[15])。该签名方案的公钥$(G{\rm{, }}H) = ({g^r}, {h^r})$,签名${\rm{SPK}}\{ r:(G{\rm{, }}H) = ({g^r}, {h^r})\} (m)$,实现方法如下:
给定要签名的消息m,随机选择k生成$(G{\rm{, }}H) = ({g^k}, {h^k})$,设置$c = {\rm{Hash}}(G', H', m)$,其中Hash是散列函数被假设为一个随机预言器(random oracle),再令$s = k - cr$,$(G'{\rm{, }}H', s)$即为签名,要验证此签名,只要检查$G' = {g^s}{G^c}$和$H' = {h^s}{H^c}$是否成立,这里$c = H(G', H', m)$。
NP语言L为:$L = \{ (G, H), (m, \delta ):{\rm{Verify}}(m, \delta ) = 1\} $,m是任一消息,而NP证据就是针对公钥$(G{\rm{, }}H)$的合法消息/签名对$(m, \delta )$;但如果$(G{\rm{, }}H)$不是DDH元组,那么对任何不能控制随机预言器的敌手来说这样的NP证据是不存在的(基于零知识证明系统的安全性质)。
此扩展的WE方案满足特别公正性的证明基本上同定理1的证明是相同的,即如果存在打破特别公正性的敌手,那么能利用敌手来攻破DDH假设。
-
下面基于增强的WE方案来构建可撤销的BE方案:
1) KeyGen:生成上述基于SPK签名方案的PK/SK作为MPK/MSK,即公钥$(G{\rm{, }}H) = ({g^r}, {h^r})$,私钥为r,初始时将撤销列表RL设置为空,即没有用户被撤销。
2) UserKeyGen (ID):对名为ID的用户颁发证书为ID的签名,即$\delta = {\rm{Sig}}{{\rm{n}}_{{\rm{MSK}}}}({\rm{ID}})$,用户可以检查其证书是否合法,即${\rm{Verify}}({\rm{ID}}, \delta ) = 1$是否成立。
3) ENC (m):对消息m进行加密是用前述的WE方案加密得到的密文CT,所用的NP语言L为:
$$ \{ {\rm{MPK}}:\exists ({\rm{ID}}, \delta ), {\rm{Verif}}{{\rm{y}}_{{\rm{MPK}}}}({\rm{ID}}, \delta ) = 1 \wedge {\rm{ID}} \notin {\rm{RL}}\} $$ (7) 针对验证公钥MPK存在一合法的消息/签名对$({\rm{ID}}, \delta )$,其中消息ID不在撤销列表RL中(RL开始为空,每撤销一个用户就把其ID加入RL中去)。
4) DEC (CT):对于合法的用户其拥有合法的消息/签名对$({\rm{ID}}, \delta )$,且其ID不在RL中,也即其拥有针对上述NP语言合法的NP证据,则显然可以利用WE方案的解密算法对密文CT进行解密得到消息m;对于非法的用户,其没有消息/签名对,或者其ID已在RL中,都没有合法的NP证据,也就不能对用WE方案加密的密文进行解密。
5) Revo:撤销某用户时,只要将其ID加入到RL中,同时也要更新此后要发广播消息时用的NP语言L,在L中要使用最新的撤销列表,来排除刚撤销的用户。
6) Re-join:假如RL中某被撤销用户要重新加入(如用户缴清欠费等),系统管理员只要从RL中将其ID删除即可。
-
上述BE和WE方案构建中,由于要把DDH语言的实例规约为NP完全问题--精确覆盖问题,这种规约通常效率较低,所以本文提出的基于WE的BE方案是理论上的方案构建,还不能够应用于实际;目前已有一些高效的BE方案:如文献[16]中提出的基于多线性映射的高效BE方案,实现了密文大小、公私钥大小等都比较短(对数级大小)、而且也支持基于身份的BE;因此本文BE方案更大意义的在于理论价值:提出了WE的另一个应用--BE的构建,进一步拓展了WE方案的应用领域,未来如果出现高效直接的WE方案构建,本文的理论方案就可应用于实际。
Construction of Revocable Broadcast Encryption Based on Witness Encryption
-
摘要: NP(non-deterministic polynomial)证据加密(witness encryption,WE)是近来提出的一种新型的没有密钥生成过程的加密方案,可以用来构建许多其他的密码系统如公开密钥加密、IBE(identity based encryption)、ABE(attribute based encryption)等。该文提出WE的一种新应用:用WE构建可撤销广播加密系统,并且所构建的广播加密方案能支持简单的成员重加入功能(如付费电视);在构建的过程中指出以前的WE安全性定义不够严格,对原WE安全性定义进行了增强,并基于原WE方案和子集成员分辨难题、ROM(random oracle model)模型提出了一个新方案。Abstract: 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.
-
[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. http://www.docin.com/p-1405378144.html [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 in Cryptology-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. http://www.oalib.com/references/18244479 [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.
计量
- 文章访问数: 5429
- HTML全文浏览量: 1560
- PDF下载量: 113
- 被引次数: 0