公钥广播加密研究综述

崔 岩,黄欣沂,赖建昌,宁建廷

(1. 福建师范大学 计算机与网络空间安全学院,福建 福州 350117；2. 香港科技大学(广州),广东 广州 511400;3. 东南大学 网络空间安全学院,江苏 南京 211189)

广播加密的概念由Fiat等[1]提出，假设Alice想要向大量接收者发送相同的消息，若采用多次执行加密算法并将密文依次发送给接收者的方法，虽然可实现一对多加密，但加密和解密的计算代价高昂且通信代价随着接收者的数量增加而线性增加。随着付费直播、数字产品、在线会议的迅速发展，点对点的加密方式已经逐渐不能满足互联网环境的通信需求，亟需一对多或多对多的安全通信方式。

广播加密是一种支持在不安全的公开信道上实现多用户数据安全共享的加密技术，适用于一对多安全传输场景。广播加密的工作方式为：数据拥有者首先选取一组接收者，运行广播加密算法，将加密得到的密文发布到公开信道，监听该信道的所有用户均可获取密文，但只有授权用户可利用解密密钥正确解密，未授权用户不能从密文中获取任何明文信息。广播加密在付费电视、数字版权保护及区块链等领域广泛使用。

根据加密和解密过程中密钥的不同，广播加密可分为对称广播加密和公钥广播加密。在对称广播加密中，广播者只能是可信机构，该机构负责生成并分发已授权用户的解密密钥，因此，对称广播加密在实际应用中局限性较大，应用范围窄。公钥广播加密允许系统内任意用户作为数据拥有者，且数据拥有者可指定任意系统内一个用户集合作为数据接收者，只有集合内的用户可以解密。由于系统中任意用户均可作为发送者运行加密算法，更具一般性且灵活。因此，公钥广播加密具有更加广泛的应用，得到了专家学者的广泛关注和研究。

公钥广播加密为多用户数据安全共享的典型方法技术，其研究方向主要可概括为2个方向：

(1)根据广播加密的应用场景需求不同或功能不同，可分为标识广播加密、匿名广播加密、叛逆者追踪广播加密，以及可撤销广播加密等；

(2)从算法本身对广播加密方案进行优化，可分为2类：①对算法安全性的研究，例如选择密文攻击、自适应安全性等；②对算法效率的研究，包括加密和解密算法的时间复杂度、公共参数大小、私钥长度以及密文长度等。

评估广播加密方案的优劣通常从方案满足的安全属性、方案的计算和通信代价进行分析。一个健壮的广播加密系统应满足如下安全属性：

(1)权限控制：系统用户的添加或删除由可信中心执行，用户的解密权限由加密者(数据拥有者)决定。

(2)抗合谋攻击：任何数量的非授权接收者即使合谋都无法解密获取加密数据的内容。

(3)接收者无状态：在系统的整个生命周期内接收者无需改变自己的设置，解密操作只能按照系统初始设置进行。

Wong等[2]于2000年基于逻辑层次树结构提出了组播密钥管理方案，该方案也称为有状态广播加密。在该系统中，接收者需利用接收到的组密钥解密广播密文。若组内成员发生变化，即有成员新加入系统或离开系统，为保证系统安全性，所有用户的组密钥必须更新；若利用该方案实现无状态广播加密，则通信代价和计算开销极高，且可信中心知道每个接收者的信息，无法实现匿名等功能，灵活性较差。因此，本文不考虑该类型的广播加密。

另一种广播加密称为静态广播加密[3]，该机制需要在系统建立阶段确定接收者集合，每个用户的私钥生成都与其他所有授权接收者的公钥相关，应用场景较为有限，本文同样不考虑该类型的广播加密。

本文着重关注近年来公钥广播加密的研究进展，阐述了公钥广播加密的研究历史、形式化定义和典型构造，旨在推动广播加密的研究与发展。

1 基于PKI的广播加密

一对多加密传输最早由Berkovits[4]提出，在文献[4]中，利用拉格朗日插值，可将任意秘密分享方案转换成秘密广播方案。随后Fiat等[1]在1993年提出“广播加密”的概念并给出了广播加密的形式化定义和安全模型，同时给出了对称广播加密方案的具体构造。

然而由于对称广播加密的局限性较大，近年来对广播加密的研究主要围绕公钥广播加密展开。公钥广播加密(Public Key Broadcast Encryption,PKBE)的概念由Naor等[5]首次提出，传统公钥广播加密方案通常为基于证书的密码方案，为确保用户公钥的真实有效性，公钥基础设施(Public Key Infrastructure,PKI)应运而生。PKI中通常包含一个证书认证机构(Certificate Authority,CA)，负责为用户签发证书。文献[5]中的方案利用门限秘密共享技术，实现了有效叛逆者追踪，最多撤销t个用户的解密权限，满足t-抗合谋攻击的安全性。

1.1 公钥广播加密定义

公钥广播加密包括3个过程：

(1)Setup(λ,n):输入安全参数λ，广播接收者人数n，输出n个私钥k1,k2,…,kn和一个公钥PK。

(2)Encrypt (S,PK):以授权接收者集合S∈{1,2,…,n}和公钥PK为输入，输出二元组(Hdr,K)，其中，Hdr称为首部；K为加密密钥，用于加密广播内容。已知广播消息为M，利用会话密钥K加密消息M得到密文CM，则整个广播内容为(S,Hdr,CM)，其中，(S,Hdr)通常称为广播头，CM称为广播体。

(3)Decrypt (S,i,ki,Hdr,PK):输入接收者集合S∈{1,2,…,n}，用户i和对应的私钥ki，首部Hdr和公钥PK。若i∈S，则算法可正确输出会话密钥K，进而解密CM得到消息M，否则不能获取明文信息。

