基于国密SM9的匿名标识广播加密方案

潘 璇 严 芬

(扬州大学信息工程学院 江苏扬州 225127)

Fait等人[1]于1993年提出了广播加密(broadcast encryption)的概念,并给出了具体方案.该方案可以根据选定的多个接收方加密数据,在公开信道广播后,只有预先选定的接收者,即接收者得到合法授权后方可正确解密,且非法接收者无法通过合谋获取加密内容.广播加密是一种1对多的加密技术,可以有效地减少数据交流过程中的计算成本和通信负载.另一种相似的概念是由Beak等人[2]在2005年提出的多接收方加密,加密在1组接收者标识而不是单一标识上进行,本文将其和广播加密视为相同的概念.

标识密码(identity-based cryptosystem)是密码学中的另一个重要研究领域,此概念在1984年由Shamir[3]首次提出.标识密码以接收者的唯一信息作为公钥,取代传统公钥加密中证书的功能.2001年,Boneh等人[4]提出了第1个可证明安全的标识加密(identity-based encryption, IBE)方案.

标识广播加密(identity-based broadcast encryption, IBBE)的概念在2007年由Delerablée[5]与Sakai等人[6]分别提出,将广播加密与标识加密相结合,避免了耗费大量资源的证书管理工作.随后,对照传统的广播加密,针对IBBE的研究逐渐深入,其功能性和安全性得以不断完善.

在现实应用中,数据的合法接收者通常并不愿意将其身份暴露给其他接收者.因此在2001年,Bellare等人[7]首次提出了加密方案中的匿名概念.而在一般的IBBE方案中,往往将合法接收者的身份作为广播数据的一部分对所有接收者广播,所以并不具备匿名性.因此,对于IBBE方案的匿名性也有诸多研究[8-18].在2016年,He等人[16]提出了一种通用匿名IBBE方案,方案可以利用满足安全条件的IBE方案构造出具备抵御适应性选择密文攻击(adaptively chosen ciphertext attacks, CCA2)的不可区分性和匿名性的IBBE方案,相较于抵御选择明文攻击(chosen plaintext attacks, CPA)的CPA安全,CCA2安全能够有效应对攻击者的主动攻击.这也是首个基于非对称双线性群的CCA2安全的不可区分性和匿名性的IBBE方案,但在文献[18]中被证明不具备内部匿名性.

2020年1月1日,《中华人民共和国密码法》正式开始施行,其支持我国商用密码算法的自主可控,鼓励从业单位采用商用密码推荐性国家标准、行业标准,提升商用密码的防护能力.而我国在2008年自主设计了标识密码SM9,2016年成为我国密码行业标准[19],并在2020年正式成为我国的国家标准.之后,SM9各部分也陆续成为国际标准,并在2021年全体系纳入ISO/IEC标准.

目前,基于国密SM9的研究有诸多成果.其中,赖建昌等人[20]借鉴Delerablée[5]的方案,在2021年首次设计出基于SM9标识加密算法的高效IBBE方案,并给出IND-sID-CPA安全性分析.但目前为止,仍缺失基于SM9标识加密算法的匿名IBBE方案的研究.

1 基础知识

1.1 双线性群

双线性群可以用五元组(N,G1,G2,GT,e)描述,其中N是1个大质数,G1,G2,GT均是阶为N的乘法循环群(在基于椭圆曲线的双线性群构造中G1,G2是加法群,本文方案的设计与分析均以加法群表示),e为双线性映射e:G1×G2→GT.如果G1=G2,则为对称双线性群,否则为非对称双线性群.令g,g′分别为G1,G2的生成元,满足以下3个性质:

1) 双线性(bilinearity).对于任意的P∈G1,Q∈G2,a,b∈N,有e(aP,bQ)=e(P,Q)ab.

2) 非退化性(non-degeneracy).满足e(g,g′)≠1.

3) 可计算性(efficiency).对于任意的P∈G1,Q∈G2,存在多项式时间算法,可以高效地计算e(P,Q).

