高效无双线性对的基于证书代理重加密方案

徐海琳 陈莺 陆阳

摘要：针对已有基于证书代理重加密（PRE）方案需要复杂的双线性对运算，计算效率较低的问题，提出了一个高效的不依赖于双线性对的基于证书代理重加密方案。基于计算性DiffieHellman（CDH）问题的困难性假设，该方案在随机预言模型下被严格证明满足适应性选择密文攻击下的不可区分安全性，即满足选择密文安全性。所提方案的构造基于椭圆曲线群，避免了计算开销高昂的双线性对运算，因此方案的计算性能得到了显著提高。对比分析表明，相对于已有使用双线性对的基于证书代理重加密方案，所提方案在计算效率和通信代价两个方面都具有明显的优势，更适用于计算受限以及低通信带宽的应用场合。

关键词：公共云；基于证书代理重加密；椭圆曲线；随机预言模型；选择密文安全性

中图分类号：TP309.7 文献标志码：A

Abstract： All the previous certificatebased Proxy ReEncryption （PRE） schemes are based on the computationallyheavy bilinear pairings， and thus have low computation efficiency. To solve this problem， a certificatebased proxy reencryption scheme without relying on the bilinear pairings was proposed over the elliptic curve group. Under the hardness assumption of the Computational DiffieHellman （CDH） problem， the proposed scheme was formally proven to be indistinguishable against adaptively chosenciphertext attacks in the random oracle model. Due to avoiding the timeconsuming bilinear pairing operations， the proposed scheme significantly reduced the computation cost. Compared with the previous certificatebased proxy reencryption schemes with bilinear pairings， the analysis shows that the proposed scheme has obvious advantages in both the computation efficiency and the communication cost， and the scheme is more suitable for the computationconstrained and bandwidthlimited applications.

Key words：public cloud； certificatebased proxy reencryption； elliptic curve； Random Oracle Model （ROM）； chosenciphertext security

0 引言

云计算是近年来互联网领域发展的热点，它旨在通过计算机网络把多个成本相对较低的计算实体整合成一个具有强大计算能力的完美系统， 搭建高可扩展性、超大规模、高可用性以及低廉成本的云计算平台已经成为当前信息化建设的方向。作为云计算最广泛的应用，云存储为广大用户带来方便性的同时，也造成了数据所有权和管理权分离的问题。当用户使用云计算环境时，需要将数据存储至云端并依靠云服务提供者处理数据，这使得数据脱离了用户的控制。由于用户数据中含有隐私敏感信息，因此需要有合适的机制来保障存储在云端的用户数据不被非授权访问。密文访问控制是云存储模式下实现用户数据机密性和访问控制的重要方法，该方法要求数据拥有者将数据加密后存放在云端。为了解决加密数据分发或分享的问题，一些密文访问控制方法采用了密钥分发的方法，即数据拥有者通过保密的方式将解密密钥发送给授权用户。在这种情况下，需要针对不同的访问控制单元使用不同的密钥加密数据，显然这会造成数据的重复加密，从而浪费大量的计算资源和存储资源。另一类解决方法则需要数据拥有者从云端取回加密数据，解密后再使用被授权用户的公钥对数据重新加密并发送给被授权用户，显然这会给数据拥有者带来严重的计算和通信开销，从而降低系统整体效率。因此，在云计算环境中如何实现加密数据的高效分享是亟待解决的问题。

代理重加密（Proxy ReEncryption， PRE）是Blaze等[1]在1998年的欧洲密码学大会上为解决解密授权问题而提出的一种公钥加密体制。在代理重加密系统中，一个半可信的代理在获得由授权人产生的针对被授权人的重加密密钥后，能够将原本加密给授权人的密文转换为针对被授权人的密文，然后被授权人只需利用自己的私钥就可以解密转换后的密文。而在密文重加密的过程中，代理无法获得所处理密文对应明文的任何信息。利用代理重加密这一技术，能够有效地解决云计算环境中加密数据分享的问题：数据拥有者将针对指定用户的重加密密钥交给云计算提供者，后者将存储在云端的属于该数据拥有者的数据密文转换为针对指定用户的密文，然后该指定用户利用自身的私钥就可以解密这些重加密密文。近年来，代理重加密引起了密码学界的广泛关注，许多代理重加密方案被相继提出[2-9]。