基于PKI的广播加密的正确性要求对任意的消息M，(PK,(k1,…,kn))←Setup(λ,n)，(Hdr,K)←Encrypt(S,PK)。若i∈S，那么

Pr[Decrypt(S,i,ki,Hdr,PK)=M]=1。

1.2 公钥广播加密安全模型

在广播加密的安全模型中，根据敌手的攻击能力不同可将敌手分为自适应敌手和静态敌手。静态敌手要求在发起攻击之前给出要攻击的接收者集合。显然，自适应敌手具有更强的攻击能力，敌手无需在攻击前选取待攻击的接收者集合。因此，自适应敌手模型比静态敌手模型安全性更强。

广播加密最基本的要求是保证数据的机密性，即非授权用户不能获取任何明文信息。针对数据的机密性，下面给出自适应选择密文攻击下的不可区分性(Indistinguishability against Adaptive Chosen-Ciphertext Attacks,IND-CCA)[6]，通过敌手和挑战者的交互游戏定义，安全模型定义如下：

(2)询问阶段1。敌手允许在该阶段自适应地发起如下询问：

a.私钥询问：敌手可自适应地询问集合中第u个位置的私钥，挑战者将ku发送给敌手；

b.解密询问：敌手可针对密文发起解密询问，询问的格式为 (u,S,Hdr)，挑战者运行算法Decrypt(S,u,ku,Hdr,PK)，将解密结果K返回给敌手。

(3)挑战阶段。敌手输出挑战接收者集合S*，要求敌手没有发起过对u∈S*的私钥询问。挑战者运行加密算法Encrypt(S*,PK)，输出二元组(Hdr*,K)。接着挑战者随机选取1比特b∈{0,1}，令Kb=K，从密钥空间中选取随机密钥K′∈K，令K1-b=K′，最后将(Hdr*,K0,K1)发送给敌手。

(4)询问阶段2。敌手可在该阶段继续发起私钥询问和解密询问，询问的限制是不能询问u∈S*的私钥，不能发起Hdr=Hdr*,S=S*的解密询问。挑战者的回复方式与询问阶段1相同。

(5)猜测。敌手输出猜测值b′∈{0,1}，若b=b′，则敌手获胜。

定义1(可忽略) 令||为自然数集合，对于任意d∈，若存在λd∈，使得对于任意λ>λd，ε(λ)≤λ-d始终成立，那么函数ε:→[0,1]称为可忽略函数。

定义2 如果对于任意的多项式时间(Probabilistic Polynomial Time,PPT)敌手，在上述游戏中获胜的优势是可忽略的，则称广播加密方案是IND-CCA安全的。

若在上述IND-CCA模型中，不允许敌手在询问阶段发起密钥询问，则相应的模型为IND-CPA模型。

广播加密与传统点对点的公钥加密在IND-CCA安全模型的不同点主要体现在：前者要求在系统建立阶段，挑战者需要将所有用户的公钥信息发送给敌手，敌手可在询问阶段自适应的发起密钥询问。在挑战阶段，敌手可根据已掌握的信息选取接收者集合进行攻击；后者在系统建立阶段只需要向敌手发送挑战用户的公钥信息即可。

1.3 公钥广播加密研究现状

在2002年，Dodis等[7]对基于对称密钥的广播加密和公钥广播加密展开进一步研究，将对称广播加密中的子集差分法(Subset Difference,SD)拓展到公钥体制广播加密，给出一种对称广播加密向公钥广播加密的转化关系，提出具有定长公钥的公钥广播加密方案。

2005年，Boneh等[6]利用双线性对技术提出首个完全抗合谋攻击(fully collusion resistant)的无状态公钥广播加密方案(简称BGW方案)，文献[6]中给出了两种PKBE构造方案，第一个构造中具有定长的密文长度，公钥长度和解密代价均随着接收者线性增长，能够抵抗选择明文攻击(Chosen Plaintext Attack,CPA)；第二个构造具有亚线性大小的密文长度和公钥长度。并利用相同的参数给出一种可抵抗选择密文攻击的方案。

Delerablée等[8]在2007年提出了动态广播加密的概念，在系统建立阶段用户总数不是固定的，系统参数的生成也无需用到接收者的公钥信息，新用户可随时加入广播系统，并获取之前公布的广播消息，且无需修改其他用户的私钥。该方案适用于付费电视等应用，当新用户想观看之前的直播回放时，即可利用自己的私钥解密。

Gentry等[9]在2009年提出具有抵抗自适应性选择明文攻击安全的广播加密方案，安全性基于判定性BDHE(Bilinear Diffie-Hellman Exponent)假设。文献[9]中引入半静态(semi-static)敌手模型的概念，在半静态模型中，敌手在系统建立阶段之前要提交一个集合S，在挑战阶段可以选取集合S的任意子集S′作为攻击目标。该模型比静态敌手模型具有更强的灵活性，在静态模型中敌手只能攻击集合S。

在2012年，Phan等[10]基于文献[6]的CPA方案，提出了一个定长密文的公钥广播加密方案，可抵抗静态选择密文敌手攻击，其公钥长度在BGW方案的基础上增加一个群元素。文献[10]还提出了一个具有撤销功能的广播加密方案，与第一个方案采用同样的参数，安全性基于较为普遍的BDH(Bilinear Diffie-Hellman)困难假设。

2018年，Gay等[11]在文献[6]的基础上做了进一步研究，指出文献[6]的两点局限性：①BGW方案不能抵抗自适应敌手，敌手可根据获取到的公共参数后选择容易发起攻击的用户；②BGW方案的安全性依赖参数化假设(parameterized assumptions)，即q-type的安全性假设，其安全性较弱。文献[11]提出一种更安全高效的公钥广播加密方案，实现了固定大小的密文和用户私钥，且满足自适应安全性。

1.4 典型方案回顾