SM9标识密码算法使用非对称双线性群,且存在同态映射ψ:G2→G1,使得ψ(g′)=g.

1.2 困难性假设

以下假设均定义在双线性群(N,G1,G2,GT,e)上,设g,g′分别是G1,G2的生成元(关于假设2,3,4的详细内容可参见文献[21]).

假设1.ADBDH(asymmetric decision bilinear Diffie-Hellman)假设:对于随机选择的a,b,c∈和Z∈GT,给定元组(g,ag,cg,g′,ag′,bg′,Z),判断Z是否等于e(g,g′)abc是困难的.

假设2.τ-BCA1(bilinear collision attack)假设:对于正整数τ和随机选择的α∈给定元组其中hi∈且是随机选取),计算e(g,g′)α/(h0+α)是困难的.

假设3.DBIDH(decision bilinear inversion Diffie-Hellman)假设:对于随机选择的a,b∈和Z∈GT,给定元组(g,g′,ag,bg,Z),判断Z是否等于e(g,g′)a/b是困难的.

假设4.Gap-τ-BCA1假设:对于正整数τ和随机选择的α∈给定元组其中hi∈且是随机选取)和1个可以解决1个给定DBIDH问题的DBIDH谕言机,计算e(g,g′)α/(h0+α)是困难的.

1.3 标识广播加密

IBBE方案可以用算法元组(Setup,KeyGen,Encrypt,Decrypt)描述,方案需引入密钥生成中心(key generation center, KGC).由于本文方案采用混合加密方案,所以数据封装机制(data encapsulation mechanism, DEM)可以选用ISO/IEC18033-2中的DEM2或DEM3等方案,本文只进行简要描述,不重点讨论.(Setup,KeyGen,Encrypt,Decrypt)的具体细节描述如下:

1)Setup(1λ).算法由KGC执行.以系统安全参数λ为输入,输出系统主公钥mpk和主私钥msk.mpk作为主公钥,其整体或部分均可以隐性地作为其他算法的输入参数.

2)KeyGen(msk,ID).算法由KGC执行.以msk和接收者标识ID为输入,输出接收者标识ID所对应的私钥skID.

3)Encrypt(S,M).算法由加密者执行.以接收者标识集合S=(ID1,ID2,…,IDs)和明文消息M为输入.首先生成封装密文C和对称密钥K.加密方以K作为加密算法DEM.Enc的密钥生成密文CM,广播(C,CM).

4)Decrypt(C,CM,skID).算法由解密者执行.输入C,CM以及对应的skID.如果解密成功输出K,否则输出错误符号⊥.如果输出的是K,接收者可以利用K和DEM的解密算DEM.Dec解密CM.

IBBE方案的正确性要求:对于任意的(mpk,msk)←Setup(1λ),skID←KeyGen(msk,ID),(C,K)←Encrypt(S).当ID∈S时,Decrypt(C,skID)=K.

1.4 安全模型

本节所述的安全模型主要针对密钥封装机制(key encapsulation mechanism, KEM).

1.4.1 IND-nID-CCA2不可区分性安全模型

初始化:攻击者A给出欲攻击的接收者标识集合S*的大小s.

系统建立:挑战者C运行Setup算法,然后,发送mpk给攻击者A并秘密保存msk.

询问1:攻击者A适应性地向挑战者C询问以下问题.

私钥询问:输入ID,挑战者C运行KeyGen算法返回skID给攻击者A.

解密询问:输入ID和C,挑战者C运行KeyGen算法获得skID,而后运行Decrypt算法返回解密结果给攻击者A.

挑战:攻击者A确定询问1结束后,任意选择欲攻击的接收者标识集合S*,要求|S*|=s,且攻击者A没有在询问1阶段中对标识ID∈S*进行私钥询问.挑战者C利用Encrypt算法生成挑战密文C*和对称密钥K,同时挑战者C从密钥空间中随机另选1个密钥K′,选择1个比特μ∈{0,1},设Kμ=K,所选随机密钥为K1-μ,最后将(C*,K0,K1)发送给攻击者A.

