高效無雙線性對的基于證書代理重加密方案

徐海琳 陳鶯 陸陽

摘要：針對已有基于證書代理重加密（PRE）方案需要復雜的雙線性對運算，計算效率較低的問題，提出了一個高效的不依賴于雙線性對的基于證書代理重加密方案?；谟嬎阈訢iffieHellman（CDH）問題的困難性假設，該方案在隨機預言模型下被嚴格證明滿足適應性選擇密文攻擊下的不可區(qū)分安全性，即滿足選擇密文安全性。所提方案的構造基于橢圓曲線群，避免了計算開銷高昂的雙線性對運算，因此方案的計算性能得到了顯著提高。對比分析表明，相對于已有使用雙線性對的基于證書代理重加密方案，所提方案在計算效率和通信代價兩個方面都具有明顯的優(yōu)勢，更適用于計算受限以及低通信帶寬的應用場合。

關鍵詞：公共云；基于證書代理重加密；橢圓曲線；隨機預言模型；選擇密文安全性

中圖分類號：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 引言

云計算是近年來互聯(lián)網(wǎng)領域發(fā)展的熱點，它旨在通過計算機網(wǎng)絡把多個成本相對較低的計算實體整合成一個具有強大計算能力的完美系統(tǒng)， 搭建高可擴展性、超大規(guī)模、高可用性以及低廉成本的云計算平臺已經(jīng)成為當前信息化建設的方向。作為云計算最廣泛的應用，云存儲為廣大用戶帶來方便性的同時，也造成了數(shù)據(jù)所有權和管理權分離的問題。當用戶使用云計算環(huán)境時，需要將數(shù)據(jù)存儲至云端并依靠云服務提供者處理數(shù)據(jù)，這使得數(shù)據(jù)脫離了用戶的控制。由于用戶數(shù)據(jù)中含有隱私敏感信息，因此需要有合適的機制來保障存儲在云端的用戶數(shù)據(jù)不被非授權訪問。密文訪問控制是云存儲模式下實現(xiàn)用戶數(shù)據(jù)機密性和訪問控制的重要方法，該方法要求數(shù)據(jù)擁有者將數(shù)據(jù)加密后存放在云端。為了解決加密數(shù)據(jù)分發(fā)或分享的問題，一些密文訪問控制方法采用了密鑰分發(fā)的方法，即數(shù)據(jù)擁有者通過保密的方式將解密密鑰發(fā)送給授權用戶。在這種情況下，需要針對不同的訪問控制單元使用不同的密鑰加密數(shù)據(jù)，顯然這會造成數(shù)據(jù)的重復加密，從而浪費大量的計算資源和存儲資源。另一類解決方法則需要數(shù)據(jù)擁有者從云端取回加密數(shù)據(jù)，解密后再使用被授權用戶的公鑰對數(shù)據(jù)重新加密并發(fā)送給被授權用戶，顯然這會給數(shù)據(jù)擁有者帶來嚴重的計算和通信開銷，從而降低系統(tǒng)整體效率。因此，在云計算環(huán)境中如何實現(xiàn)加密數(shù)據(jù)的高效分享是亟待解決的問題。

代理重加密（Proxy ReEncryption， PRE）是Blaze等[1]在1998年的歐洲密碼學大會上為解決解密授權問題而提出的一種公鑰加密體制。在代理重加密系統(tǒng)中，一個半可信的代理在獲得由授權人產(chǎn)生的針對被授權人的重加密密鑰后，能夠將原本加密給授權人的密文轉換為針對被授權人的密文，然后被授權人只需利用自己的私鑰就可以解密轉換后的密文。而在密文重加密的過程中，代理無法獲得所處理密文對應明文的任何信息。利用代理重加密這一技術，能夠有效地解決云計算環(huán)境中加密數(shù)據(jù)分享的問題：數(shù)據(jù)擁有者將針對指定用戶的重加密密鑰交給云計算提供者，后者將存儲在云端的屬于該數(shù)據(jù)擁有者的數(shù)據(jù)密文轉換為針對指定用戶的密文，然后該指定用戶利用自身的私鑰就可以解密這些重加密密文。近年來，代理重加密引起了密碼學界的廣泛關注，許多代理重加密方案被相繼提出[2-9]。

