采用扩展公钥的云存储广播加密优化方法

李春花 王 桦 张彦哲 周 可

(武汉光电国家实验室(华中科技大学) 武汉 430074)

采用扩展公钥的云存储广播加密优化方法

李春花 王 桦 张彦哲 周 可

(武汉光电国家实验室(华中科技大学) 武汉 430074)

(li.chunhua@hust.edu.cn)

基于广播加密的云存储系统受到研究者的关注.然而，基本的广播加密方案不能适应云存储环境中用户和权限的动态变更情况.针对广播加密中密钥管理分发开销大的问题，提出一种扩展公钥的广播加密优化方法，通过保留初始产生公钥时使用的部分私有参数，当用户加入或撤离系统时，使用保留的私有参数产生新的公钥来加密数据.这样，合法用户仍可以使用之前已分发的私钥解密新公钥加密的数据，从而避免了用户动态变化时公钥的频繁变化和密钥的重复分发.通过引入懒惰回收机制，降低了权限变更和密钥定期更新带来的开销.测试结果表明：采用优化方案后，增加用户数量和权限撤销时，系统性能得到较大提高.

云存储；广播加密；扩展公钥；密钥管理；优化

近年来，云存储因其价格低廉、部署方便、随时随地可用等优点而成为信息领域的一大研究热点.然而，用户将数据存放到云端之后便失去了对数据的直接控制，存放在云端的数据能否得到安全的管理和有效的访问控制一直是用户担忧的问题，尤其是近年来屡次出现的一些隐私泄露、数据丢失等安全事件，给云存储系统的进一步推广应用带来了很大的阻碍[1-2].

数据加密技术是提高存储系统安全和数据安全的一种基本方法，将数据在上传到云端之前进行加密可以有效地保护数据的机密性.云存储系统中由于用户群体广泛、文件数量巨大，因此管理数据密钥和会话密钥非常复杂，加上云用户时不时地加入和撤离系统，导致密钥更新频繁，极大地影响了系统的性能.如何提高云存储系统中密钥管理的安全性、如何降低密钥重分发的性能开销是云存储安全研究的重要内容之一.

已有的安全云存储系统中针对密钥的管理和分发提出了很多方法.Adya等人[3]提出一种无密钥服务器的分布式文件系统FARSITE，他们采用对称密钥加密文件，并用被授权用户的公钥加密对称密钥后存储在云端，这种方式在权限变更时计算开销较大.文献[4]提出的Plutus系统中文件和目录都进行了加密，通过file-groups实现文件之间权限的共享，减少了分发密钥的次数；但是Plutus系统中用户是直接向数据拥有者请求密钥的，这样不仅增加了数据拥有者的负载，更重要的是在数据拥有者离线时无法获取文件访问权限，这种设计模式也使得权限的撤销变得更加复杂.Goh等人[5]提出一种中间件形式的安全存储系统SiRiUS，每个文件采用对称密钥进行加密，并用非对称密钥进行文件签名，以确保文件的完整性.同时每个用户拥有2个对应的非对称密钥用于加密文件密钥和签名密钥，并存储在元数据中以方便分发.这种方法虽然结合了FARSITE和Plutus的优点，但并没有克服密钥重分发和带宽开销较大问题，其扩展性不足以适应云存储环境.

文献[6]提出的Cloudproof系统使用广播加密机制进行密钥分发，密钥的管理比SiRiUS更加简单.同Plutus系统类似，Cloudproof系统中也使用了群组的方式减少密钥数量，采用block-group将权限相同的块使用相同的密钥加密，虽比Plutus访问控制粒度更细，但并没有解决撤销权限时的开销问题.而且，Cloudproof系统采用的是固定公钥广播加密方案，密文和私钥的大小固定，但要求接收用户集合在系统建立时就能唯一确定，此后若有用户加入或离开，则计算开销会很大，因此无法适应用户变化频繁的云存储环境.文献[7-8]提出了动态广播加密的概念，用户可以在广播系统建立之后再加入到系统中，但由于加解密时间开销较大，无法满足云存储系统的性能要求.文献[9]提出一种使用多重线性映射方法解决公钥广播加密中长期存在的性能开销问题，但不能保证重新生成的随机数是有效的，从而增加了系统的不稳定性.

本文将在Cloudproof基础上，对其使用的广播加密方案进行优化，通过扩展公钥和保留系统初始阶段产生公钥时所使用的部分私有参数来提高密钥管理的效率和权限变更时的性能.当用户加入或撤离系统时使用保留的私有参数产生新的公钥来加密数据，这样已授权用户仍可以使用之前分发的私钥来解密采用新公钥加密的数据，从而避免了因用户和权限的动态变化而导致频繁的公钥变化和密钥重分发等问题.