询问2:与询问1类似,但私钥询问和解密询问不得涉及挑战阶段中的ID∈S*和C*.

猜测:攻击者A输出对μ的猜测.

定义攻击者A的优势为

(1)

在模型的初始化阶段若需指定具体欲攻击的接收者标识集合,则为选择身份安全模型,记作IND-sID-CCA2.若无初始化阶段,则为完全安全模型,记作IND-ID-CCA2.若在询问2阶段无解密询问,则为选择密文模型,记作IND-nID-CCA1.若在询问1,2阶段均无解密询问,则为选择明文模型,记作IND-nID-CPA.匿名性安全模型的相关概念与上述类似,后续不再赘述.

1.4.2 ANO-ID-CCA2匿名性安全模型

系统建立:与IND-nID-CCA2安全模型类似.

询问1:与IND-nID-CCA2安全模型类似.

挑战:攻击者A确定询问1结束后,任意选择欲攻击的接收者标识集合S0和S1给挑战者C.要求|S0|=|S1|,且攻击者A没有以ID∈(S0∪S1-S0∩S1)在询问1中发起过私钥询问.然后,挑战者C随机选择1个比特μ∈{0,1},利用Sμ和Encrypt算法返回挑战密文C*给攻击者A.

询问2:与询问1类似,但不得对ID∈(S0∪S1-S0∩S1)进行私钥询问和以ID∈(S0∪S1-S0∩S1)对挑战密文C*进行解密询问.

猜测:攻击者A输出对μ的猜测.

定义攻击者A的优势为

(2)

2 具体方案

本节所使用的符号借鉴于国密SM9标准文档.对于数据类型间的转换,可以按照国家标准GB/T38635.1—2020中7.2节给出的方法进行.设1个强一次性签名方案为Σ=(Gen,Sig,Ver).具体方案如下:

1)Setup(1λ).首先,生成双线性群(N,G1,G2,GT,e),随机选择生成元g∈G1,g′∈G2,随机选择α,β∈计算g1=αg,g2=βg,g3=e(g2,g′).选择哈希函数H1:{0,1}*→G2,H2:GT→{0,1}n,H3:{0,1}*→和用1B表示的加密私钥生成函数识别符hid.选择密钥派生函数KDF:{0,1}*→klen,其中klen是封装的对称密钥的长度.设置主公钥mpk=(G1,G2,GT,e,g,g1,g2,g3,g′,H1,H2,H3,hid,KDF),主密钥msk=(α,β).

3)Encrypt(S,M).首先,生成1个签名密钥对(svk,ssk)←Gen(1λ).然后,随机选择r∈计算T=rg.对于每个ID∈S,计算H1(ID))r).随机选择r′∈令q=H3(ID‖hid,N)g+g2,计算设计算生成密文C=(svk,T,C1,σ),其中σ=Sig(ssk,T‖C1).最后,计算K=KDF(C‖w,klen),如果K为全0比特串,则重新计算.以K作为对称密钥加密明文得到密文CM=DEM.Enc(K,M).

3 安全性分析

3.1 IND-nID-CCA2安全性分析

定理1.如果H3,KDF是随机谕言机,Gap-τ-BCA1假设成立,那么本文所构造的基于国密SM9的匿名IBBE方案是IND-nID-CCA2安全的.

证明.设攻击者A欲攻击的接收者标识集合为S*且|S*|=s.首先给出2个游戏,并证明Game0和Game1在计算上无法区分.

Game0:按照IND-nID-CCA2安全模型进行.

Game1:与Game0相同,但是挑战者在挑战阶段后拒绝所有对含有相同验证密钥svk*的(ID,C)解密询问.

引理1.如果签名方案Σ是一个强一次性签名方案,那么Game0和Game1在计算上无法区分.