已有的代理重加密方案大多基于传统公钥密码体制或基于身份密码体制，因此这些方案要么存在复杂的证书管理问题，要么存在密钥托管问题。为了解决已有代理重加密方案中存在的上述问题，Sur等[10]于2013年将代理重加密方法扩展到基于证书密码体制中，提出了基于证书代理重加密的概念。基于证书密码体制（CertificateBased Cryptography， CBC）由Gentry[11]在2003年的欧洲密码学大会上首次提出，是近年来颇受关注的一种新型公钥密码体制[12-18]。该体制有机结合了传统公钥密码体制和基于身份密码体制，并有效克服了这两种密码体制中一些固有的缺陷。基于证书代理重加密继承了基于证书密码体制的所有优良特性，不仅简化了传统公钥代理重加密中复杂的证书管理问题，而且解决了基于身份代理重加密中固有的密钥托管，为公共云中加密数据的高效分享提供了理想的方法。在文献[10]中，Sur等设计出了首个基于证书代理重加密方案，并在随机预言模型（Random Oracle Model， ROM）下证明了该方案满足选择密文安全性。最近，Li等[19]也提出了一个随机预言模型下可证明安全的基于证书代理重加密方案。然而，已有的基于证书代理重加密方案的构造严重地依赖双线性对运算，因此方案的效率不高。作为密码方案设计中的一个重要工具，双线性对运算有着良好的数学性质，即双线性。然而，相对于密码学领域的其他常用运算，双线性对的计算代价比较高。随着智能手机、平板电脑等计算受限或电量受限的移动用户终端在云计算环境中广泛应用，基于双线性对的密码方案的应用将受到限制。

本文提出了一个高效的、不依赖于双线性对的基于证书代理重加密方案，并在随机预言模型下基于计算性DiffieHellman（Computational DiffieHellman， CDH）问题的困难性证明了该方案对适应性选择密文攻击是不可区分的，即满足选择密文安全性。与已有的基于证书代理重加密方案[10，19]相比，本文方案在计算效率和通信带宽上具有明显的优势，更适用于计算受限、低通信带宽的应用环境。

2 基于证书代理重加密方案及其安全模型

2.1 基于证书代理重加密方案的定义

基于证书代理重加密方案由如下8个算法组成：

1）系统参数设置算法（Setup）。输入安全参数k，该算法生成并输出CA的主密钥msk和系统参数集params。CA将系统参数集params公开，而将主密钥msk保密。

2）用户密钥生成算法（UserKeyGen）。输入系统公开参数集params，该算法生成并输出用户U的私钥SKU和部分公钥pkU。

3）证书生成算法（Certify）。输入系统公开参数集params、CA的主密钥msk、用户U的身份IDU和部分公钥pkU，该算法生成并输出用户U的证书CertU和公钥PKU。通常，该算法由CA运行。

4）加密算法（Encrypt）。输入系统公开参数集params、明文M、数据发布方A的身份IDA和公钥PKA， 该算法生成并输出消息M的原始密文CA。该算法由数据发布方A运行。

5）重加密密钥生成算法（ReKeyGen）。输入系统公开参数集params、数据发布方A的身份IDA、私钥SKA和证书CertA、被授权方的身份IDB和公钥PKB，该算法生成并输出重加密密钥RKA→B。该算法由数据发布方A运行。

6）重加密算法（ReEncrypt）。输入系统公开参数集params、原始密文CA、重加密密钥RKA→B，该算法生成并输出重加密密文CB或无效标志。该算法由云端代理运行。

7）原始密文解密算法（Decrypt1）。输入系统公开参数集params、原始密文CA、数据发布方A的身份IDA、私钥SKA和证书CertA，该算法生成并输出明文M或无效标志。该算法由数据发布方A运行。

