固定密文長度的可驗證屬性基外包解密方案

李 聰，楊曉元，王緒安，白 平

(1.武警工程大學(xué) 電子技術(shù)系，西安 710086； 2.武警工程大學(xué) 網(wǎng)絡(luò)與信息安全武警部隊重點實驗室，西安 710086)

固定密文長度的可驗證屬性基外包解密方案

李 聰1,2*，楊曉元1,2，王緒安1,2，白 平1,2

(1.武警工程大學(xué) 電子技術(shù)系，西安 710086； 2.武警工程大學(xué) 網(wǎng)絡(luò)與信息安全武警部隊重點實驗室，西安 710086)

傳統(tǒng)密鑰策略屬性基加解密方案存在密文長度隨著屬性增加而線性增加，在通信過程中消耗用戶大量的通信帶寬的缺點。提出了屬性加密的改進方案，基于密鑰策略屬性加密，提出具有固定密文長度的可驗證外包解密方案，在非單調(diào)訪問結(jié)構(gòu)實現(xiàn)密文長度固定，有效節(jié)省通信帶寬，通過對外包密鑰生成算法的改進，實現(xiàn)一次模指數(shù)運算，有效縮短外包密鑰生成時間。通過運用哈希函數(shù)，實現(xiàn)外包解密的驗證性, 并對其安全性進行了證明。

密鑰策略屬性基加密；外包解密；可驗證性;云計算

0 引言

現(xiàn)代社會中云計算快速發(fā)展，人們大量使用云計算來共享數(shù)據(jù)。為了加強數(shù)據(jù)安全和防止隱私泄露，需要對數(shù)據(jù)進行加密操作, 因此提出基于屬性的加密方案(Attributed-Based Encryption, ABE)[1]，ABE方案靈活地利用訪問策略加密數(shù)據(jù)。根據(jù)密文與訪問策略和屬性的關(guān)系，可分為兩大類[2]：密文策略屬性基加密(Ciphertext-Policy ABE, CP-ABE)和密鑰策略屬性基加密(Key-Policy ABE, KP-ABE)。

傳統(tǒng)雙線性對的ABE方案，存在大量的雙線性對運算，計算量隨著訪問策略的復(fù)雜性而線性增加[3-4]。這對于資源受限的用戶設(shè)備完成解密是一個重大的挑戰(zhàn)，為了減少用戶解密算法中用戶的計算量,Green等[5]提出了解密計算外包給第三方云服務(wù)器，這有助于“瘦身客戶機”實現(xiàn)解密，他們提出外包解密的一個關(guān)鍵的技術(shù)[6-10]，使第三方云服務(wù)不泄露數(shù)據(jù)或被惡意攻擊。用戶提供轉(zhuǎn)換密鑰給云服務(wù)器，云服務(wù)器解密輸出恒定大小的ElGamal密文，然后利用私鑰恢復(fù)出明文?？紤]以下場景：用戶Alice想要把自己的病例傳給某醫(yī)院的醫(yī)生Bob，但是Bob在休假且只能用移動電話的情況下，那么Alice先用加密方案加密數(shù)據(jù)(如KP-ABE); 然后把密文上傳到云存儲，醫(yī)生B需要下載數(shù)據(jù)解密，假如他直接下載密文解密，他的移動電話不能承擔(dān)如此大的計算量，因此，將解密過程外包給云端。一個重要的問題是密文長度，假如外包給云的密文非常長,需要消耗移動電話大量電量，會嚴(yán)重縮短移動電話的使用時間，這是難以忍受的。還有外包密鑰生成服務(wù)器，算法復(fù)雜生成外包密鑰也會花費大量時間和手機電量。另外還要確保解密結(jié)果是正確的，否則，看錯病，對病人是非常嚴(yán)重的問題，所以在外包解密時既要關(guān)心密文的長度也要關(guān)心解密的正確性。

