基于RLWE的密文策略属性代理重加密

张恩，裴瑶瑶，杜蛟



基于RLWE的密文策略属性代理重加密

张恩1,2，裴瑶瑶1,2，杜蛟3

（1. 河南师范大学计算机与信息工程学院，河南 新乡 453007； 2. “智慧商务与物联网技术”河南省工程实验室，河南 新乡 453007； 3. 河南师范大学数学与信息科学学院，河南 新乡 453007）

针对现有基于LWE的代理重加密方案存在无法实现细粒度访问及效率低的问题，结合线性秘密共享方案、RLWE和属性加密，提出一种密文策略属性代理重加密方案。该方案可以缩短密钥尺寸、减小密文空间、提高加解密效率，同时利用线性秘密共享矩阵作为访问矩阵，满足授权人细粒度委托控制的需求，抵抗代理服务器和被授权人之间的合谋。安全分析表明，在基于RLWE假设的标准模型下，所提方案是安全的。

代理重加密；RLWE；属性加密；线性秘密共享方案；细粒度访问

1 引言

云计算作为一种新兴的服务模式，采用负载均衡、分布式计算等技术，能够方便地为远程用户提供计算和存储功能，从而节省本地开销、提高资源利用率。云计算的出现改变了人们共享数据、信息和知识的方式。借助于云平台的超大存储空间和快速计算能力，人们可以通过网络实时快捷地存储、查询和共享数据。但是当用户向云平台上传数据时，这些数据处于用户不可控范围。如何实现数据的安全共享已成为当前重要的安全问题，而代理重加密为该问题提供了一种有效的解决方法。

在1998年的欧洲密码学年会上，Blaze等[1]首次提出代理重加密的概念。典型的代理重加密方案涉及三方：代理授权人（Alice）、被授权人（Bob）和代理服务器。在代理重加密的过程中，代理授权人（Alice）生成一个代理重加密键，并将其发送给代理服务器。代理服务器可以把代理授权人（Alice）公钥加密的密文转换成被授权人（Bob）公钥对同一明文加密的密文。被授权人（Bob）可以用自己的私钥来恢复加密的消息，而不需要知道授权人的私钥信息。同时，代理服务器并未得到有关数据的明文信息，从而保证了数据的安全性。

一般来说，根据密文转换方向，可将代理重加密分为单向代理重加密和双向代理重加密。单向代理重加密仅能实现A到B的密文转换，而双向代理重加密不仅能实现A到B的密文转换，还可以实现B到A的密文转换。Blaze等[1]首先构造了一种双向代理重加密方案，但该方案在抵抗合谋攻击方面存在一定的问题。Ivan等[2]提出单向代理重加密方案的通用方法，但无法保证其安全性。Ateniese等[3]首次基于双线性对设计出一种单向代理重加密方案并给出安全模型。但是，以上方案都无法抵抗选择明文攻击。Canetti等[4]和Libert等[5]分别构建了CCA安全的双向代理重加密和单向代理重加密方案。

随着身份加密和属性加密的出现，人们将代理重加密分别与身份加密和属性加密相结合，对代理重加密进行了扩展。2005年，Sahai等[6]提出模糊的基于身份加密的机制（FIBE），但该机制仅能支持门限访问控制策略。为了实现灵活的访问控制，Goyal等[7]在2006年首次提出密钥策略属性加密（KP-ABE）方案，Bethencourt等[8]提出了密文策略属性加密（CP-ABE）方案。Jin等[9]对CP-ABE方案进行改进，提出一种安全的隐藏明文策略的属性加密方案，有效地避免访问策略中敏感信息的泄露。2007年，Green等[10]将代理重加密与身份加密相结合，首次提出了基于身份的代理重加密（ID-PRE）概念。Liang等[11]对ID-PRE方案进行改进，率先设计出基于属性的代理重加密（AB-PRE）方案。Weng等[12]首次提出了条件代理重加密的概念。Luo等[13]提出了一种单向非交互的基于密文策略属性代理重加密方案。Seo等[14]构造出一种高效的基于属性的代理重加密（AB-PRE）方案。Wungpornpaiboon等[15]基于密文策略的属性加密，提出一种支持个人电子医疗记录代理的两层代理重加密方案，其内层的策略由数据拥有者控制，外层的策略由代理者控制。Liang等[16]对文献[11]进行了改进，使基于属性的代理重加密（AB-PRE）方案满足选择明文攻击安全。Xu等[17]提出了一种基于CP-ABE的多授权的属性代理重加密方案，解决CP-ABE方案中密钥分发和撤销用户访问权限时存在的安全问题。