系统建立:对挑战者C给定1个验证密钥svk*,然后运行Setup算法生成(mpk,msk).而后,将mpk返回给A,秘密保存msk.

询问1:攻击者A可以适应性地发出私钥询问和解密询问.挑战者C利用msk进行回复.

询问2:攻击者A继续适应性地发起如下询问.

私钥询问:与询问1阶段类似,但所询问的ID∉S*.

猜测:攻击者A输出1个猜测μ′∈{0,1}.

可以观察到,当事件F不发生时,Game1和Game0是相同的.如果事件F以一个不可忽略的概率发生,那么挑战者C就可以以一个不可忽略的优势对有效签名进行伪造.由于签名方案Σ是一个强一次性签名方案,因此事件F发生的概率可以忽略.因此,Game0和Game1在计算上是无法区分的.

证毕.

由于Game0和Game1在计算上无法区分,所以关于加密方案的安全性分析,即定理1的证明在Game1上进行.如果存在1个攻击者A能够以一个不可忽略的优势ε(λ)取得IND-nID-CCA2安全模型的胜利,攻击期间进行了q1+1次H3询问、q2次KDF询问、qD次解密询问.那么,易构造1个多项式时间算法C作为挑战者,其可以利用攻击者A解决Gap-τ-BCA1问题.

系统建立:挑战者C生成主公钥mpk=(G1,G2,GT,e,g,g1,xg,e(xg,g′),g′,H1,H2,H3,hid,KDF),主私钥msk=(α,x),将mpk返回给A,秘密保存msk.随机谕言机H3和KDF由挑战者C控制.挑战者C随机选择s个互不相同的Ii(1≤Ii≤q1+1,i∈{1,2,…,s}).

KDF询问:输入(C,w),挑战者C维护1个列表KDF.list={(C,w,K)},当攻击者A以(Ci,wi)发起询问时,挑战者C按如下方式回复.

如果KDF.list中存在(Ci,wi,Ki),则挑战者C回复Ki.否则,首先解析Ci=(svki,Ti,C1,i,σi)并验证.

如果Ver(svki,Ti‖C1,i,σi)=0,挑战者C在对称密钥空间中随机选择Ki,将(Ci,wi,Ki)加入KDF.list,回复Ki.

询问1:攻击者A适应性地发起如下询问.

解密询问:挑战者C维护1个列表Dec.list={(C,K)},当攻击者A以(IDi,Ci)发起询问时,挑战者C按如下方式回复.

首先解析Ci=(svki,Ti,C1,i,σi)并验证.如果Ver(svki,Ti‖C1,i,σi)=0,则挑战者C回复⊥.

询问2:首先解析Ci=(svki,Ti,C1,i,σi),如果svki=svk*,挑战者C回复⊥.后续操作与询问1阶段类似,其中中止游戏的事件已经包含安全模型对询问2的限制.

猜测:攻击者A输出1个猜测μ′∈{0,1}.一旦攻击者A输出其猜测,挑战者C按如下方式回答Gap-τ-BCA1问题.

Pr[μ′=μ]=Pr[μ′=μ|E3]Pr[E3]+

Pr[μ′=μ]≥Pr[μ′=μ|E3]Pr[E3]=

因此,定理1成立.

证毕.

3.2 ANO-ID-CCA2安全性分析

定理2.如果H1,H2是随机谕言机,ADBDH和Gap-τ-BCA1假设成立,那么本文所构造的基于国密SM9的匿名IBBE方案是ANO-ID-CCA2安全的.

证明.证明的方式通过一系列的游戏进行.不失一般性,假设接收者标识集合S0和S1中只有1个标识ID不同且|S0|=|S1|=s.记{ID|ID∈Si∩ID∉Sj}=SiSj,IDυ为S0S1的唯一元素,IDω为S1S0的唯一元素.

Game1:与Game0相同,但是挑战者在挑战阶段后拒绝所有对含有相同验证密钥svk*的(ID,C)的解密询问.