在文献[6]中提出的两个公钥广播加密方案，均具有完全抗合谋的安全特性。其中，第一个方案(简称BGW1)计算代价较低，而通信代价过高，当接收者数量为n时，系统公钥长度为2n+1，难以应用于大规模网络；第二个方案(简称BGW2)中牺牲了部分计算量，获得更短的公钥长度。

BGW2为公钥广播加密的典型构造，后续大量公钥广播加密的研究均基于该方案[10-11]，因此，本小节给出该方案的具体构造，方案描述如下：

已知接收者集合为{u1,u2,…,un}，将n个用户进行分组，首先确定每个分组的最大接收者数量为B(B

(1)Setup(λ,n)：输入安全参数λ，系统接收者数量n，令A=「n/B⎤。G是阶为素数p的双线性群，随机选取生成元g∈G和一个随机数α∈p。对于任意i=1,2,…,B,B+2,…,2B，计算gi=gαi。接着随机选取A个群元素γ1,γ2,…,γA∈p，设v1=gγ1,…,vA=gγA∈G，将系统公钥设置为

PK=(g,g1,…,gB,gB+2,…,g2B,v1,…,vA)∈G2B+A。

(2)Encrypt(PK,S)：对于任意l=1,…,A，定义子集l和Sl为

l=S∩{(l-1)B+1,…,lB},

Sl={x-lB+B|x∈l}⊆{1,…,B}。

接着，随机选取t∈p，设会话密钥为K=e(gB+1,g)t∈G，其中，e(gB+1,g)可通过e(gn,g)获得。最后，输出(Hdr,K)，其中，

(3)Decrypt(S,i,ki,Hdr,PK)：输入接收者集合S、用户下标i、用户私钥ki、密文首部Hdr和系统公钥PK，其中，i=(a-1)B+b，若用户为合法接收者，则可以通过利用获得的私钥ki计算出

正确性分析：对于合法接收者uij，通过输入kij，有如下等式成立：

e(gB+1,g)t。

2 标识广播加密

在公钥密码体制的实际应用过程中，用户公钥为一串毫无意义的字符串，不便于记忆，对用户并不友好。为保证用户公钥的有效性，需通过证书绑定用户，而证书的引入增加了额外的存储和验证开销。标识密码体制[12]可有效解决公钥密码中加密存在的证书问题，消除了对证书的依赖，用户的公钥可由能够唯一标识用户身份信息的字符串组成，如邮箱地址、手机号码等，使用上述字符串具有便于用户记忆的优点。

随着双线性对实用且安全算法[13]的提出，标识广播加密(Identity-Based Broadcast Encryption,IBBE)也得到了广泛研究。IBBE也称为基于身份的广播加密，系统中的密钥生成中心负责为新加入系统的用户生成并分发用户私钥。

标识广播加密是公钥广播加密的一种特例，用户的私钥由额外的可信第三方生成。标识广播加密工作流程如图1所示。

图1 标识广播加密工作流程Fig.1 The workflow of identity-based broadcast encryption

由图1可知，密钥生成中心(Key Generator Center,KGC)首先运行Setup算法生成主密钥msk和主公钥mpk，接着运行KeyGen算法生成用户私钥,系统中的任意用户均可选择任意接收者集合运行加密算法Encrypt并发布广播密文。在图1中，Alice可向Dave和Eric发送加密消息，授权接收者Dave可利用自己的用户私钥解密广播密文进而获取数据。

2.1 标识广播加密定义

IBBE方案由以下4个可在多项式时间内计算出的算法组成：

(1)Setup(1λ,m)→(mpk,msk):输入安全参数λ和系统可容纳的最大接收者个数m，KGC运行Setup算法，输出系统主私钥msk、系统主公钥mpk。系统主私钥由KGC秘密保存，系统主公钥公开。

(2)KeyGen(mpk,msk,ID)→skID:输入系统主公钥mpk，主私钥msk，用户标识ID，KGC运行KeyGen算法生成用户私钥skID。

(3)Encrypt(mpk,S,M)→CT:输入系统主公钥mpk、接收者标识集合S=(ID1,ID2,…,IDn)和待加密消息M，其中，n≤m，加密者运行加密算法Encrypt，输出密文CT并通过公开信道广播。

(4)Decrypt(mpk,S,CT,ID,skID)→(M/⊥):输入系统主公钥mpk、接收者身份集合S、密文CT、接收者标识ID以及对应的私钥skID，解密者运行解密算法Decrypt，输出正确的明文数据M或者⊥代表解密失败。

标识广播加密的正确性要求对任意的消息M，(mpk,msk)←Setup(1λ,m)，skID←KeyGen(mpk,msk,ID),CT←Encrypt(mpk,S,M)。若ID∈S，那么

Pr[Decrypt(mpk,S,CT,ID,skID)=M]=1。

2.2 安全模型

IBBE的安全模型与PKBE的安全模型相似，主要区别体现在私钥询问阶段，敌手可发起对任意身份ID的私钥询问，但不能询问挑战标识ID*的私钥，挑战者运行KeyGen(mpk,msk,ID)算法并将产生的密钥发送给敌手[14]。

2.3 标识广播加密研究现状

Sakai等[14]在2007年提出了标识广播加密，可利用任意字符串作为接收者的公钥，避免了对公钥基础设施的依赖。在通信代价方面，该方案优于BGW方案，其公钥大小与最大接收者数量有关，适用于潜在用户数量较多，而实际接收者数量比较少时且接收者不会经常发生变化的场景；在安全性方面，该方案满足完全抗合谋攻击，基于随机谕言模型证明了方案满足CPA安全。

同年，Delerablée[15]提出具有定长密文和私钥的IBBE方案，文献[15]利用多接收者密钥封装(multi-receiver Key Encapsulation Mechanism,mKEM)[16]机制，mKEM是一种高效的多用户密钥协商技术，与多接收者公钥加密[17-18]不同，文献[17-18]为一个发送者向多个接收者发送不同的消息。文献[16,19]中将多接收者密钥封装的概念扩展到标识多接收者密钥封装(multi-receiver Identity-based Key Encapsulation Mechanism,mID-KEM)。

Boneh等[20]为构造标识广播加密提供了通用的构造方案，并使用分层标识加密技术构造了首个具有短密文的分层标识广播加密方案，密文由3个元素组成，私钥长度随系统的复杂性线性增长。

刘潇等[21]基于文献[15]，通过在广播接收者集合中引入虚拟标识，构造了一个具有静态(selective)选择密文安全(Chosen Ciphertext Attack,CCA)的标识广播加密方案，与文献[15]相比，公钥长度增加一个群元素。在加密过程中，增加了与接收者集合相关群元素的哈希值计算过程，解密过程中也增加了对该哈希值的计算，可利用该部分的内部关联特性检验广播密文是否有效。

Kim等[22]利用混合阶群下的对偶加密(dual system encryption)技术提出一个自适应(adaptive)选择密文安全的标识广播加密方案，该方案的系统公钥和用户私钥均随着最大接收者个数线性增长，密文长度为定长。

文献[23]把内积加密技术融合到广播加密系统中，提出内积型标识广播加密方案，解密结果不在是明文，而是与用户私钥和明文关联的内积值，可用于数理统计等应用场景。

赖建昌等[24]结合SM9商用标识密码的特点，提出了首个基于SM9的标识广播加密方案，在SM9标识加密算法的基础上，密文长度仅增加一个群元素，并采用与SM9标识加密算法相同的密钥生成算法。

Yao等[25]也对内积型广播加密进行了深入研究，考虑到广播加密接收者的身份隐私，提出了具有匿名性质的基于证书的内积广播加密，同时证明了该方案在IND-CCA安全模型下是自适应安全的，密文长度随着接收者数量线性增长。Liu等[26]针对云场景中重复数据的删除进行研究，利用广播加密技术提出了一种无需独立密钥管理服务器的客户端重复数据删除协议。

2.4 典型方案回顾

在Delerablée[15]提出的方案中，系统公钥长度与系统可容纳最大接收者个数成线性关系，密文长度为固定长度。后续具有定长密文的IBBE方案大多采取该方案的构造技术，方案的具体描述如下：

(4)Decrypt(S,IDi,SKIDi,Hdr,PK)：输入由广播信道获取的密文首部Hdr=(C1,C2)，接收者标识集合S，用户自身的标识IDi和标识对应的私钥SKIDi以及公钥PK。首先计算

其中，

方案的正确性分析如下：

若IDi∈S，则

T=(e(C1,hpi,n(γ))·e(SKIDi,C2))=

3 匿名广播加密

由广播加密的定义可知，在解密过程中，每个用户需要输入密文CT，接收者集合S，自己的私钥skID和主公钥mpk，所有接收者信息也作为广播密文的一部分传输，这种设置将造成严重的隐私泄露问题。假设在付费电视中使用的是上述不提供匿名性的广播加密，授权用户集合为某个频道所有付费用户的集合，那么用户必须知道所有购买该频道的用户才能解密，该做法侵犯了消费者隐私，在实际部署中极为不便。

然而在当今互联网环境，保护用户的隐私至关重要，密码学几个重要研究领域都依赖匿名性，例如数字签名中的群签名和匿名凭证。在很多广播场景中，授权用户的身份信息和广播消息本身同样是敏感内容。理想情况下，广播加密方案应确保密文不会泄露任何接收者集合的任何信息，进而保护接收者的隐私。

3.1 匿名广播加密定义

匿名广播加密的形式化定义与IBBE类似，区别在于匿名广播加密在解密阶段无需输入接收者集合。

3.2 匿名广播加密安全模型

匿名广播加密不仅需要保证消息的机密性，还要保证接收者的匿名性。接收者的匿名性由选择密文攻击下的用户集合不可区分性(Anonymous indistinguishability under Chosen-Ciphertext Attacks,ANON-CCA)[27]来定义，该交互游戏确保敌手无法区分由两个不同接收者集合生成的密文。

(1)系统建立阶段

已知安全参数λ和系统可容纳的最大接收者个数m，挑战者运行Setup(1λ,m)算法，输出主公钥mpk及主私钥msk，将mpk发送给。

(2)询问阶段1

敌手允许在该阶段自适应地发起如下询问：

a.私钥询问：输入标识ID，挑战者运行算法KeyGen(mpk,msk,ID)→skID，将结果发送给敌手；

b.解密询问：输入标识ID和密文CT，挑战者运行解密算法Decrypt(mpk,S,CT,ID,skID)→M，将解密得到的消息M返回给敌手。

(3)挑战阶段

(4)询问阶段2

(5) 猜测阶段

定义3 如果对于任意的PPT敌手，在上述游戏中获胜的优势是可忽略的，则称广播加密方案是ANON-CCA安全的。

3.3 相关工作

在以往对广播加密的研究中，大多围绕提高广播加密系统的抗合谋能力和减少广播密文长度展开，Barth等[28]提出私有广播加密的概念，首次解决了用户隐私泄露的问题。并提出一个私有广播加密方案的通用构造，方案满足静态敌手模型下的匿名性和IND-CCA安全，能够保证在不泄露接收者身份信息的情况下正确解密。

文献[29]利用子集覆盖(subset-cover)技术提出具有亚线性密文长度的匿名标识广播加密方案，并给出了外部匿名性的形式化定义。对于接收者集合S外的用户来说是匿名的，但对于S内的用户不满足匿名性。

Libert等[30]指出文献[29]中的匿名性较弱，不能满足完全匿名性，然而完全匿名性在实际应用中是必要的。文献[30]给出了匿名广播加密的形式化定义，并提出两个具有CCA安全的匿名广播加密的一般构造。然而，方案的匿名性由多个对称加密的密文构成，通信代价和解密计算开销较大。

文献[31]提出可在不需要解密的情况下匿名撤销IBBE系统中部分接收者的解密权限，该方案满足完全匿名性，只有数据发送方知道接收者的身份信息，并且撤销过程不会泄露明文和接收者身份的任何信息。

基于证书(certificate-based)的匿名广播加密概念在文献[32]中给出，文献[32]同时给出了相应的形式化定义和安全模型，并提出一个自适应CCA安全的基于证书的匿名广播加密方案。基于证书的密码机制解决了传统公钥密码体制中的证书管理问题，无需建立安全信道，同时也避免了标识密码体制中的密钥托管问题。

3.4 典型方案回顾

文献[27]提出了在选择密文攻击下可同时满足机密性和完全匿名性的AIBBE方案，且公共参数和私钥大小与接收者数量无关，方案通信代价较小，具有代表性。该方案描述如下：

符号定义为[x]表示比特串x的前位，[x]表示比特串x的后位。x‖y表示将比特串x和y连接。

(1)Setup(1λ):以安全参数λ为输入，首先生成双线性群(p,G,GT,e)，其中，p是长度为λ的素数，G,GT为两个p阶循环群，e为双线性映射e:G×G→GT。随机选取生成元g,u,v,w∈G，选取一个随机数α∈p作为主密钥，计算g1=gα。接着选取4个哈希函数:p。公共参数设为

paras=(p,G,GT,e,g,g1,u,v,w,H1,H2,H3,H4),

私钥msk=α。

(3)Encrypt(params,S,m)：输入系统公开参数params,接收者身份信息集合S={ID1,ID2,…,IDt}和代价密广播消息m∈{0,1}l，执行以下步骤：

1)选取随机数r,k,τ∈p;