1 背景知识

广播加密用于在广播信道上传输加密的消息[10]，通过广播加密进行加密的内容只有加密时选定的授权用户集合中的用户才能正确解密.密钥由数据拥有者管理，无需在系统中引入第三方，且数据拥有者不需要长期在线，大大简化了密钥管理的复杂性.本文采用文献[11]提出的公开密钥广播加密方案(BGW方案)，针对该方案应用在云存储环境中产生的问题进行优化.

1.1 双线性映射

设G和G1是阶为p的乘法循环群，g是群G的生成元，称映射e:G×G→G1为一个双线性映射，如果e满足3个性质：

1) 可计算性(computable).存在有效算法对∀R,S∈G，计算e(R,S)的值.

2) 双线性(bilinear).对于∀R,S∈G和a,b∈Zp，都有换算关系：

e(Ra,Sb)=e(R,S)a b.

(1)

3) 非退化性(non-degelerate).

e(g,g)≠1.

(2)

映射过程中用到的一些数学符号定义如下：

Zp——模p的加法群{ 0,1,…,p}；

G——包括G和G1，均是阶为p的乘法循环群；

g——群G的生成元；

e( , )——双线性映射.

1.2 BGW方案

在BGW方案中，一个广播加密系统由3部分组成.

1) Setup(n).输入接收者的数量n，输出n个私钥d1,d2,…,dn和公钥PK.具体过程如下：

选取G的任意生成元g∈G和任意a∈Zp，对于i= 1,2，…，2n，计算g(αi)∈G，将g(αi)视作gi.选取任意γ∈Zp，计算v=gγ∈G，最终得到:

PK=(g,g1,…,gn,gn+2,…,g2n,v).

(3)

计算用户私钥:

(4)

2) Encrypt(S,PK).输入一个接收者的子集S⊆{1,2,…,n}和公钥PK，输出 (Hdr,K).其中K作为对称密钥用于加密，Hdr则是本次加密产生的公开信息.具体过程为：

3) Decrypt(S,id,di,Hdr,PK).输入公钥PK、步骤2中输入的S和产生的Hdr以及用户的id和私钥di，输出K，用K解密数据:

(5)

BGW方案中用户需要存储的私钥di大小固定，加解密时都需要使用公钥PK，公钥大小为O(n)，解密时还需要广播头Hdr，Hdr的大小固定，加解密的运算量均为O(t)(与授权用户数相关).

2 基本方案及优化方法

本节分析了基于广播加密的密钥分发基本方案，指出了其中的不足，在此基础上提出了适用于云环境的广播加密优化方法.

2.1 基于广播加密的密钥分发基本方案分析

在云存储环境中使用广播加密管理密钥时，系统由3部分构成：云端、数据拥有者和普通用户.每个用户都可以同时是数据拥有者和普通用户.

图1描述了用户与云端的交互过程。其中，用户1对于其上传到云端的文件来说是数据拥有者，用户2和用户3可以向用户1请求这些文件的访问权限，同时当用户1请求用户2和用户3的文件权限时又是普通用户.所有文件的权限都由对应的文件上传者管理，云端只负责接收文件的读写请求，无法对没有权限的用户授权，也无法获取文件内容.

Fig. 1 Interactive processes between the user and the cloud图1 用户和云端的交互过程

1) 区分文件读写权限

数据拥有者上传文件之前首先使用对称加密算法加密文件，加密文件使用的密钥记作Ke；之后选取一对非对称加密体制中的公私钥Kv和Ks，使用私钥Ks对加密后的文件生成一个签名Sig，并将签名和Kv与文件一起上传到云端.这样数据拥有者就可以通过分发Ke和Ks的方式向用户授予读写权限.得到Ke的用户可以解密出文件内容，即拥有读权限.用户在每次修改文件内容时需要使用Ke将文件重新加密，然后使用Ks重新生成签名，云端需要在用户每次提交读请求时使用Kv检查签名是否正确，所以只有持有Ks的用户拥有写权限.

2) 授予用户权限

数据拥有者通过广播加密将读写密钥分发给其他用户，选取拥有读权限的用户集合Sr和拥有写权限的用户集合Sw，分别用2个集合为参数使用广播加密将Ke和Ks加密，将加密后的Ke和Ks与文件一起上传到云端，这样有权限的用户就可以通过自己事先从数据拥有者获取到的广播加密私钥di解密出对应的Ke或Ks，从而获取文件的权限.撤销用户权限时需要先生成新的读写密钥，将对应的密钥重新使用广播加密方案加密后上传.如果更新了读密钥还需要重新加密文件.

