基于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)