2)计算G中群元素C0=gr；

3)对任意IDi∈S，计算VIDi=H2(e(QIDi,g1));

4)计算多项式

5)计算

C1=[H3(k‖C0)]l-l1‖([H3(k‖C0)]l1)⨁m，

h=H4(C0,C2,a0,a1,…,at-1),C2=(uhvτw)r，

输出密文CT=(τ,C0,C1,C2,a0,a1,…,at-1)。

[C1]l-l1≠[H3(k‖C0)]l-l1，

则解密失败，输出⊥。否则可得到广播明文m=[C1]l1‖([H3(k‖C0)]l1)。

由上述方案可知，用户在解密过程中无需输入接收者集合，有效保护了接收者的身份信息。方案的正确性分析如下：

若接收者获得的C0,C2未经篡改过，则如下等式成立：

e(g,C2)=e(g,(uh,vτ,w)r)=

e(gr,uh,vτ,w)=

e(C0,uh,vτ,w),

接收者接着可利用自己的私钥计算VID：

VID=H2(e(skID,C0))=

H2(e(QID,g1)r),

带入f(x)可得到正确的k，进而求得正确解密的广播明文。

4 叛逆者追踪广播加密

在一对一传输场景中，只存在一个授权方，若授权方知晓的某个秘密泄露出来，显而易见泄密者就是该授权方。当授权方有多个时，找出泄露秘密的授权方就变得比较复杂。随着网络服务的不断多样化，越来越多的数字产品都以广播的形式进行发放，例如电子图书、电子软件及音乐等。通常情况下，数据提供商会向每一个合法用户分发一个包含用户私钥的硬件或软件“解密盒”，这在付费电视和电子商务中更为常见。然而盗版问题是不可避免的，若某个恶意的订阅者将自己的“解密盒”拷贝给其他人，数据提供商并不能阻止该做法；另一种恶意用户是利用自己的私钥通过共谋生成非法的盗版产品，再进行转卖获取利润。这种行为既侵犯了作者的知识产权，又破坏了正常市场秩序。为减少数据提供商的经济损失，需尽快找出该恶意用户(叛逆者)。