在系统初始化之后，数据拥有者保存了公钥PK和用户数n，云端保存了公钥PK，其他用户只保存自己对应的私钥di.

在上传某个文件之后，数据拥有者和其他用户保存的内容不变，而云端则需要额外存储对应的用户集合Sr，Sw和广播加密生成的公开信息Hdr.

Fig. 2 Data format stored in the cloud图2 存储在云端的数据格式

从上述数据交互和密钥分发的过程可以看出：用户加入系统时需要获取其他所有用户分发的广播加密私钥，也需要向其他所有用户分发广播加密私钥，导致空间开销和带宽开销都很大.由于广播加密的初始阶段是根据当前指定的用户数进行初始化的，新用户加入系统必然引起所有用户的重新初始化，此时产生的新私钥和原有的私钥不同，文件也需要重新加密，因此导致时间开销和带宽开销都很大.针对以上问题本文提出一种针对广播加密的扩展公钥方法，以降低用户数量变化时密钥重分发引起的时间开销和带宽开销.

2.2 扩展公钥优化方法

广播加密系统中，用户之间交互时由于相互存储了对方提供的广播加密私钥，造成存储空间的浪费，同时也增加了用户分发私钥的时间开销.实际情况中用户不会向所有其他用户请求文件，因此，在用户加入系统时可以不获取所有私钥，而是在第1次请求文件时数据拥有者才向他分发广播加密私钥，这样不仅减少了用户存储的私钥数量，也减少了分发私钥的次数，从而减少了网络开销.然而当系统用户数增加时仍然会产生重新初始化的问题，针对此问题本文提出一种扩展公钥的方法，在撤销用户权限时使用懒惰回收策略以减少文件重加密引起的开销.

由2.1节可知，广播加密公钥PK和用户私钥di都是在系统初始化阶段生成:

PK′=(g,g1,…,gn,gn+1,gn+3,…,
g2n,g2n+1,g2n+2,v)，

在新公钥中增加的gn+1会破坏原有公钥的安全性，原有公钥中的gn+2也会影响新公钥的安全性，因此如果按这种方式扩展公钥就需要将公钥扩展为原本的2倍大小以确保安全.用户请求私钥时先检查当前的公钥是否还可以产生新私钥，如果不可以再进行扩展.由于更新了广播加密公钥，之前的key block需要重新加密，这部分开销与文件数相关.

用户进行广播加密和解密时都需要下载公钥，实际加解密时使用的并不是公钥中的全部参数，而是有权限的用户对应的那一部分，若改变公钥的存储方式，让用户可以选择性地下载公钥中的某些参数，则可以将用户进行广播加解密时的带宽开销从O(n)降低到O(t)，其中n表示公钥能产生的私钥数，t表示本次加密有权限的用户数.

2.3 懒惰权限回收的优化策略

本方案中，数据拥有者在撤销用户读权限之后生成新的对称密钥，并对新的有读权限的用户集合广播加密，使用版本号区分新旧密钥并且将版本号附在文件后上传到云端，用户在读文件时根据文件当前加密使用的版本号选取对应的密钥解密文件.用户提交写操作时使用最新的密钥加密，当文件密钥版本更新到最新之后，下次数据拥有者修改key block内容时将旧版本密钥丢弃.撤销用户写权限时生成新的公私钥对并立刻更新key block中的内容和文件签名即可.

之所以保留当前版本到最新版本的密钥，是因为如果数据拥有者在更新密钥时删除当前版本和最新版本之间的密钥，有可能在更新权限时有其他用户在进行写操作，那么其他用户加密使用的密钥会被丢弃，从而使得文件无法解密.而更新写密钥时进行写操作只会导致云端验证不通过，用户可以重新获取写密钥生成签名或重新提交写请求.

Fig. 3 The cloud data format when lazy revocation is introduced图3 引入懒惰回收后云端数据的格式

2.4 安全性分析

BGW方案的安全性是基于BDHE假设的，可以抵抗完全同谋攻击，即所有无权限用户联合起来也不能获得广播加密明文，适合在云环境中保护密钥所需要的安全性，因此数据拥有者可以使用基本方案安全地分发密钥.