Game5:与Game4相同,但挑战者在挑战阶段后不拒绝对(ID,C)的解密询问,其中C包含相同的验证密钥svk*.此时,C*是在S1上加密产生的.

下文利用几个引理,证明上文所述的游戏相邻之间在计算上无法区分.通过游戏间传递性,可得Game0和Game5在计算上无法区分.Game0中的C*是在S0上加密产生,Game5中的C*是在S1上加密产生的.根据ANO-ID-CCA2安全模型,可知基于国密SM9的匿名IBBE方案是ANO-ID-CCA2安全的.

引理2.如果签名方案Σ是一个强一次性签名方案,那么Game0和Game1在计算上无法区分.

与引理1证明类似.

引理3.如果ADBDH假设成立,那么Game1和Game2在计算上无法区分.

证明.如果存在1个攻击者A能够以一个不可忽略的优势区分Game1和Game2.那么,易构造1个多项式时间算法C作为挑战者,其可以利用攻击者A解决ADBDH问题.给定1个ADBDH问题实例(g,ag,cg,g′,ag′,bg′,Z).

系统建立:挑战者C生成主公钥mpk=(G1,G2,GT,e,g,g1=ag,g2,g3,g′,H1,H2,H3,hid,KDF),主私钥msk=(a,β),将mpk返回给A,秘密保存msk.选择随机谕言机H1,H2由挑战者C控制.

H1询问:挑战者C维护1个列表H1.list={(ID,Q,q,ϖ)}.输入标识IDi,当IDi存在于H1.list中时,返回Q,否则随机选择ϖ∈{0,1}和q∈如果ϖ=0,计算Q=qg′,否则计算Q=bqg′,更新H1.list.挑战者C将Q返回给攻击者A.

H2询问:挑战者C维护1个列表H2.list={(X,v)}.输入Xi,当Xi存在于H2.list中时,返回v,否则随机选择v←{0,1}n,更新H2.list.挑战者C将v返回给攻击者A.

挑战者C维护1个列表List={(C,K)},每当挑战者C生成密文C时,同时生成对称密钥K,并以此更新List列表.

询问1:攻击者A适应性地发起如下询问.

询问2:攻击者A继续适应性地发起如下询问.

私钥询问:与询问1阶段类似,但所询问的ID∉{IDυ,IDω}.

解密询问:对(ID,C)进行解密询问,但不能以ID∈{IDυ,IDω}对挑战密文C*进行解密询问.挑战者C解析C=(svk,T,C1,σ).如果svk=svk*挑战者C输出⊥,否则挑战者C按照询问1阶段回复攻击者A.

猜测:攻击者A输出1个猜测μ′∈{0,1}.

容易观察出,当Z=e(g,g′)abc时,是对Game1适当的模拟,否则是对Game2适当的模拟.因此,如果攻击者A能够以一个不可忽视的优势区分Game1和Game2,那么挑战者C也能以一个不可忽视的优势解决ADBDH问题,违背了ADBDH假设.因此,Game1和Game2在计算上无法区分.

证毕.

引理4.如果Gap-τ-BCA1假设成立,那么Game2和Game3是在计算上无法区分的.

系统建立:与定理1证明类似.但挑战者C随机选择互不相同的I1和I2(1≤Ii≤q1+1,i∈{1,2}).

KDF询问:与定理1证明类似.

询问1:与定理1证明类似.

询问2:与定理1证明类似.

猜测:攻击者A输出1个猜测μ′∈{0,1}.一旦攻击者A输出其猜测,挑战者C按如下方式回答Gap-τ-BCA1问题.

容易观察出,当C*是在S0上加密时,是对Game2适当的模拟,否则是对Game3适当的模拟.因此,如果攻击者A能够以一个不可忽视的优势区分Game2和Game3,那么挑战者C也可以以一个不可忽视的优势解决1个Gap-τ-BCA1问题,违背了Gap-τ-BCA1假设.因此,Game2和Game3在计算上无法区分.

证毕.