4.1 叛逆者追踪广播加密定义

叛逆者追踪广播加密由以下4个多项式时间算法组成：

(1)KeyGen(λ,n)：密钥生成算法，又称为用户初始化算法，输入安全参数λ和接收者个数n，算法输出公钥e和n个私钥d1,d2,…,dn，其中任何的私钥都可以对广播密文解密。

(2)Encryption(e,S,M)：输入公钥e，接收者集合S和待加密消息M，加密算法输出广播密文C并发送给所有用户。

(3)Decryption(C,di)：输入广播密文C和私钥di，输出解密后得到明文M。

(4)Tracing(D)：输入一个盗版解密盒D，若该解密盒在创建时使用到多个私钥d1,d2,…,dk，则叛逆者追踪算法至少追踪到其中一个叛徒。

叛逆者追踪广播加密的正确性要求对任意的消息M，(e,(d1,…,dn))←Setup(λ,n)，C←Encrypt(e,S,M)。若i∈S，那么

Pr[Decrypt(S,i,di,Hdr,PK)=M]=1。

4.2 叛逆者追踪广播研究现状

叛逆者追踪技术由Chor等[33]在1994年的美密会上首次提出，主要用于对抗广播加密中合谋攻击和重放攻击。文献[33]为基于对称密钥的叛逆者可追踪的广播加密，采用的方法是为每个接收者提供不同的密钥，每一个密钥相当于一个水印，可追溯到特定解密盒的所有者。但对于多个叛逆者合谋产生的解密盒，该方案无法实现有效追踪。随后，Naor等[34]提出了门限叛逆者追踪方案，可有效降低存储代价与计算开销。随后，研究方向主要集中于基于公钥的叛逆者追踪，大量基于公钥的叛逆者追踪方案也相继被提出[35-42]。