為了確定第三方是誠實地進行外包計算, Lai等[11]引入可驗證性的外包解密ABE方案，在文獻[5]加密/解密算法的基礎(chǔ)上增加了額外的實例，用于驗證外包結(jié)果的正確性。該方法明顯增加了方案的計算開銷，發(fā)送者需要加密一個額外的隨機消息，計算同兩個消息有關(guān)的校驗值。雖然文獻[11]方案很容易理解，但它存在兩個缺點：第一，加密和解密的成本是其他ABE方案的兩倍；第二，密文長度是其他ABE方案的兩倍。2015年Qin等[12]提出了一個非常有效的可驗證外包解密方案，隨機選擇一個消息密鑰K，利用密鑰提取器提取對K操作生成對稱加密的密鑰，再對消息密鑰K進行公鑰加密，同時在加密過程中對消息密鑰K進行哈希生成驗證密鑰，有效實現(xiàn)了外包解密結(jié)果的驗證。但是，他們都沒有關(guān)注密文的長度，其加密的密文隨著屬性數(shù)量的增加而增大,而且也沒有關(guān)注外包密鑰生成時間，其外包密鑰生成時間也隨著屬性數(shù)量的增加而增加。Attrapadung等[13]提出了非單調(diào)訪問結(jié)構(gòu)的短密文KP-ABE方案，實現(xiàn)了固定長度的密文，但是其加解密的運算量很大。

本文在文獻[12-13]方案的基礎(chǔ)上實現(xiàn)了固定密文可驗證外包解密，并在外包密鑰生成算法上進行了改進。通過運用密鑰提取器及兩個散列碰撞函數(shù)，實現(xiàn)外包解密的驗證性。與之前在ABE的外包解密方案相比，本方案不僅可以縮短外包密文的長度，還可有效節(jié)省外包密鑰生成時間。

1 預(yù)備知識

定義1 雙線性映射e:G0×G0=G1。G0、G1是兩個以素數(shù)p為階的循環(huán)群，滿足以下性質(zhì):

1)雙線性性。e(ga,gb)=e(g,g)ab，?a,b∈Zp，?p,q∈G0。

2)非退化性。存在g是G0的生成元，使得e(g,g))≠1。

3)可計算性。存在有效算法計算雙線性對。

定義2 線性秘密共享方案(Linear Secret Sharing Scheme, LSSS)，當(dāng)滿足以下兩個條件時，參與方集合P上的秘密共享方案在Zp域上是線性的[12,14]。

1)各方共享的秘密形成一個Zp域上的矩陣；

2)存在一個行列的秘密共享矩陣A。存在一個函數(shù)把矩陣的每一個行映射到參與方P，即矩陣的第i(i=1,2,…,l)行被標(biāo)識為參與方ρ(i)，當(dāng)考慮列向量ν=(α,r2,r3,…,rn)，其中α∈Zp是將要共享的秘密值，r2,r3,…,rn是隨機數(shù),則向量Αν為秘密α的l個共享子秘密，且(Αν)i屬于參與方ρ(i)。

引理1[15]定義X、Y和Z為隨機變量，假如Y有2r種可能取值，則H∞(X|(Y,Z))≥H∞(X|Z)-r。

定理1[15]當(dāng)H∞(X|Z)≥log |Y|+2 log |1/ε|時，成對獨立的哈希函數(shù)H:(h:X→Y)是平均(H∞(X|Z)，ε)的強提取器。

2 安全模型

訪問結(jié)構(gòu)用f表示，定義(Ienc,Ikey)為加密操作和密鑰生成操作，在KP-ABE中，有(Ienc,Ikey)=(ω,f)，模型中允許敵手選擇云服務(wù)提供者，并且腐化他們進行惡意攻擊。S代表屬性集，安全模型包括以下幾個階段：

1)初始化。敵手A宣布一系列加密屬性集S用于挑戰(zhàn)階段生成挑戰(zhàn)密文，并把屬性集S提交給挑戰(zhàn)者。

2)系統(tǒng)參數(shù)建立。挑戰(zhàn)者運行初始化算法，將公共參數(shù)發(fā)給敵手A。