然而，上述代理重加密方案均是基于经典密码学困难问题构造的，这些加密方案随着量子计算机的应用已变得不再安全。近年来，密码学者致力于设计安全、高效且能够有效抵御量子攻击的密码体系。格密码的出现为研究者提供了新的方法。2005年，Regev等[18]提出了一个新的格上困难问题——带误差的学习（LWE），并且证明它与格中最坏情况下的SVP问题是一样困难的。到目前为止，尚没有多项式时间量子算法能够破解格困难问题，而因子分解和离散对数问题可以通过Shor算法[19]在多项式时间内求解。Ajtai等[20]发现，即使在最坏情况下，基于格困难问题的格密码系统也是非常安全的。

研究者根据格上的LWE问题设计出基于身份的加密方案[21-22]、基于属性的加密方案[23]以及基于密钥策略属性加密方案[24]。Kirshanova[25]和Fan等[26]分别基于LWE问题，提出了格上的代理重加密方案。Singh等[27]将格上身份加密和代理重加密相结合，提出了一种基于身份的代理重加密方案。Kim等[28]基于最坏情况下的格困难问题，提出了一种基于格上的抗合谋单向代理重加密方案，并且证明了该方案在随机预言模型下是安全的。Jiang等[29]提出了格上基于多用户的单向代理重加密方案。张恩等[30]将声誉系统和基于LWE的对称代理重加密相结合，提出一个基于声誉系统的服务器辅助的隐私集合交集协议。Li等[31]基于LWEE（learning with errors in the exponent）概念提出了一种单比特单跳单向的代理重加密方案，解决基于LWE构造的代理重加密方案存在的噪声扩散问题。然而，基于格上LWE问题构造的代理重加密方案存在密钥尺寸过长、密文空间较大、效率较低的问题。2010年，Lyubashevsky等[32]对LWE问题进行改进，提出了RLWE问题，减小了密钥的尺寸。随后，Tan等[33]在2015年提出基于RLWE密文策略属性加密体制。孙泽栋等[34]在2016年提出一种基于RLWE密钥策略属性加密体制。郑永辉等[35]设计一种环上基于属性的全同态加密体制的方案。张恩等[36]在RLWE困难问题的基础上，提出了抗隐蔽敌手的云外包秘密共享方案。Polyakov等[37]基于RLWE的密钥交换，对NTRU-RLWE同态加密方案和BV同态加密方案进行改进，分别提出了NTRU-ABD-PRE方案和BV-PRE方案，但是这两种方案都无法实现细粒度的代理控制。目前尚没有基于RLWE的属性代理重加密方案。

为了解决现有基于LWE的代理重加密方案存在的加解密效率较低、无法实现细粒度访问的问题，本文在Tan方案[33]的基础上，提出一种基于RLWE的密文策略属性代理重加密方案，能够减小密钥尺寸、提高加解密效率、实现细粒度访问、抵抗代理者和授权者之间的合谋，达到抵御量子攻击的目的。本文所提方案具有以下特点。1) 细粒度访问控制。方案利用属性集合构造的访问结构来控制被授权人，被授权人可以为一个人、一个组织或多个组织，实现灵活的代理重加密。当且仅当被授权人的属性集合符合授权人设置的访问结构时，被授权人才能解密出密文。2) 高效性。和基于LWE的代理重加密方案相比，本文所提方案能够缩短密钥的尺寸、减小密文空间、节省内存资源、实现高效加解密运算。3) 防合谋。本文所提方案利用线性秘密共享方案来构造代理重加密键，使代理服务器通过代理重加密键无法获得授权者和被授权者的私钥信息，同时也能抵抗代理服务器与被授权者之间的合谋。4) 抗量子攻击。本文所提方案是基于格上的判定性RLWE问题构造的，借助于格的多维特点和格上的困难问题，使其在多项式量子算法内无法被攻破，提高了安全性，实现了抵御量子攻击的目的。

2 基础知识

2.1 格

2.2 访问结构和线性秘密共享

定义9 线性秘密共享方案（LSSS, linear secret sharing schemes）。基于一组属性集合上的线性秘密共享方案Π具有以下特性。

1) 每一个属性关于秘密的子份额形成一个向量。

2.3 CP-ABPRERLWE方案的系统定义及安全模型