Pfitzmann[35]在1996年首次提出了基于公钥的叛逆者追踪方案，指出在对称叛逆者追踪加密体制中存在不满足不可抵赖性的问题，这与对称的消息认证码类似，不提供不可抵赖性，也称为不可否认性。系统权威机构与订阅用户共享密钥，恶意的权威机构可能利用用户的密钥生成盗版解密盒，并且将诚实的用户控告为叛逆者。而非对称的叛逆者追踪方案可避免该问题。文献[35]中利用交互式的密钥分发协议实现叛逆者追踪广播加密方案。

Boneh等[43]指出文献[34,36]中的方案仅能够实现概率性的叛逆者追踪，提出了改进版的公钥叛逆者追踪方案，能够实现确定性追踪且满足k-抗共谋攻击，即当发起共谋的恶意用户(叛逆者)个数不超过k时，至少可以有效识别出其中一个叛逆者，若个数超过k，则不能有效追踪。该方案同样具有黑盒追踪性(无需打开解密盒)。

2008年，Boneh等[44]提出了定长密文的叛逆者追踪方案，密文仅由两个群元素组成，可满足t-抗共谋攻击。与文献[43]的k-抗共谋攻击不同的是，t-抗共谋攻击中允许叛逆者数量t和接收者数量n相等。在文献[44]中t=n时，满足完全抗共谋攻击，且不会增加密文大小。但该方案的私钥长度过大，私钥复杂度为O(t2logn)。

文献[40-41]中的方案均利用复合阶(composite order)双线性群提出，然而复合阶双线性群存在针对模数因式分解的亚指数攻击。为保证安全性，必须使用阶数较大的复合阶群。Garg等[45]指出利用复合阶双线性群效率较低，与素数阶双线性群相比，在相同的安全级别下，复合阶双线性群中的指数运算时间是素数阶双线性群中的25倍，在很多实际应用场景不便于使用。Garg基于素数阶双线性群首次提出了完全抗共谋攻击的叛逆者追踪方案，与文献[43]相比，该方案的加解密效率有大幅提升，且密文长度更短。

4.3 典型方案回顾

文献[42]利用多项式插值技术提出一种具有撤销能力的公钥叛逆者追踪方案，方案满足黑盒追踪性。若出现盗版解密盒，可追踪并撤销门限值为z的用户私钥，而无需更新其他用户的私钥，并可以恢复已撤销用户私钥的解密权限。该方案还满足k-弹性追踪，如果叛逆者的数量为k或更少，跟踪算法可以找到所有叛逆者。由于该方案代表性较强，此后众多叛逆者追踪且可撤销方案均是基于该方案的构造技巧，这里给出文献[42]的具体构造：

令k为最大叛逆者数量，z为可撤销的叛逆者数量门限值，并设2k-1≤z。

(3)Encryption：输入待加密广播消息M，数据提供商随机选取z个未使用过的二元份额组(j1,f(j1)),(j2,f(j2)),…,(jz,f(jz))和一次性随机数r∈q，接着计算联合授权分组

T=(sgra0,gr,(j1,grf(j1)),(j2,grf(j2)),…,(jz,grf(jz))),

其中,s是加密广播数据的会话密钥。数据提供商将广播密文设为E(f(x),M)=(T,E′(s,M))，其中,E()为分组加密算法，例如DES算法。

(4)Decryption：订阅者获取到广播密文(T,E′(s,M))，可利用密文中的T按照如下方式计算会话密钥s，

(5)Traitor tracing：假设可能存在m个订阅者{c1,c2,…,cm}(m≤k)，利用其份额构造了盗版解密盒，为确定这m个用户是否确定为叛逆者。数据提供商可按如下步骤操作：数据提供商随机选取z-m个未使用的份额，如{j1,…,jz-m}，利用测试消息M构造测试密文E(f(x),M)=(T,E′(s,M))，其中

T=(sgra0,gr,(c1,grf(c1)),(c2,grf(c2)),…,(cm,grf(cm)),(j1,grf(j1)),(j2,grf(j2))…,(jz-m,grf(jz-m))),

将(T,E′(s,M))作为盗版解密盒的输入，若该解密盒无法正确解密输出测试消息M，则{c1,c2,…,cm}中存在叛逆者。接着，可缩小集合范围或对集合{c1,c2,…,cm}的标识元素单独运行上述算法，以精确求得叛逆者集合。

5 可撤销广播加密

仅实现叛逆者追踪性质并不能完全满足应用的需求。一个健壮的广播加密系统需满足追踪并撤销功能，当出现非法解密设备时，应确保在第一时间追踪到该非法设备所使用密钥的来源并撤销密钥拥有者的解密能力，使撤销用户不再能够解密密文。

在将一个广播加密系统部署到付费电视等实际应用中时，可能存在如下问题：①用户的私钥可能泄露、丢失；②用户因退订服务退出广播加密系统等；③用户主动离开广播加密系统等。为保证数据机密性，广播加密系统需保证上述用户不再具有解密权限。用于解决该问题的广播加密称为接收者可撤销广播加密(Recipient Revocable Identity-Based Broadcast Encryption,RR-IBBE)。

5.1 可撤销广播加密定义

文献[46]给出的标识可撤销广播加密的定义与标识广播加密的定义类似，区别在于前者在加密阶段输入为撤销用户的标识集合，而后者在加密阶段输入为授权接收者用户的标识集合。

在Susilo等[47]提出的方案中，撤销方式同样为利用接收者标识集合撤销，该方案在加密阶段输入的集合为当前已授权用户的标识集合S，撤销阶段输入撤销标识集合R，则解密阶段只有S′=S-R中的用户可正确解密。

5.2 可撤销广播加密的研究现状