3)階段1。敵手重復(fù)發(fā)出私鑰詢問給相應(yīng)的訪問結(jié)構(gòu)(L,π)，但是ω*不滿足訪問結(jié)構(gòu)(L,π)，ω*是敵手準(zhǔn)備攻擊的屬性。

4)挑戰(zhàn)。敵手輸出兩個屬性長度相同的明文M0和M1，挑戰(zhàn)者隨機選擇b∈{0,1}，加密明文(M,S*)，并把密文CT作為挑戰(zhàn)發(fā)給敵手A。

5)階段2。敵手的屬性在不滿足挑戰(zhàn)訪問結(jié)構(gòu)(L,π)的條件下，重復(fù)階段1的過程，發(fā)出更多的詢問。

6)猜測。敵手輸出猜測的β′,假如β=β′，則敵手獲勝，敵手在游戲中的優(yōu)勢為|Pr[β=β′]-1/2|。

3 固定密文長度的可驗KP-ABE外包解密方案

3.1 可驗證外包解密方案模型定義

可驗證外包屬性基解密方案模型通常由以下算法組成。

1)Setup(λ，n)。運行Setup′(λ，n)得一外包ABE密鑰對(MPK′，MSK′)，對于消息空間M，選擇兩個哈希函數(shù)H0：M→{0，1}lH0,H1：{0，1}*→{0，1}lH1和密鑰提取器h∈H[15]，及一個對稱加密方案SE。輸出主公鑰MPK=(MPK′，H0,H1，h，SE)和主私鑰MSK=(MPK，MSK′)。

2)Encrypt(MPK，M，Ienc)。隨機消息K，明文M，運行Encrypt′(MPK′，K，Ienc)，輸出密文C。另外定義標(biāo)簽為Lab0=H0(K)計算對稱加密密鑰KSE=h(K)，計算對稱加密密文CSE=SE.Enc(KSE,M)和標(biāo)簽Lab=H1(Lab0‖CSE)，輸出最后密文CTIenc=(C,CSE)和驗證密鑰VK=Lab。

3)KeyGenout(MPK，MSK，Ikey)。外包密鑰生成算法輸入主私鑰MSK，主公鑰MPK和密鑰生成算法Ikey，輸出轉(zhuǎn)換公鑰Tkout和轉(zhuǎn)換私鑰Skout。

4)Transform(Tkout，CTIenc)。密文轉(zhuǎn)換算法輸入轉(zhuǎn)換公鑰Tkout和密文CTIenc。輸出部分解密密文即轉(zhuǎn)換密文CTout=(CTout′,CSE)。

5)Decryptout(MPK，Skout，CTout)。首先解密算法計算出隨機消息K，然后計算Lab0=H0(K)，若H(Lab0‖CSE)≠VK輸出⊥，否則計算KSE=h(K)，輸出明文M=SE.Dec(KSE，CSE)。

3.2 固定密文長度的可驗證外包解密方案

Di,1=gλi·h1ri,Di,2=gλi,

Kρi, j={Ki, j=(h1-ρi, n/ρi,1·hj)ri}j=2,3,…,n

另外Lab0=H0(R)，計算對稱加密密鑰KSE=h(R)，利用對稱加密方案加密明文得CSE=SE.Enc(KSE,M)，而后生成驗證標(biāo)簽Lab=H1(Lab0,CSE),最后輸出密文CT=(C,CSE)和驗證密鑰VK=Lab。

Di,1′=gλi/zh1ri

Di,2′=gri

Kρi, i={Ki, j=(h1-ρi, n/ρi,1·hj)ri}j=2, 3, …, n

正確性判斷：

所以：

4 方案分析

4.1 安全分析

RCCA(Replayable Chosen Ciphertext Attacks)安全：運用RCCA安全[13]對于可驗證ABE外包解密，它們之間的區(qū)別是對手獲得一個固定長度的密文，這可能與加密的消息中的挑戰(zhàn)密文有關(guān)。游戲1包含挑戰(zhàn)者和敵手A1，具體包括以下步驟:

Setup：挑戰(zhàn)者運行Setup(κ,U)生成主密鑰對(mpk,msk)，把msk給敵手。

Phase 1：挑戰(zhàn)者初始化一個空表T，一個空屬性集D和一個計數(shù)器j:=0。敵手可以重復(fù)對下面的問題進行適應(yīng)性的詢問：

Create(Ikey)：挑戰(zhàn)者設(shè)置j:=j+1，首先運行KeyGenout(msk,Ikey)獲得密鑰對(Tkout,Ikey,Skout, Ikey)，然后發(fā)送Tkout,Ikey給敵手，并存儲在表T中，一行實體為(j,Ikey,Tkout,Ikey,Skout,Ikey)。

Decrypt(i,(VK,CTout)):假如表中存在第i個實體，挑戰(zhàn)者獲得實體(i,Ikey,Tkout,Ikey,Skout,Ikey)并發(fā)送解密密文Decrypt(Skout,Ikey,VK,CTout)給敵手；如果不存在這樣的實體則返回⊥。

Phase 2: 重復(fù)階段1的詢問，但是除了以下的詢問：

2)如果解密出明文為M0或M1，那么挑戰(zhàn)者則回應(yīng)特殊的消息⊥。

定義3 可驗證ABE外包解密是RCCA安全，當(dāng)在概率多項式時間(Probabilistic Polynomial Time, PPT)內(nèi)，敵手猜測成功的優(yōu)勢可忽略。

定理2 假設(shè)傳統(tǒng)外包ABE方案是CPA(Chosen-Plaintext Attack)安全，H是一對獨立的哈希函數(shù)，SE是對稱加密方案，那么，本文方案可驗證ABE外包解密方案是CPA安全。

證明 本文定義三個游戲：游戲1、游戲2、游戲3。其中：游戲1是原始傳統(tǒng)CPA安全證明，目的是證明任意兩個游戲之間對于敵手是不可區(qū)分的，在游戲3中，敵手不可區(qū)分加密的是消息M0還是M1。令Si代表敵手在游戲i中成功的可能性。

假設(shè)1 假如外包ABE方案是CPA安全，那么敵手對游戲1和游戲2在計算上是不可區(qū)分的。

證明 首先定義一個概率多項式時間算法Sim，希望能在敵手A1的幫助下打破CPA安全的ABE方案，Sim依靠挑戰(zhàn)密文來模仿敵手A1看待游戲1和游戲2的觀點。

階段1 敵手A1可以重復(fù)進行Create(Ikey)和Corrupt(i)進行詢問。

猜測 模擬器可以完全模擬敵手在游戲1、2中的觀點，所以可得出：

多個敵手B攻擊CPA安全的外包ABE方案。

假設(shè)2 假設(shè)H是一對獨立的哈希函數(shù)，那么敵手對游戲2、3是統(tǒng)計上不可區(qū)分的。

假設(shè)3 假如對稱加密方案SE是語義安全的，那么敵手在游戲3中有可忽略的優(yōu)勢。

在上述安全性證明中，本文只考慮(選擇性)CPA安全。同時，如果潛在的外包加密方案是RCCA安全同時對稱加密方案也是RCCA安全，也可證明可驗證性外包解密方案也是RCCA安全。到目前為止，所有的RCCA安全外包ABE依靠Random Oracle(RO)，因此由此產(chǎn)生的可驗證方案只是RO模型下是RCCA安全。

定理3 假設(shè)H0和H1是耐碰撞散列函數(shù)，那么本文外包解密ABE方案是可驗證的。

4.2 性能分析