8）重加密密文解密算法（Decrypt2）。输入系统公开参数集params、重加密密文CB、数据发布方A的身份IDA和公钥PKA、被授权方B的身份IDB、私钥SKB和证书CertB，该算法生成并输出明文M或无效标志。该算法由被授权方B运行。

上述算法应满足如下的正确性约束：若CA=Encrypt（params， M， IDA， PKA），则M=Decrypt1（params， CA， IDA， SKA， CertA）；若RKA→B=ReKeyGen（params， IDA， SKA， CertA， IDB， PKB）且CB=ReEncrypt（params， CA， RKA→B），则M=Decrypt2（params， CB， IDA， PKA， IDB， SKB， CertB）。

2.2 基于证书密钥封装机制的安全模型

基于证书代理重加密方案的安全模型包含2类不同的敌手A1和A2[10，19]。第1类敌手A1模拟未经CA认证的用户，它不知道系统的主密钥，但可以询问任意用户的私钥以及除目标用户以外的任意用户的证书。第2类敌手A2则模拟拥有系统主密钥的恶意CA，它可以生成任意用户的证书，并可以询问除目标用户以外的任意用户的私钥。

基于证书代理重加密方案的选择密文安全性可通过如下两个敌手游戏INDCCA2Ⅰ和INDCCA2Ⅱ来定义。

2.2.1 游戏INDCCA2Ⅰ

1）系统参数设置。挑战者模拟算法Setup（k）生成系统主密钥msk和公开参数集params。挑战者保密主密钥msk并将公开参数集params输出给敌手A1。

2）第1阶段询问。在这一阶段中，敌手A1可以向挑战者适应性地作如下一系列询问。

用户产生询问 挑战者维护一个列表Luser用于记录用户的私钥、公钥和证书。列表Luser初始为空。敌手A1输入身份IDU，如果列表Luser中已存在相应的记录，挑战者则直接输出身份IDU对应的公钥PKU给敌手A1；否则，挑战者生成身份IDU对应的私钥SKU、公钥PKU和证书CertU，然后将结果保存在列表Luser中并输出公钥PKU给敌手A1。对于任意的身份IDU，规定敌手A1必须先对其进行用户产生询问，才可作下述的其他预言询问。

私钥询问 敌手A1输入身份IDU，挑战者从列表Luser中获取身份IDU对应的私钥SKU并输出给敌手A1。

证书询问 敌手A1输入身份IDU，挑战者从列表Luser中获取身份IDU对应的证书CertU并输出给敌手A1。

重加密密钥询问 敌手A1输入身份IDA和IDB，挑战者生成一个重加密密钥RKA→B，并将之输出给敌手A1。

重加密询问 敌手A1输入身份IDA和IDB以及一个原始密文CA，挑战者生成一个重加密密文CB，并将之输出给敌手A1。

解密询问 敌手A1输入身份IDU和一个密文CU，挑战者解密密文CU并将结果输出给敌手A1。

3）挑战阶段。敌手A1输出身份IDch以及2个等长的明文（M0， M1）进行挑战，限制是敌手A1在第1阶段询问中没有询问过身份IDch对应的证书。挑战者随机选择γ∈{0，1}，运行加密算法Encrypt（params， Mλ， IDch， PKch）生成Mλ的原始密文Cch，并将之作为挑战密文输出给敌手A1。

4）第2阶段询问。同第1阶段询问，限制是：敌手A1不可询问挑战身份IDch的证书；对于任意的身份IDU ≠ IDch，敌手A1不可对（IDch， IDU）作重加密密钥询问；敌手A1不可对（IDch， Cch）和（IDder， Cder）作解密询问，其中密文Cder是重加密询问（IDch， IDder， Cch）的输出。

5）猜测。敌手A1输出对γ的猜测γ′。如果γ=γ′，则称敌手A1赢得游戏。敌手A1获胜的优势定义为：

AdvINDCCA2A1= 2|Pr[γ=γ′]-1/2|

2.2.2 游戏INDCCA2Ⅱ

1）系统参数设置。挑战者模拟算法Setup（k）生成系统主密钥msk和公开参数集params。挑战者将主密钥msk和公开参数集params输出给敌手A2。