采用扩展公钥方法后，新产生的公钥中gn+1会破坏原有公钥的安全性，因此在扩展公钥之后需要将key block使用新的公钥重加密.重新加密避免了增加用户带来的安全风险，但是也产生了额外计算开销，这部分开销会使得扩展公钥时用户加入所需的时间较长.原有公钥中的内容均包含在新公钥中，不会影响新公钥的安全性.由于数据拥有者需要保留α和γ以生成新公钥，而公开α会使得BDHE假设不成立，公开γ使得用户可以计算其他用户的私钥，因此数据拥有者需要避免α和γ的泄露.

引入懒惰回收机制，使得用户在被撤销读权限之后、文件读密钥更新之前仍可以使用之前的读密钥解密文件，即：若用户缓存了文件读密钥，则在文件密钥更新之前仍可以读取文件，这在一定程度上降低了安全性，但是用户被撤销权限之后只能获得修改之前的文件内容，无法获取文件最新内容，从而保护了修改后文件的安全访问.这样的权衡自然一定程度上降低了安全性，但是考虑到一旦用户可以读文件内容即可以保留一份文件的副本，本方法认为延长用户对文件历史版本的读权限的有效时间，虽然增加了信息泄露风险但提高了系统的整体性能，这种平衡策略是可以接受的.

3 性能评估

在开源云存储项目OpenStack的Swift平台上对本文方案进行了测试.密钥管理分发方案的额外开销主要产生在用户数量变化和密钥变化时，本文将从这2方面进行对比测试.

由BGW方案的介绍可知，方案中私钥di大小固定，加解密时都需要使用公钥PK，公钥大小为O(n)，初始化产生一个公钥的时间也是O(n)，解密时还需要广播头Hdr，Hdr的大小固定，加解密的运算量均为O(t).对于扩展公钥的方法来说，加解密的运算量不变，扩展公钥到可以支持n个用户时的时间开销为O(n).

在实际使用中，当前对算法的实现中单个私钥大小为276 B，Hdr大小为216 B，而公钥的大小则和用户数量相关，在用户数为8 192时约7 MB.根据所使用的加密算法不同，key block的大小也会不同，这部分开销与系统的具体实现相关.

3.1 扩展公钥方法的对比测试

在使用广播加密前需要针对对应的用户数量进行初始化.对于基本方案，有新用户加入系统时，系统中的其他用户都需要更新用户数并进行初始化，该用户也需要针对系统中其他用户做初始化.采用扩展公钥方法之后，用户第1次初始化产生一定大小的公钥，之后通过扩展公钥的方式适应用户数或角色数的变化.

图4可以看出，系统采用扩展公钥优化方法之后，增加新用户时时间开销大大降低.基本方案中，每次加入新用户产生的重新初始化时间开销很大，增加300个用户的时间超过770 s.对于扩展公钥方法，在当前公钥可以分配的私钥用完之前增加用户的开销非常低，增加300个用户的时间小于10 s，增加10 000个用户的时间是284.37 s(由于横坐标的关系，未在图上表示出来)，而且之前已经加入的用户也不需要更换私钥.由于本文采用了公钥扩展方案后统一使用新公钥加密的方式，在公钥扩展时有可能需要对key block进行修改.

Fig. 4 Time cost vs the number of users between BGW and our scheme图4 系统增加用户时的时间开销

3.2 懒惰回收对密钥更新的优化

撤销权限的时间开销主要取决于对对应密钥进行广播加解密消耗的时间，在没有采用懒惰回收机制的方案中，用户撤销读权限需要下载文件重新加密，在采用了懒惰回收机制之后省去了这部分开销，撤销写权限不需要重加密，两者的开销是相同的.

Fig. 5 Time cost when lazy revocation scheme is adopted图5 结合懒惰回收策略的时间开销

图5表示基本方案和结合懒惰回收之后撤销读权限的开销，用户数为1 000，授权用户数为100.由于实验室测试环境处于同一局域网内，上传下载的速度可以达到10 MBps左右，但是在文件较大时，基本方案撤销读权限耗时仍较高.相比基本方案，采用懒惰回收之后的开销和文件大小没有关系，只有下载、修改和上传key block的开销，这部分时间开销在总用户数1 000、授权用户数100时为0.02 s，相比基本方案，时间开销降低很多，也节省了下载上传文件消耗的带宽.

4 结束语

为了解决使用广播加密在云存储系统中重新分发密钥存在的性能开销大的问题，本文提出了一种对公钥进行扩展的方法，并且结合懒惰回收机制进一步优化了权限撤销时的性能.测试表明优化方法降低了基本方案在增加用户和更新密钥时的时间开销和带宽开销，可以更好地适应云存储系统中用户的动态变化.