已有的代理重加密方案大多基于傳統(tǒng)公鑰密碼體制或基于身份密碼體制，因此這些方案要么存在復雜的證書管理問題，要么存在密鑰托管問題。為了解決已有代理重加密方案中存在的上述問題，Sur等[10]于2013年將代理重加密方法擴展到基于證書密碼體制中，提出了基于證書代理重加密的概念?；谧C書密碼體制（CertificateBased Cryptography， CBC）由Gentry[11]在2003年的歐洲密碼學大會上首次提出，是近年來頗受關注的一種新型公鑰密碼體制[12-18]。該體制有機結合了傳統(tǒng)公鑰密碼體制和基于身份密碼體制，并有效克服了這兩種密碼體制中一些固有的缺陷?；谧C書代理重加密繼承了基于證書密碼體制的所有優(yōu)良特性，不僅簡化了傳統(tǒng)公鑰代理重加密中復雜的證書管理問題，而且解決了基于身份代理重加密中固有的密鑰托管，為公共云中加密數(shù)據(jù)的高效分享提供了理想的方法。在文獻[10]中，Sur等設計出了首個基于證書代理重加密方案，并在隨機預言模型（Random Oracle Model， ROM）下證明了該方案滿足選擇密文安全性。最近，Li等[19]也提出了一個隨機預言模型下可證明安全的基于證書代理重加密方案。然而，已有的基于證書代理重加密方案的構造嚴重地依賴雙線性對運算，因此方案的效率不高。作為密碼方案設計中的一個重要工具，雙線性對運算有著良好的數(shù)學性質，即雙線性。然而，相對于密碼學領域的其他常用運算，雙線性對的計算代價比較高。隨著智能手機、平板電腦等計算受限或電量受限的移動用戶終端在云計算環(huán)境中廣泛應用，基于雙線性對的密碼方案的應用將受到限制。

本文提出了一個高效的、不依賴于雙線性對的基于證書代理重加密方案，并在隨機預言模型下基于計算性DiffieHellman（Computational DiffieHellman， CDH）問題的困難性證明了該方案對適應性選擇密文攻擊是不可區(qū)分的，即滿足選擇密文安全性。與已有的基于證書代理重加密方案[10，19]相比，本文方案在計算效率和通信帶寬上具有明顯的優(yōu)勢，更適用于計算受限、低通信帶寬的應用環(huán)境。

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

2.1 基于證書代理重加密方案的定義

基于證書代理重加密方案由如下8個算法組成：

1）系統(tǒng)參數(shù)設置算法（Setup）。輸入安全參數(shù)k，該算法生成并輸出CA的主密鑰msk和系統(tǒng)參數(shù)集params。CA將系統(tǒng)參數(shù)集params公開，而將主密鑰msk保密。

2）用戶密鑰生成算法（UserKeyGen）。輸入系統(tǒng)公開參數(shù)集params，該算法生成并輸出用戶U的私鑰SKU和部分公鑰pkU。

3）證書生成算法（Certify）。輸入系統(tǒng)公開參數(shù)集params、CA的主密鑰msk、用戶U的身份IDU和部分公鑰pkU，該算法生成并輸出用戶U的證書CertU和公鑰PKU。通常，該算法由CA運行。

4）加密算法（Encrypt）。輸入系統(tǒng)公開參數(shù)集params、明文M、數(shù)據(jù)發(fā)布方A的身份IDA和公鑰PKA， 該算法生成并輸出消息M的原始密文CA。該算法由數(shù)據(jù)發(fā)布方A運行。

5）重加密密鑰生成算法（ReKeyGen）。輸入系統(tǒng)公開參數(shù)集params、數(shù)據(jù)發(fā)布方A的身份IDA、私鑰SKA和證書CertA、被授權方的身份IDB和公鑰PKB，該算法生成并輸出重加密密鑰RKA→B。該算法由數(shù)據(jù)發(fā)布方A運行。

6）重加密算法（ReEncrypt）。輸入系統(tǒng)公開參數(shù)集params、原始密文CA、重加密密鑰RKA→B，該算法生成并輸出重加密密文CB或無效標志。該算法由云端代理運行。