2）第1阶段询问。在这一阶段中，敌手A2可以向挑战者适应性地作如下一系列询问。

用户产生询问 挑战者维护一个列表Luser用于记录用户的私钥、公钥和证书。列表Luser初始为空。敌手A2输入身份IDU，如果列表Luser中已存在相应的记录，挑战者则直接输出身份IDU对应的公钥PKU给敌手A2；否则，挑战者生成身份IDU对应的私钥SKU、公钥PKU和证书CertU，然后将结果保存在列表Luser中并输出公钥PKU给敌手A2。

私钥询问 敌手A2输入身份IDU，挑战者从列表Luser中获取身份IDU对应的私钥SKU并输出给敌手A2。

重加密密钥询问 敌手A2输入身份IDA和IDB，挑战者生成一个重加密密钥RKA→B，并将之输出给敌手A2。

重加密询问 敌手A2输入身份IDA和IDB以及一个原始密文CA，挑战者生成一个重加密密文CB并将之输出给敌手A2。

解密询问 敌手A2输入身份IDU和一个密文CU，挑战者解密密文CU并将结果输出给敌手A2。

3）挑战阶段。敌手A2输出身份IDch以及2个等长的明文（M0， M1）进行挑战，限制是敌手A2在第1阶段询问中没有询问过身份IDch对应的私钥。挑战者随机选择γ∈{0，1}，运行加密算法Encrypt（params， Mγ， IDch， PKch）生成Mγ的原始密文Cch，并将之作为挑战密文输出给敌手A2。

4）第2阶段询问。同第1阶段询问，限制是：敌手A2不可询问挑战身份IDch的私钥；对于任意的身份IDU ≠ IDch，敌手A2不可对（IDch， IDU）作重加密密钥询问；敌手A2不可对（IDch， Cch）和（IDder， Cder）作解密询问，其中密文Cder是重加密询问（IDch， IDder， Cch）的输出。

4.2 性能评价

下面从计算代价和通信代价这两个方面来评价本文方法的性能。

表1给出了本文方案与文献[10，19]中基于证书代理重加密方案的性能对比。假设这方案中的双线性对为e： G×G→GT，其中GT为双线性目标群。表1中符号p、 eT、e和h分别表示双线对性运算、群GT中的指数运算、群G中的指数运算以及MaptoPoint杂凑函数运算，其系数表示该运算的次数。一般杂凑函数运算的计算代价忽略不计。

根据文献[20]中的度量数据（见表2），表3和表4进一步给出了本文方案与文献[10，19]中方案的详细对比，其中MNT/80和SS/80分别表示80比特的MNT（MiyajiNakabayashiTakano）椭圆曲线和80比特的超奇异椭圆（Super Singular， SS）曲线，可提供1024比特的RSA安全性。便于比较，假定三个方案加密时都使用SHA1杂凑函数，此时n和l的值为160。

由表3和表4可见，与文献[10，19]中方案相比，本文方案在计算代价和通信代价两个方面都具有明显的优势，更适用于计算受限且低通信带宽的应用场合。

5 结语

本文提出了一个高效的不依赖于双线性对的基于证书代理重加密方案。基于CDH问题的困难性假设，该方案在随机预言模型下被证明满足选择密文安全性。与已有的基于证书代理重加密方案相比较，本文方案具有计算效率高和通信代价低的优点，因此适用于计算受限且低通信带宽的应用场合。

已有的代理重加密方案只能针对唯一的被授权人产生重加密密钥和重加密密文。但在很多实际应用场合下，一个用户希望与多个用户同时分享其存储在云端的加密数据，那么授权人将不得不针对每一个被授权人生成重加密密钥，而云端代理也需要针对每一个被授权人生成相应的重加密密文。这不仅给授权人和代理带来了沉重的计算负担，同时也增加了授权人与代理之间的通信代价，因此，构造多接受者的基于证书代理重加密方案是下一步的工作重心。

参考文献：