一个基于RLWE的密文策略属性代理重加密（CP-ABPRERLWE）方案由下述6个多项式算法构成。

1) Setup（）：输入安全参数，通过安全参数构造一个多项式环，定义一个属性域，输出主公钥和主私钥。

5) KeyGen(,)：输入主私钥和被授权人的属性集合，输出被授权人私钥。

定义10 CP-ABPRERLWE的安全模型。一个基于RLWE的密文策略属性代理重加密方案的安全模型可以通过以下游戏来描述。

3 方案描述

本文基于线性秘密共享方案和RLWE，将代理重加密和属性加密相结合，提出了一种基于RLWE的密文策略属性代理重加密方案。具体方案如下。

4 方案分析

4.1 正确性分析

4.2 安全性分析

4.3 性能比较

首先，将文献[1,9,11,27-28,37]方案和所提方案进行比较，如表1所示。同时，将文献[25-26,28-29]方案和所提方案产生的密钥尺寸进行对比，如表2所示。最后，对方案进行仿真，分别如图1和图2所示。

表1 方案比较

图1 公钥产生的时间

图2 私钥产生的时间

表2 密钥尺寸对比

文献[1,9,27-28,37]方案不支持门限访问策略，不能实现细粒度的访问控制；而对于文献[11]，虽能实现细粒度的访问控制，但该访问结构仅能支持与门限。为了更细粒度地控制被授权人，所提方案基于RLWE问题，将密文策略属性加密、线性秘密共享和代理重加密相结合，提出了一个支持与和或门限的代理重加密方案。同时，所提方案利用线性秘密共享方案来构造代理重加密键，代理服务器和被授权者合谋无法得到授权者的私钥信息，解决了代理服务器与被授权者之间的合谋问题。

基于传统密码学困难问题构造的代理重加密方案[1,9,11]在大素数或椭圆双曲线性环境下进行操作，计算复杂、效率低下。而基于LWE问题构造的代理重加密方案[25-26,28-29]在小整数范围内对矩阵进行操作，可以实现并行计算，但存在密钥尺寸较大的问题。所提方案基于LWE的变体RLWE这一特殊的代数结构进行构造。根据定义5和定义6可知，在LWE分布中随机均匀选取的和为向量，而在RLWE分布中随机均匀选取的和为常数。由于和选取形式的不同，使基于RLWE和基于LWE构造的公钥和私钥的尺寸不同。基于LWE构造的公钥和私钥为矩阵，且尺寸大小为(2)，而基于RLWE构造的公钥和私钥为向量，尺寸大小为()。和基于LWE构造的方案相比，所提方案基于RLWE构造，可以缩短公钥和私钥尺寸、减小密文的空间，从而降低加解密复杂度。表2为在相同参数条件下所提方案和文献[25-26,28-29]方案的密钥尺寸的比较。同时，本文在处理器为Intel Core i7 @ 3.4 GHz的Lenovo Ghost win7 x64上采用python2.7对方案进行仿真，在不同参数条件下（=128, 256, 512, 1 024, 2 048），测试基于RLWE和基于LWE产生公钥和私钥的时间，结果如图1和图2所示。由图1和图2可知，基于RLWE产生公钥和私钥时间明显小于基于LWE产生公钥和私钥的时间。同时，随公钥参数和私钥参数的增加，基于RLWE产生的公钥和私钥的时间呈线性增长，而基于LWE产生的公钥和私钥时间呈指数增长。

5 结束语

随着云计算的高速发展，数据共享成为研究的热点，代理重加密受到广泛的关注。但基于LWE的代理重加密方案存在效率低、无法实现细粒度的访问等问题。本文结合RLWE、线性秘密共享和属性加密，提出一种密文策略的属性代理重加密方案。该方案可以缩短密钥尺寸、减小密文空间、提高加解密效率。同时，本文将代理重加密和密文策略属性加密相结合，对被授权人（被授权人可以为一个人、一个组织或多个人）进行细粒度的访问控制，达到抵御量子攻击的目的。安全分析表明，在基于RLWE困难问题的标准模型下，所提方案是安全的。

[1] BLAZE M, BLEUMER G, STRAUSS M. Divertible protocols and atomic proxy cryptography[C]//Advances in Cryptology EUROCRYPT. 1998: 127-144.

[2] IVAN A A, DODIS Y. Proxy cryptography revisited[C]//Network and Distributed System Security Symposium. 2003.