Naor等[48]利用子集-覆盖方法提供了一种经典的追踪可撤销的广播加密构造方法。子集‐覆盖算法为每个不相交的划分集合分配一个长期密钥，并为每个子集加密短期密钥，用短期密钥加密需要广播的消息。文献[48]分别利用完全生成子树和子集差分给出了2种方案的构造。当加密者为一些授权用户集合S⊆{1,2,…,N}提供广播密文时，若存在一个盗版者利用合谋用户T⊆{1,2,…,N}的一组私钥构造了一个盗版解密盒D，那么，跟踪算法可以与D进行交互，并识别追踪到盗版者拥有的一个活动密钥，即其中一个用户的密钥t∈S∩T。广播者将授权用户集合S′设置为S′←S{t}，再进行广播，其中，S{t}表示删除集合S中的t元素。如果盗版解密盒依旧可以解密，再次运行跟踪算法并得到另一个参与共谋的密钥t′∈S′∩T，将授权用户集合S″设置为S″←S′{t′}。按照此方法进行下去，直到盗版解密盒无法解密。

Boneh等[40]提出了增强广播加密(Augmented Broadcast Encryption,ABE)的概念，并给出了可同时满足叛逆者追踪并撤销、完全抗合谋性、黑盒追踪性的方案构造，方案具有亚线性大小的密文和私钥，且可抵抗自适应选择明文攻击的敌手。

文献[45]提出了两个具有短密钥的可撤销广播加密方案，方案的密文开销均为O(r)，其中，r为被撤销的用户数量。公钥和私钥的大小为素数阶椭圆曲线群中的定长群元素，公钥的长度分别为5个和12个群元素，私钥长度分别为3个和5个群元素。与文献[5,7,9]中的方案不同，该方案允许用户创建一个可以撤销无限数量用户的广播密文。而在其他系统中，公共参数限制了系统中的可撤销用户数量，必须更新系统公共参数才能支持撤销更多用户。

谭作文等[49]在2005年提出一种完全式的公钥广播加密方案，与传统的公钥广播加密方案不同，在完全式广播加密方案中，由用户自己生成解密密钥，而传统公钥广播加密中用户的解密密钥由广播者分发。文献[49]还实现了叛逆者追踪和非法用户撤销的功能，该方案在DDH困难假设下可抵抗选择密文攻击。

文献[47]首次提出接收者可撤销的广播加密，在RR-IBBE中，数据提供商将生成的密文内容发送给受信任的第三方，即广播公司。广播公司会周期性的向订阅者广播内容，也可以从加密内容中撤销一组用户，而无需对其进行解密。在文献[47]提出的方案中，首先发送给广播公司长度为m+3个群元素的广播密文，其中，m为一次加密中最大撤销用户数量，广播公司执行撤销算法后生成长度为3个群元素的广播密文发送给订阅者。

Lai等[31]基于文件共享的应用场景提出了匿名标识可撤销广播加密方案，该方案适用于：数据拥有者将文件加密后存储于云服务器中共享，当一个用户集合R中的用户离开公司后，该服务器必须撤销R中用户的访问权限。撤销算法执行后，集合R中用户将不能再利用自己的私钥解密文件。文献[31]提出的方案具有恒定大小的公钥和私钥，撤销阶段的计算开销为O(r)，其中，r为撤销用户的数量。

Ge等[50]从密钥更新的角度出发，实现了可撤销广播加密。文献[50]基于二叉树结构和素数阶双线性群的非对称配对，提出了可撤销IBBE的具体方案。在该方案中，KGC定期发布一些更新密钥所需的元素，只有未撤销的用户才能更新其解密密钥，已撤销用户无法更新密钥。在标准模型中，选择明文攻击下，该方案被证明是半自适应安全的，且实现了固定长度的密文。

5.3 典型方案回顾

文献[46]的方案采用了新型的秘密分享技术，将秘密份额si和撤销用户标识IDi一同嵌入到密文中，使得已撤销用户无法解密密文。该方案的构造技巧后来被广泛应用于属性基加密方案构造中[51-52]。该方案代表性较强，其方案构造具体描述如下：

(1)Setup：定义阶为素数p的双线性群G，随机选取G中2个生成元g,h∈G和中两个随机数α,b∈p将公钥设为PK=(g,gb,gb2,hb,e(g,g)α)，系统私钥为MSK=(α,b)。

(2)KeyGen(MSK,ID)：首先随机选取t∈p，依次计算D0=gαgb2t,D1=(gb·IDh)t,D2=g-t，将私钥设为SKID=(D0,D1,D2)。

(3)Encrypt(PK,M,S)：随机选取s∈p，令r=|S|，即撤销用户数量。随机选取r个随机数s1,…,sr使得s=s1+…+sr。令IDi表示撤销集合S中的第i个身份。接着计算C′=e(g,g)αsM，C0=gs。对于任意i=1,2,…,r，计算

Ci,1=gb,si,Ci,2=(gb2·IDi·hb)si，

密文为CT=(C′,C0,(C1,1,C1,2),…,(Cr,1,Cr,2))。

(4)Decrypt(S,CT,ID,SKID)：输入撤销用户身份集合S、密文CT、用户的身份ID和用户私钥SKID，若用户身份在撤销集合内，则解密算法终止解密。否则，解密算法计算

正确性分析：

W=e(C0,D0)/

e(gs,gαgb2t)/

e(gs,gα)·e(gs,gb2t)/

e(gs,gα)·e(gs,gb2t)/

e(gs,gα)·e(gs,gb2t)/

e(gs,gα)。

6 公钥广播加密的应用研究

广播加密可提供一对多场景下数据安全共享的功能，适用于互联网以及物联网中众多场景，如：

(1)车载自组织网络的安全通信