基于benchmark中的實驗數(shù)據(jù)，通過對模指數(shù)和雙線性對的理論分析，下面從通信開銷和計算開銷方面對方案進行性能分析，給出本文方案和文獻[5,11-13]方案的性能比較，如表1所示。其中n指的是方案的訪問結(jié)構(gòu)中的屬性個數(shù)，|G0|表示群G0中元素的長度,lH代表CRH函數(shù)的輸出大小。本方案外包密鑰生成時運算次數(shù)需進行n次G0群上的指數(shù)運算；Green等方案需進行2n次G0群上的指數(shù)運算。綜上，本方案在通信開銷和外包密鑰生成算法上比較有優(yōu)勢，節(jié)省時間。綜合考慮無疑本方案更加適用于實際環(huán)境。在表中，l代表LSSS訪問結(jié)構(gòu)中的l行，Out.CT.size代表外包密文大小，Ken.out表示外包密鑰運算次數(shù)。

表1 幾種方法性能對比Tab.1 Program performance comparison

5 結(jié)語

本文分析了有效驗證屬性基外包解密方案。結(jié)果表明,該方案沒有關(guān)注外包密文的長度，密文大小隨著屬性的增加而增大，這不利于通信傳輸。外包密鑰生成時間隨著屬性而增加，同時也不適用于計算能力有限的小型移動設(shè)備。本文改進了該方案，實現(xiàn)固定密文大小的可驗證KP-ABE外包解密方案，有效縮短外包密鑰生成時間，并在標(biāo)準(zhǔn)模型下證明了其安全性。

[1] SAHAI A, WATERS B. Fuzzy identity-based encryption[C]// Proceedings of the 24th Annual International Conference on Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2005: 457-473.

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

[3] ATTRAPADUNG N. Dual system encryption via doubly selective security: framework, fully secure functional encryption for regular languages, and more[C]// Proceedings of the 2014 Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2014: 557-577.

[4] YAMADA S, ATTRAPADUNG N, HANAOKA G, et al. Generic constructions for chosen-ciphertext secure attribute based encryption[C]// Proceedings of the 2011 International Workshop on Public Key Cryptography. Berlin: Springer, 2011: 71-89.

[5] GREEN M, HOHENBERGER S, WATERS B. Outsourcing the decryption of ABE ciphertexts[C]// Proceedings of the 20th USENIX Conference on Security. Berkeley: USENIX Association, 2011: 34-34.

[6] MAO X, LAI J, MEI Q, et al. Generic and efficient constructions of attribute-based encryption with verifiable outsourced decryption[J]. IEEE Transactions on Dependable and Secure Computing, 2016, 13(5): 533-546.

[7] LI J, HUANG X, LI J, et al. Securely outsourcing attribute-based encryption with checkability[J]. IEEE Transactions on Parallel and Distributed Systems, 2014, 25(8): 2201-2210.

[8] PARNO B, RAYKOVA M, VAIKUNTANATHAN V. How to delegate and verify in public: verifiable computation from attribute-based encryption[C]// Proceedings of the 9th International Conference on Theory of Cryptography. Berlin: Springer, 2012: 422-439.

[9] 陳飛, 韓益亮, 李曉策, 等. 支持通用電路的多線性映射外包屬性加密方案[J]. 計算機應(yīng)用, 2016, 36(10): 2747-2752. (CHEN F, HAN Y L, LI X C, et al. Outsourced attribute-based encryption for general circuit from multilinear maps[J]. Journal of Computer Applications, 2016,36(10):2747-2752.)

[10] 方雪鋒, 王曉明. 可撤銷用戶的外包加解密 CP-ABE 方案[J]. 計算機工程, 2016, 42(12): 124-128,132. (FANG X F,WANG X M. Outsourced encryption and decryption CP-ABE Scheme with user revocation[J].Computer Engineering,2016,42(12):124-128,132.)

[11] LAI J, DENG R H, GUAN C, et al. Attribute-based encryption with verifiable outsourced decryption[J]. IEEE Transactions on Information Forensics and Security, 2013, 8(8): 1343-1354.

[12] QIN B, DENG R H, LIU S et al. Attribute-based encryption with efficient verifiable outsourced decryption[J]. IEEE Transactions on Information Forensics and Security, 2015, 10(7): 1384-1393.