7）原始密文解密算法（Decrypt1）。輸入系統(tǒng)公開參數(shù)集params、原始密文CA、數(shù)據(jù)發(fā)布方A的身份IDA、私鑰SKA和證書CertA，該算法生成并輸出明文M或無效標志。該算法由數(shù)據(jù)發(fā)布方A運行。

8）重加密密文解密算法（Decrypt2）。輸入系統(tǒng)公開參數(shù)集params、重加密密文CB、數(shù)據(jù)發(fā)布方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模擬未經(jīng)CA認證的用戶，它不知道系統(tǒng)的主密鑰，但可以詢問任意用戶的私鑰以及除目標用戶以外的任意用戶的證書。第2類敵手A2則模擬擁有系統(tǒng)主密鑰的惡意CA，它可以生成任意用戶的證書，并可以詢問除目標用戶以外的任意用戶的私鑰。

基于證書代理重加密方案的選擇密文安全性可通過如下兩個敵手游戲INDCCA2Ⅰ和INDCCA2Ⅱ來定義。

2.2.1 游戲INDCCA2Ⅰ

1）系統(tǒng)參數(shù)設置。挑戰(zhàn)者模擬算法Setup（k）生成系統(tǒng)主密鑰msk和公開參數(shù)集params。挑戰(zhàn)者保密主密鑰msk并將公開參數(shù)集params輸出給敵手A1。

2）第1階段詢問。在這一階段中，敵手A1可以向挑戰(zhàn)者適應性地作如下一系列詢問。

用戶產(chǎn)生詢問 挑戰(zhàn)者維護一個列表Luser用于記錄用戶的私鑰、公鑰和證書。列表Luser初始為空。敵手A1輸入身份IDU，如果列表Luser中已存在相應的記錄，挑戰(zhàn)者則直接輸出身份IDU對應的公鑰PKU給敵手A1；否則，挑戰(zhàn)者生成身份IDU對應的私鑰SKU、公鑰PKU和證書CertU，然后將結果保存在列表Luser中并輸出公鑰PKU給敵手A1。對于任意的身份IDU，規(guī)定敵手A1必須先對其進行用戶產(chǎn)生詢問，才可作下述的其他預言詢問。

私鑰詢問 敵手A1輸入身份IDU，挑戰(zhàn)者從列表Luser中獲取身份IDU對應的私鑰SKU并輸出給敵手A1。

證書詢問 敵手A1輸入身份IDU，挑戰(zhàn)者從列表Luser中獲取身份IDU對應的證書CertU并輸出給敵手A1。

重加密密鑰詢問 敵手A1輸入身份IDA和IDB，挑戰(zhàn)者生成一個重加密密鑰RKA→B，并將之輸出給敵手A1。

重加密詢問 敵手A1輸入身份IDA和IDB以及一個原始密文CA，挑戰(zhàn)者生成一個重加密密文CB，并將之輸出給敵手A1。

解密詢問 敵手A1輸入身份IDU和一個密文CU，挑戰(zhàn)者解密密文CU并將結果輸出給敵手A1。

3）挑戰(zhàn)階段。敵手A1輸出身份IDch以及2個等長的明文（M0， M1）進行挑戰(zhàn)，限制是敵手A1在第1階段詢問中沒有詢問過身份IDch對應的證書。挑戰(zhàn)者隨機選擇γ∈{0，1}，運行加密算法Encrypt（params， Mλ， IDch， PKch）生成Mλ的原始密文Cch，并將之作為挑戰(zhàn)密文輸出給敵手A1。

4）第2階段詢問。同第1階段詢問，限制是：敵手A1不可詢問挑戰(zhàn)身份IDch的證書；對于任意的身份IDU ≠ IDch，敵手A1不可對（IDch， IDU）作重加密密鑰詢問；敵手A1不可對（IDch， Cch）和（IDder， Cder）作解密詢問，其中密文Cder是重加密詢問（IDch， IDder， Cch）的輸出。

5）猜測。敵手A1輸出對γ的猜測γ′。如果γ=γ′，則稱敵手A1贏得游戲。敵手A1獲勝的優(yōu)勢定義為：

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