[1]BLAZE M， BLEUMER G， STRAUSS M. Divertible protocols and atomic proxy cryptography [C]// Proceedings of the 1998 International Conference on the Theory and Application of Cryptographic Techniques. Berlin： Springer， 1998： 127-144.

[2]ATENIESE G， FU K， GREEN M， et al. Improved proxy reencryption schemes with applications to secure distributed storage[J]. ACM Transactions on Information and System Security， 2006， 9（1）： 1-30.

[3]CANETTI R， HOHENBERGER S. Chosenciphertext secure proxy reencryption[C]// Proceedings of the 14th ACM Conference on Computer and Communications Security. New York： ACM， 2007： 185-194.

[4]LIBERT B， VERGNAUD D. Unidirectional chosenciphertext secure proxy reencryption[C]// Proceedings of the 11th International Workshop on Practice and Theory in PublicKey Cryptography. Berlin： Springer， 2008： 360-379.

[5]SHAO J， CAO Z. CCAsecure proxy reencryption without pairings [C]// Proceedings of the 12th International Workshop on Practice and Theory in PublicKey Cryptography. Berlin： Springer， 2009： 357-376.

[6]GREEN M， ATENIESE G. Identitybased proxy reencryption[C]// Proceedings of the 5th International Conference on Applied Cryptography and Network Security. Berlin： Springer， 2007： 288-306.

[7]MATSUO T. Proxy reencryption systems for identitybased encryption[C]// Proceedings of the 1st International Conference on PairingBased Cryptography. Berlin： Springer， 2007： 247-267.

[8]LUO S， SHEN Q， CHEN Z. Fully secure unidirectional identitybased proxy reencryption[C]// Proceedings of the 14th Annual International Conference on Information Security and Cryptology. Berlin： Springer， 2012： 109-126.

[9]LIANG K， LIU J K， WONG D S， et al. An efficient cloudbased revocable identitybased proxy reencryption scheme for public clouds data sharing[C]// Proceedings of the 19th European Symposium on Research in Computer Security. Berlin： Springer， 2014： 257-272.

[10]SUR C， PARK Y， SHIN S U， et al. Certificatebased proxy reencryption for public cloud storage[C]// Proceedings of the 7th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing. Piscataway， NJ： IEEE， 2013： 159-166.

[11]GENTRY C. Certificatebased encryption and the certificate revocation problem[C]// Proceedings of 2003 International Conference on the Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2003： 272-293.

[12]WANG L， SHAO J， CAO Z， et al. A certificatebased proxy cryptosystem with revocable proxy decryption power[C]// Proceedings of the 8th International Conference on Cryptology in India. Berlin： Springer， 2007： 297-311.

[13]GALINDO D， MORILLO P， RFOLS C. Improved certificatebased encryption in the standard model[J]. Journal of Systems and Software， 2008， 81（7）： 1218-1226.

[14]LIU J K， ZHOU J Y. Efficient certificatebased encryption in the standard model[C]// Proceedings of the 6th International Conference on Security and Cryptography for Networks. Berlin： Springer， 2008： 144-155.

[15]LU Y， LI J G， XIAO J M. Constructing efficient certificatebased encryption with pairing[J]. Journal of Computers， 2009， 4（1）： 19-26.

[16]SHAO Z. Enhanced certificatebased encryption from pairings [J]. Computers & Electrical Engineering， 2011， 37（2）： 136-146.

[17]YAO J， LI J G， ZHANG Y. Certificatebased encryption scheme without pairing[J]. KSII Transactions on Internet and Information Systems， 2013， 7（6）： 1480-1491.

[18]LU Y， LI J G. Efficient construction of certificatebased encryption secure against public key replacement attacks in the standard model[J]. Journal of Information Science and Engineering， 2014， 30（5）： 1553-1568.

[19]LI J G， ZHAO X， ZHANG Y. Certificatebased conditional proxy reencryption[C]// Proceedings of the 8th International Conference on Network and System Security. Berlin： Springer， 2014： 299-310.

[20]BOYEN X. The BB1 identitybased cryptosystem： a standard for encryption and key encapsulation [EB/OL]. [2015-06-10].