[13] ATTRAPADUNG N, LIBERT B, DE PANAFIEU E. Expressive key-policy attribute-based encryption with constant-size ciphertexts[C]// Proceedings of the 14th International Conference on Practice and Theory in Public Key Cryptography Conference on Public Key Cryptography. Berlin: Springer, 2011: 90-108.

[14] 劉夢君，劉樹波，王穎，等．基于LSSS共享矩陣無授權(quán)策略的屬性密碼解密效率提高方案[J]．電子學(xué)報，2014，43(6)：1065-1072．(LIU M J, LIU S B, WANG Y, et al. Optimizing the decryption efficiency in LSSS matrix-based attribute-based encryption without given policy[J].Acta Electronica Sinica,2014,43(6):1065-1072.)

[15] WATERS B. Dual system encryption: realizing fully secure IBE and HIBE under simple assumptions[C]// Proceedings of the 29th Annual International Cryptology Conference on Advances in Cryptology. Berlin: Springer-Verlag, 2009: 619-636.

[16] YAMADA S, ATTRAPADUNG N, HANAOKA G, et al. A framework and compact constructions for non-monotonic attribute-based encryption[C]// PKC 2014: Public Key Cryptography, LNCS8383. Berlin: Springer, 2014: 275-292.

This work is partially supported by the National Natural Science Foundation of China (U1636114, 61572521), the Natural Science Basic Research Plan in Shaanxi Province of China (2016JQ6037)

LICong, born in 1990, M. S. candidate. His research interest include public key cryptology.

YANGXiaoyuan, born in 1959, Ph. D., professor. His research interests include cryptology, information security.

WANGXu’an, born in 1981, Ph. D., associate professor. His research interests include cryptology, information security.

BAIPing, born in 1990, M. S. candidate. His research interests include public key cryptology.

Efficientverifiableoutsourceddecryptionbasedonattribute-basedencryptionandfixedciphertextlength

LI Cong1,2*, YANG Xiaoyuan1,2, WANG Xu’an1,2, BAI Ping1,2

(1.DepartmentofElectronicTechnology,EngineeringCollegeofChineseArmedPoliceForce,Xi’anShaanxi710086,China;2.KeyLaboratoryofNetworkandInformationSecurity,EngineeringCollegeofChineseArmedPoliceForce,Xi’anShaanxi710086,China)

The traditional key policy attribute base encryption and decryption scheme has the disadvantages that the ciphertext length increases linearly with the increase of the number of attributes, and consumes a large amount of communication bandwidth of the user in the communication process. The improved scheme of attribute encryption was proposed. Based on the encryption of key policy attributes, a verifiable packet decryption scheme with fixed ciphertext length was proposed. In the non-monotonic access structure, the cipher length was fixed, and the communication bandwidth was effectively saved. Through the improvement of outsourced key generation algorithm, a primary modular exponentiation operation was realized, and the generation time of key generation was effectively shortened.The hash function was used to realize the verification of the decryption and its security was proved.

Key-Policy Attributed-Based Encryption (KP-ABE)；outsourced description；verifiability; cloud computing

2017- 05- 15;

2017- 07- 03。

國家自然科學(xué)基金資助項目(U1636114，61572521)；陜西省自然科學(xué)基礎(chǔ)研究計劃項目(2016JQ6037)。

李聰(1990—)，男，山東濟寧人，碩士研究生，主要研究方向：公鑰密碼學(xué)； 楊曉元(1959—)，男，湖南湘潭人，教授，博士生導(dǎo)師，CCF 會員，主要研究方向：密碼學(xué)、信息安全； 王緒安(1981—)，男，湖北公安人，副教授，博士，主要研究方向：密碼學(xué)、信息安全； 白平(1990—)，男，內(nèi)蒙古烏蘭察布人，碩士研究生，主要研究方向：公鑰密碼學(xué)。

1001- 9081(2017)11- 3299- 05

10.11772/j.issn.1001- 9081.2017.11.3299

(*通信作者電子郵箱wugongcong@163.com)

TP309.7

A