[3] ATENIESE G, FU K, GREEN M, et al. Improved proxy re-encryption schemes with applications to secure distributed storage[J]. ACM Transactions on Information and System Security (TISSEC), 2006, 9(1): 1-30.

[4] CANETTI R, HOHENBERGER S. Chosen-ciphertext secure proxy re-encryption[C]//The 14th ACM Conference on Computer and Communications Security. 2007: 185-194.

[5] LIBERT B, VERGNAUD D. Unidirectional chosen-ciphertext secure proxy re-encryption[C]//International Workshop on Public Key Cryptography. 2008: 360-379.

[6] SAHAI A, WATERS B. Fuzzy identity-based encryption[C]//International Conference on the Theory and Applications of Cryptographic Techniques. 2005: 457-473.

[7] GOYAL V, PANDEY O, SAHAI A, et al. Attribute-based encryption for fine-grained access control of encrypted data[C]//The 13th ACM Conference on Computer and Communications Security. 2006: 89-98.

[8] BETHENCOURT J, SAHAI A, WATERS B. Ciphertext-policy attribute-based encryption[C]//IEEE Symposium on Security and Privacy. 2007: 321-334.

[9] GREEN M, ATENIESE G. Identity-based proxy re-encryption[C]// Applied Cryptography and Network Security. 2007: 288-306.

[10] JIN C C, FENG X Y, SHEN Q N. Fully secure hidden ciphertext policy attribute-based encryption with short ciphertext size[C]//The 6th International Conference on Communication and Network Security. 2016: 91-98.

[11] LIANG X, CAO F Z, LIN H, et al. Attribute based proxy re-encryption with delegating capabilities[C]//The 4th International Symposium on Information, Computer, and Communications Security. 2009: 276-286.

[12] WENG J, DENG R H, DING X, et al. Conditional proxy re-encryption secure against chosen-ciphertext attack[C]//The 4th International Symposium on Information, Computer, and Communications Security. 2009: 322-332.

[13] LUO S, HU J, CHEN Z. Ciphertext policy attribute-based proxy re-encryption[C]//Information and Communications Security. 2010: 401-415.

[14] SEO H. J, KIM H. Attribute-based proxy re-encryption with a constant number of pairing operations[J]. Journal of Information and Communication Convergence Engineering, 2012, 10(1): 53-60.

[15] WUNGPORNPAIBOON G, VASUPONGAYYA S. Two-layer ciphertext-policy attribute-based proxy re-encryption for supporting PHR delegation[C]//Computer Science and Engineering Conference. 2016: 1-6.

[16] LIANG K, FANG L, SUSILO W, et al. A ciphertext-policy attribute-based proxy re-encryption with chosen-ciphertext security[C]//The 5th International Conference on Intelligent Networking and Collaborative Systems. 2013: 552-559.

[17] XU X L, ZHOU J L, WANG X H, et al. Multi-authority proxy re-encryption based on CPABE for cloud storage systems[J]. Journal of Systems Engineering and Electronics, 2016, 27(1): 211-223.

[18] REGEV O. On lattices,learning with errors, random linear codes, and cryptography[C]//The 37th Annual ACM Symposium on Theory of Computing (STOC’05). 2005: 84-93.

[19] SHOR P W. Polynomial-time algorithms for prime factorizetion and discrete logarithms on a quantum computer[J]. SIAM Review, 1999, 41(2): 303-332.

[20] AJTAI M.Generating hard instances of lattice problems[C]//The 28th Annual ACM Symposium on Theory of Computing. 1996: 99-108.

[21] GENTRY C, PEIKERT C, VAIKUNTANATHAN V. Trapdoors for hard lattices and new cryptographic constructions [C]//The 40th Annual ACM Symposium on Theory of Computing. 2008: 197-206.

[22] AGRAWAL S, BOYEN X, VAIKUNTANATHAN V, et al.Fuzzy identity based encryption from lattices[J].IACR Cryptology ePrint Archive, 2011: 414.

[23] BOYEN X. Attribute-based functional encryption on lattices[J]. Lecture Notes in Computer Science: Theory of Cryptography, 2013, 7785: 122-142.

[24] DAN B, GENTRY C, GORBUNOV S, et al. Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2014: 533-556.

[25] KIRSHANOVA E. Proxy re-encryption from lattices[C]//Public Key Cryptography. 2014: 77-94.

[26] FAN X, LIU F H. Various proxy re-encryption schemes from lattices[J]. IACR Cryptology ePrint Archive, 2016: 278.