车载自组织网络(Vehicular Ad Hoc Networks,VANETs)也称车联网，通过车载智能设备可实现云端服务通讯与本地总线通讯，以及通过手机应用对车辆进行远程控制，目前已经成为通信领域和无线传感网领域的一个研究热点。VANETs中的信息传播离不开车辆和基础设施的交互。在VANETs中，可信机构(Trust Authority,TA)通常需要与多台车辆建立安全连接，并发挥重要作用。然而，当TA向多台车辆发送相同的消息时，会产生较多的冗余信息，因为TA需要与每台车辆协商并向每个车辆发送不同的密文。目前，VANETs采用的大多为点对点的通信方式，通信效率较低。因此，广播加密是VANETs通信中的重要研究方向。文献[53]针对车联网场景，提出了一种身份基广播加密方案，适用于车辆到基础设施间的通信。

(2)云存储的访问控制

云存储的访问控制是公钥广播加密另一个重要的研究方向。随着社交媒体的不断发展，众多基于云存储的社交网络应用被广泛使用，如抖音、微信和微博等。用户使用这些应用会产生大量数据。具体而言，通过社交网络应用，用户可获取网络热点新闻，也可以建立朋友群组，以分享个人观点或个人内容，如照片、视频、文件等。社交应用通常会产生大量的敏感数据。一方面，个人终端设备的计算能力和存储空间通常是有限的，使用一段时间后不得不将一些敏感数据删掉；另一方面，对于大多数维持这些应用运行的中小企业来说，随着用户规模的快速增长，企业也无力承担相应的计算和存储成本。因此，云计算和云存储服务应运而生，使得计算资源和存储资源像水、电一样利用。企业用户可以向云计算厂商租用计算资源和存储资源，既可以将大部分计算任务外包给云计算服务器，也可以将大量数据存储于云存储服务器。

近年来，企业和个人用户越来越依赖云存储服务，云存储服务技术发展也逐渐成熟，既有商业级的云存储服务，如亚马逊S3、Egnyte、和Tresorit等，也有消费级的云存储服务，如Google Drive、iCloud、微软OneDrive、Dropbox等。然而，对于云存储服务，需要解决隐私保护问题，即如何确保存储在云中的照片和视频等用户个人数据只能由数据所有者授权的用户访问，而所有未经授权的用户，包括云存储提供商本身，都不能访问或恢复原始的个人数据。因此，针对上述应用场景，提出一种高效安全、低带宽需求的公钥广播加密方案是十分有意义且可行的。文献[54]针对云存储文件共享场景进行了研究，提出了功能广播加密(Functional Broadcast Encryption,FBE)的概念，这是带访问控制的公钥加密的一种表现形式，用于云数据的访问控制。文献[55]也对广播加密在云存储的应用进行了研究，提出了自适应安全的基于证书的广播加密。

(3)在物联网的应用

物联网目前与人们的工作和生活息息相关，海量物联网设备纷纷接入到互联网中，从智能手表到安全门锁，物联网技术已经成为人们生活中不可缺少的一部分。然而，物联网安全并没有得到足够重视，安全事件频发，全球近20%的企业和相关机构在过去3年遭遇物联网攻击。例如在2021年，美国的15万个摄像头被入侵造成个人隐私泄露，以及利用摄像头组成僵尸网络发起的分布式拒绝服务攻击(Distributed Denial-Of-Service,DDOS)攻击等。因此，物联网的安全问题亟待解决。随着物联网的大规模部署，为确保整个网络的安全，需及时进行设备更新以修复高危安全漏洞。文献[56]提出一种适用于物联网中组密钥管理的多变量广播加密方案，可有效减少功耗，并提高物联网数据传输的安全性。一种利用区块链技术提供软件更新的机制在文献[57]中得到研究，一旦更新作为有效区块的一部分添加到区块链中，那么该区块就不可删除，可抵抗阻止物联网设备更新的恶意实体发起的攻击，确保了更新的可用性。同时，还可抵抗针对中心化结构的拒绝服务攻击。对于区块链基础设施向物联网设备共享升级文件、网络配置文件等通信环节，均可采用广播加密技术实现。

(4)基于格密码的广播加密

目前，大多数公钥加密方案的设计通常基于数学困难问题，随着量子技术的飞速发展，现有公钥密码算法在量子计算下将不再安全，量子计算机的出现可能会威胁到基于数学困难问题的密码体制。目前，实用化的密码体制仍是基于数学困难问题的公钥密码。格密码作为抗量子密码算法，是公认的后量子密码领域中最热门的研究方向之一。近年来，学者们已经逐步开始研究抗量子广播加密，提出了一些优秀的基于格的广播加密方案[58-60]，基于格密码的广播加密研究也将成为未来较为重要的研究方向之一。

7 结论与展望

近年来，随着无线传感网、智能终端、云计算等新兴应用的快速发展，网络形态逐步呈现出层次化、服务化等特点。面向服务的计算通常采用资源共享的工作方式，该工作方式的特点为多个用户请求同一个数据。企业或个人的数据上云首要解决的问题就是数据安全与隐私保护。广播加密为一对多场景下数据安全且高效的共享提供了解决方案，在物联网、云存储的访问控制等应用中得到广泛使用。

本文介绍了公钥广播加密的概念、定义以及安全模型，针对不同应用场景的安全需求，详细论述了公钥广播加密、标识广播加密、匿名广播加密、叛逆者追踪广播加密以及可撤销广播加密的原理、特征及研究成果。

虽然目前已经存在大量公钥广播加密研究的文献，但大多围绕国外算法展开，基于国产密码的广播加密算法及其衍生的功能型算法较少。因此，设计安全高效的具有不同功能的国产公钥广播加密算法可作为未来的研究方向之一。此外，目前基于格的广播加密研究较少，也将成为未来的研究热点。