2.2.2 游戲INDCCA2Ⅱ

1）系統(tǒng)參數(shù)設置。挑戰(zhàn)者模擬算法Setup（k）生成系統(tǒng)主密鑰msk和公開參數(shù)集params。挑戰(zhàn)者將主密鑰msk和公開參數(shù)集params輸出給敵手A2。

2）第1階段詢問。在這一階段中，敵手A2可以向挑戰(zhàn)者適應性地作如下一系列詢問。

用戶產(chǎn)生詢問 挑戰(zhàn)者維護一個列表Luser用于記錄用戶的私鑰、公鑰和證書。列表Luser初始為空。敵手A2輸入身份IDU，如果列表Luser中已存在相應的記錄，挑戰(zhàn)者則直接輸出身份IDU對應的公鑰PKU給敵手A2；否則，挑戰(zhàn)者生成身份IDU對應的私鑰SKU、公鑰PKU和證書CertU，然后將結果保存在列表Luser中并輸出公鑰PKU給敵手A2。

私鑰詢問 敵手A2輸入身份IDU，挑戰(zhàn)者從列表Luser中獲取身份IDU對應的私鑰SKU并輸出給敵手A2。

重加密密鑰詢問 敵手A2輸入身份IDA和IDB，挑戰(zhàn)者生成一個重加密密鑰RKA→B，并將之輸出給敵手A2。

重加密詢問 敵手A2輸入身份IDA和IDB以及一個原始密文CA，挑戰(zhàn)者生成一個重加密密文CB并將之輸出給敵手A2。

解密詢問 敵手A2輸入身份IDU和一個密文CU，挑戰(zhàn)者解密密文CU并將結果輸出給敵手A2。

3）挑戰(zhàn)階段。敵手A2輸出身份IDch以及2個等長的明文（M0， M1）進行挑戰(zhàn)，限制是敵手A2在第1階段詢問中沒有詢問過身份IDch對應的私鑰。挑戰(zhàn)者隨機選擇γ∈{0，1}，運行加密算法Encrypt（params， Mγ， IDch， PKch）生成Mγ的原始密文Cch，并將之作為挑戰(zhàn)密文輸出給敵手A2。

4）第2階段詢問。同第1階段詢問，限制是：敵手A2不可詢問挑戰(zhàn)身份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中的指數(shù)運算、群G中的指數(shù)運算以及MaptoPoint雜湊函數(shù)運算，其系數(shù)表示該運算的次數(shù)。一般雜湊函數(shù)運算的計算代價忽略不計。

根據(jù)文獻[20]中的度量數(shù)據(jù)（見表2），表3和表4進一步給出了本文方案與文獻[10，19]中方案的詳細對比，其中MNT/80和SS/80分別表示80比特的MNT（MiyajiNakabayashiTakano）橢圓曲線和80比特的超奇異橢圓（Super Singular， SS）曲線，可提供1024比特的RSA安全性。便于比較，假定三個方案加密時都使用SHA1雜湊函數(shù)，此時n和l的值為160。

由表3和表4可見，與文獻[10，19]中方案相比，本文方案在計算代價和通信代價兩個方面都具有明顯的優(yōu)勢，更適用于計算受限且低通信帶寬的應用場合。

5 結語

本文提出了一個高效的不依賴于雙線性對的基于證書代理重加密方案?；贑DH問題的困難性假設，該方案在隨機預言模型下被證明滿足選擇密文安全性。與已有的基于證書代理重加密方案相比較，本文方案具有計算效率高和通信代價低的優(yōu)點，因此適用于計算受限且低通信帶寬的應用場合。

已有的代理重加密方案只能針對唯一的被授權人產(chǎn)生重加密密鑰和重加密密文。但在很多實際應用場合下，一個用戶希望與多個用戶同時分享其存儲在云端的加密數(shù)據(jù)，那么授權人將不得不針對每一個被授權人生成重加密密鑰，而云端代理也需要針對每一個被授權人生成相應的重加密密文。這不僅給授權人和代理帶來了沉重的計算負擔，同時也增加了授權人與代理之間的通信代價，因此，構造多接受者的基于證書代理重加密方案是下一步的工作重心。

參考文獻：

[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].