[27] SINGH K, RANGAN C P, BANERJEE A K. Lattice based identity based proxy re-encryption scheme[J]. Journal of Internet Services and Infor- mation Security, 2013, 3(3/4): 38-51.

[28] KIM K S, JEONG I R. Collusion-resistant unidirectional proxy re-encryption scheme from lattices[J]. Journal of Communications and Networks, 2016, 18(1): 1-7.

[29] JIANG M M, HU Y P, WANG B C, et al. Lattice-based multiuse unidirectional proxy re-encryption[J]. Security and Communication Networks, 2015, 8(18): 3796-3803.

[30] ZHANG E, LI F, NIU B, et al. Server-aided private set intersection based on reputation[J]. Information Sciences, 2017, 387: 180-194.

[31] LI Z P, MA C G, WANG D, et al. Toward proxy re-encryption from learning with errors in the exponent[C]//Trustcom/BigDataSE/ICESS. 2017: 683-690.

[32] LYUBASHEVSKY V, PEIKERT C, REGEV O. On ideal lattices and learning with errors over rings[C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2010: 1-23.

[33] TAN S F, SAMSUDIN A. Lattice ciphertext-policy attribute-based encryption from ring-LWE[C]//International Symposium on Technology Management and Emerging Technologies. 2015: 258-262.

[34] 孙泽栋, 祝跃飞, 顾纯祥, 等. 基于RLWE的密钥策略属性加密体制[J]. 通信学报, 2016, 37(S1): 125-131.

SUN Z D, ZHU Y F, GU C X, et al. RLWE-based key-policy ABE scheme[J]. Journal on Communications, 2016, 37(S1): 125-131.

[35] 郑永辉, 康元基, 顾纯祥, 等. 环上基于属性的全同态加密体制设计[J]. 通信学报, 2017, 38(4): 55-63.

ZHENG Y H, KANG Y J, GU C X, et al. Attribute-based fully homomorphic encryption scheme over rings [J]. Journal on Communications, 2017, 38(4): 55-63.

[36] 张恩, 耿魁, 金伟, 等. 抗隐蔽敌手的云外包秘密共享方案[J]. 通信学报, 2017, 38(5): 57-65.

ZHANG E, GENG K, JIN W, et al. Cloud outsourcing secret sharing scheme against covert adversaries[J]. Journal on Communications, 2017, 38(5): 57-65.

[37] POLYAKOV Y, KURT R.Fast proxy re-encryption for publish/subscribe systems[J].ACM Transactions on Privacy and Security, 2017, 20(4): 1-31.

RLWE-based ciphertext-policy attribute proxy re-encryption

ZHANG En1,2, PEI Yaoyao1,2, DU Jiao3

1. College of Computer and Information Engineering, Henan Normal University, Xinxiang 453007, China 2. Engineering Lab of Intelligence Bussiness & Internet of Things of Henan Province, Xinxiang 453007, China 3. College of Mathematics and Information Science, Henan Normal University, Xinxiang 453007, China

To solve LWE-based proxy re-encryption schemes cannot achieve fine-grained access and low efficiency problem, a ciphertext-policy attribute-based proxy re-encryption scheme was proposed. The scheme based on linear secret sharing scheme, RLWE and attribute encryption could shorten the key size, reduce the ciphertext space and improve the efficiency of encryption and decryption. At the same time, the linear secret sharing matrix was used as an access matrix to meet the requirements of authorized person fine-grained commissioning control and to resist the collusion between the agent and the authorized person. In addition, the proposed scheme is shown to be secure under the ring learning with errors assumption in the standard model.

proxy re-encryption, RLWE, attribute encryption, linear secret sharing scheme, fine-grained access

TP309.2

A

10.11959/j.issn.1000-436x.2018239

张恩（1974−），男，河南新乡人，博士，河南师范大学副教授、硕士生导师，主要研究方向为密码协议、隐私保护、云计算安全。

裴瑶瑶（1992−），男，河南南阳人，河南师范大学硕士生，主要研究方向为密码协议。

杜蛟（1978−），男，湖北英山人，博士，河南师范大学讲师，主要研究方向为密码学与应用数学。

2018−01−11；

2018−05−19

张恩，zhangenzdrj@163.com

国家自然科学基金资助项目（No.U1604156, No.61772176, No.61602158）；河南省科技攻关计划基金资助项目（No.172102210045）

The National Natural Science Foundation of China (No.U1604156, No.61772176, No.61602158), The Science and Technology Research Project of Henan Province (No.172102210045)