引理5.如果ADBDH假设成立,那么Game3和Game4是在计算上无法区分的.

与引理3证明类似.

引理6.假设签名方案Σ是一个强一次性签名方案,那么Game4和Game5在计算上无法区分.

与引理2证明类似.

4 性能分析

在本节,将本文所设计的基于国密SM9的匿名IBBE方案与现有方案在通信成本、计算成本和特性上进行比较.为方便比较,当有明文数据需要发送时,首先加密1个对称密钥并广播,然后利用对称密钥加密明文数据.接收者需要首先解密获得对称密钥,利用对称密钥解密获得数据.比较中使用的符号与数值借鉴自文献[18],具体如表1所示.为方便计算,将合法接收者数目(即方案中接收者标识集合的大小)s设置为100,将文献[5,20,22]需要的最大接收者数目m设置为100,将本文方案中所使用的签名方案设置为SM9标识签名.

表1 文中使用符号

1) 通信成本对比.通过表2可以看出,文献[10,13,18]方案和本文方案的主公钥长度、主私钥长度、私钥长度为O(1),大小恒定,密文长度为O(s),会随着合法接收者数目的增大而增大.与之相比,文献[5,20,22]方案的主密钥长度为O(m),会随着最大接收者数目的增大而增大,虽然密文长度为O(1),但并不具备匿名性.

表2 通信成本对比 b

2) 计算成本对比.在计算成本的对比中,主要考虑一些重量级操作的计算成本,如群G1,G2,GT中的标量计算和双线性配对,忽视一些轻量级操作的计算成本,如哈希函数和对称加密.由于参与对比的所有方案均基于双线性群,而双线性群的生成可以提前完成,所以这部分的计算成本也忽略.通过表3可以看出,本文方案的主公钥生成、私钥生成、解密计算成本为O(1),大小恒定,加密计算成本为O(s),文献[10,13]方案和本文方案相似.而文献[5,20,22]方案的主公钥生成成本为O(m),文献[5,18,20,22]方案的加解密计算成本均为O(s).

3) 特性对比.从表4可以看出,对于方案的不可区分性,本文方案是IND-nID-CCA2安全,除了可以有效应对攻击者的主动攻击外,在安全模型中的初始化阶段仅需指定欲攻击的接收者标识集合的大小,而不需要像文献[5,10,13,20,22]方案指定具体的接收者标识集合.而文献[18]方案的不可区分性是完全安全,安全性更优.对于方案的匿名性,本文方案为ANO-ID-CCA2安全且具备内部匿名性,优于文献[5,10,13,20,22]方案.由于文献[5,10,13,20,22]方案和本文方案在安全性分析中均使用了随机谕言机,因此方案的安全模型是随机谕言模型,弱于文献[18]方案所使用的不含随机谕言机的标准模型.本文方案基于非对称双线性群,较之对称双线性群,安全性更高.最后,文献[20]方案和本文方案均基于国密SM9标识加密算法,有助于我国密码技术的自主可控.

表4 特性对比

综上所述,本文方案在通信成本和计算成本的表现上均较为优越,具备一定的理想特性,主公钥、主私钥、私钥的长度与计算成本恒定,解密计算成本恒定.本文方案在安全性上仅略弱于文献[18]方案,但文献[18]方案并未基于国密SM9标识加密算法,难以与基于国密SM9标识加密算法的系统相融合.

5 结 语

本文基于国密SM9标识加密算法,利用非对称双线性对构造了一种匿名IBBE方案,为我国密码技术自主可控作出了一定贡献.本文方案满足随机谕言模型下IND-nID-CCA2安全和ANO-ID-CCA2安全,并通过形式化安全性分析,对方案的IND-nID-CCA2安全和ANO-ID-CCA2安全进行了证明.并且在与现有方案的对比中,本文方案表现出了一定的理想特性和较好的安全性.在未来工作中,将针对本文方案的安全性和密文长度进行优化.后续也将在IBBE方案的国产化、功能性、安全性等方面继续研究探索.