[1]Liu Yahui, Zhang Tieying, Jin Xiaolong, et al. Personal privacy protection in the era of bid data[J]. Journal of Computer Research and Development, 2015, 52(1): 221-228 (in Chinese)(刘雅辉, 张铁赢, 靳小龙, 等. 大数据时代的隐私保护[J]. 计算机研究与发展, 2015, 52(1): 221-228)

[2] Kan Yang, Jia Xiaohua. Expressive, efficient, and revocable data access control for multi-authority cloud storage[J]. IEEE Trans on Parallel and Distributed Systems, 2014, 25(7): 1735-1744

[3] Adya A, Bolosky W J, Castro M, et al. Farsite: Federated, available, and reliable storage for an incompletely trusted environment[C] //Proc of the 5th Symp on OSDI. New York: ACM, 2002: 1-14

[4] Kallahalla M, Riedel E, Swaminathan R, et al. Plutus: Scalable secure file sharing on untrusted storage[C] //Proc of the 2nd USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2003: 29-42

[5] Goh E, Shacham H, Modadugu M, et al. SiRiUS: Securing remote untrusted storage[C] //Proc of the Network and Distributed System Security Symp (NDSS 2003). Reston, VA: Internet Society, 2003: 131-145

[6] Popa R A, Lorch J, Molnar D, et al. Enabling security in cloud storage SLAs with CloudProof[C] //Proc of the 2011 USENIX Annual Technical Conf. Berkeley, CA: USENIX Association, 2011

[7] Cecile D, Pascal P, David P. Fully collusion secure dynamic broadcast encryption with constant-size ciphertexts or decryption keys[C] //Proc of the 2007 Int Conf on Pairing-Based Cryptography. Berlin: Springer, 2007: 39-59

[8] Cecile D. Identity-based broadcast encryption with constant size ciphertexts and private keys[C] //Proc of CRYPTO 2007. Berlin: Springer, 2007: 200-215

[9] Boneh D, Waters B, Zhandry M. Low overhead broadcast encryption from multilinear maps[C] //Proc of CRYPTO 2014. Berlin: Springer, 2014: 206-223

[10] Koyama K, Ohta K. Identity-based conference key distribution systems[C] //Proc of CRYPTO 1987. Berlin: Springer, 1987: 175-194

[11] Boneh D, Gentry C, Waters B. Collusion resistant broadcast encryption with short ciphertexts and private keys[C] //Proc of CRYPTO 2005. Berlin: Springer, 2005: 258-275

OptimizationforBroadcastEncryptioninCloudUsingExtendedPublicKey

Li Chunhua, Wang Hua, Zhang Yanzhe, and Zhou Ke

(WuhanNationalLaboratoryforOptoelectronics(HuazhongUniversityofScienceandTechnology),Wuhan430074)

Security issues have been a major hurdle for the application of cloud storage. As data encryption is the mainstream method to ensure confidentiality, users always share their data by means of key’s management and distribution. However, how to manage massive keys and distribute them securely and efficiently is a challenge in cloud storage. In recent years, broadcast encryption scheme has been paid more attention by researchers to mitigate above problems for cloud data sharing. Since current schemes take insufficient account of changes of users and users’s privilege, they do not perform well in cloud. To reduce the overhead of key distribution, an optimization method is proposed for public-key based broadcast encryption in this paper. First, the scope of public keys is expanded to two or more times and the initial related parameters used for generating public keys are kept simultaneously. These parameters can ensure private keys distributed previously still available when they are employed to generate the new public keys for new valid users, thus greatly decreases the cost of redistributing private keys. Second, lazy revocation is adopted to reduce the cost of updating keys. Experimental results show that our optimized method outperforms the existing schemes while adding new users and revoking users’ privilege in cloud.

cloud storage; broadcast encryption; extended public key; key management; optimization

2015-10-12；

2017-04-14

国家重点研发计划项目(2016YFB0800402)；中央高校基本科研业务费专项资金项目(2016YXMS020)

This work was supported by the National Key Research and Development Program of China(2016YFB0800402) and the Fundamental Research Funds for the Central Universities(2016YXMS020).

王桦(birch_wh@163.com)

TP391

LiChunhua, born in 1971. PhD, associate professor. Her main research interests include storage security, privacy protection, and big data.

WangHua, born in 1975. PhD, associate professor. Her main research interests include cloud storage system, data backup and caching.

ZhangYanzhe, born in 1991. Master. His main research interests include storage system and information security (465096070@qq.com).

ZhouKe, born in 1974. Professor, PhD supervisor. Senior member of CCF. His main research interests include distributed system, cloud computing, storage security and big data (k.zhou@hust.edu.cn).