一種基于格的屬性多重加密方案

湯海婷,汪學明

(貴州大學 計算機科學與技術(shù)學院,貴陽 550025)

0 概述

傳統(tǒng)的屬性基加密方案最初是在歐洲密碼年會上創(chuàng)造性提出的[1]。之后,相繼有學者提出了各種ABE方案。文獻[2]對屬性加密體制進行細粒度的劃分,由此引入了KP-ABE和CP-ABE這2種屬性加密體制。文獻[3]給出了一個隱藏策略的ABE方案,但該方案不能抗合謀性。文獻[4]構(gòu)造出能抵抗合謀攻擊,訪問結(jié)構(gòu)復雜的高安全的CP-ABE方案。文獻[5]提出了可追責的CP-ABE方案,分別在用戶追責和屬性授權(quán)機構(gòu)追責下進行考慮,該方案的缺陷是僅支持與門操作。當前,大部分屬性密碼體制都是用雙線性對來構(gòu)建的。隨著量子密碼時代的到來,構(gòu)建能抵抗量子攻擊的密碼[6]是迫切需要的。格密碼[7]在后量子密碼中具有很高的地位,利用格構(gòu)造密碼方案不僅能抵抗量子攻擊,同時也能減少計算過程的復雜程度。

文獻[8]開創(chuàng)性提出格密碼學,它是基于特定格代數(shù)結(jié)構(gòu)構(gòu)造的。直到2008年,才有基于格的身份加密方案提出。文獻[9]利用格構(gòu)造了標準模型下安全的模糊身份加密方案。同年,文獻[10]提出應用門限訪問結(jié)構(gòu)來構(gòu)建格上的CP-ABE方案。文獻[11]提出了可證明安全的基于格的屬性加密方案,在線性秘密分享技術(shù)下構(gòu)建基于格的屬性加密方案,并用學習錯誤(Learning with Errors,LWE)問題[12]證明了方案的正確性。文獻[13]用格構(gòu)造多授權(quán)機構(gòu)的ABE方案。在基于格的屬性加密研究中,提高加解密運行效率,引入合適的訪問結(jié)構(gòu)一直是個熱點課題。對格上密文策略的屬性加密研究不多,而實現(xiàn)基于格的密文策略屬性加密方案,使它能夠支持表達能力更強的訪問結(jié)構(gòu)是當前研究的熱點。本文利用文獻[10]提出的格上的CP-ABE方案和文獻[14]提出的基于屬性的動態(tài)多重加密方案,構(gòu)造基于格的屬性多重加密方案,并嚴格推導方案的正確性和在LWE問題下的高安全性。

1 屬性加密和格理論

1.1 CP-ABE方案形式化描述

方案的形式化描述包括初始化、密鑰生成、加密和解密。相關(guān)內(nèi)容和安全模型及具體的方案描述見文獻[14]。

1.2 格的基本定義

1.3 高斯分布

1.4 LWE問題

(Zq,n,χ)-LWE問題用一個算法來描述,其判定LWE問題的優(yōu)勢為|Pr[AOs=1]-Pr[AO$=1]|,若算法判定取樣是屬于OS,則輸出0;否則輸出1。算法對預言機多次詢問后,其判定LWE問題的優(yōu)勢不可忽略,則稱算法可以判定LWE問題。

格上的離散高斯抽樣算法和相關(guān)引理見文獻[15]。

2 基于格的屬性多重加密方案

2.1 方案描述

引入一個松弛屬性集合,它沒有具體的意義,用來完成主密鑰的構(gòu)建。加入松弛屬性集合可以支持更靈活的加密消息數(shù)量,也就是說用戶在加密時更為靈活。采用文獻[16]的多重秘密共享方案來生成用戶的密鑰,因為有松弛屬性存在,使得本文方案具有動態(tài)性。

方案構(gòu)造的第一步,生成發(fā)布多個系統(tǒng)主密鑰來加密多個消息或者說可以加密一個很大的消息。這個很大的消息能夠分組成多個長度較小的消息。由此,可以提高加解密效率。主密鑰在生成過程中,利用多重秘密共享方案的思想,先轉(zhuǎn)變成點值對,再融入到高次多項式里。在方案生成密鑰的過程中,高次多項式會將主密鑰msk分發(fā)到每個用戶的解密密鑰中。在文獻[16]的方案中,每個用戶僅維護一個秘密份額。這些秘密在重構(gòu)過程中,只有擁有授權(quán)子集的參與者才能恢復每一個秘密,方案的加密過程可以同時加密多個消息。根據(jù)文獻[10]提出的格上的CP-ABE方案,做出如下的構(gòu)造。

2.2 方案具體構(gòu)造

首先假設(shè)系統(tǒng)有y個屬性,記松弛屬性集合為Ω,它的個數(shù)為|Ω|=k。k表示同時加密的消息的數(shù)量。系統(tǒng)屬性集合記為U={1,2,…,y},由文獻[16],假設(shè)訪問策略為Lpolicy,W為用戶屬性集合,且W?U,門限值為t。用戶屬性集合至少有t個屬性才滿足Lpolicy。

2.2.1 初始化

Setup(1λ):

2.2.2 密鑰生成

KGen(msk,w):

1)輸入用戶屬性集合W。

2.2.3 加密過程

Enc(pk,Lpolicy,Mv):

1)輸入用戶屬性集W和公共參數(shù)pk,W滿足Lpolicy,消息Mv∈{0,1},v∈[k]。

3)返回密文C=(Cv,C′,{Ciw}iw∈W,{CiΩ}iΩ∈Ω)。

2.2.4 解密過程

Dec(C,sk):

1)輸入密文C、私鑰ski、消息Mv,訪問控制結(jié)構(gòu)Lpolicy。

3 正確性證明

當|D∩W|≥t時,密文屬性集滿足用戶屬性集W,即屬性集滿足訪問控制策略Lpolicy,由2.2.4節(jié)知:

同理得到(C′;CjΩ)的計算結(jié)果。

在解密算法中,計算:

其中,h=∑j∈SLjhjs,則:

r=Cv-b=Cv-(μTf+h)=

4 安全性

4.1 安全性證明

假設(shè)存在一個多項式時間的算法能以ε>0的優(yōu)勢攻破上文的方案,則說明存在一個概率多項式時間的算法可以判定(Zq,n,χ)-LWE問題。

若敵手A能以不可忽略的概率解決(Zq,n,χ)-LWE問題,則方案就不安全。根據(jù)文獻[10]的算法,相關(guān)過程如下:

Init:

1)敵手A給挑戰(zhàn)者β發(fā)送了一個待挑戰(zhàn)的訪問結(jié)構(gòu)Lpolicy。

2)令W*為待挑戰(zhàn)的屬性集合,它是敵手A將要攻擊的目標。

3)A0和u是由LWE預言機隨機產(chǎn)生,B由TrapGen算法產(chǎn)生。

Setup:

Phase1:

1)β收到私鑰,產(chǎn)生詢問,詢問集合為θ,屬性集滿足|W*∩θ|

Phase2:預言機重復Phase1中的行為。

Guess:敵手A給出對于預言機隨機選取b的猜測值b′。若b′=b,那么預言機返回1,否則預言機輸出0。

4.2 參數(shù)估計

本文構(gòu)造的方案結(jié)合文獻[10,14]和一些相關(guān)算法,如果要保證方案的正確性和安全性,需要對參數(shù)進行如下設(shè)置:

2)方案開始階段用到了TrapGen算法,這里要求m≥5nlogaq。

4)在安全性證明中,有:

logaq+w(logan)。

5)在解密階段,需要:

5 結(jié)束語

本文將格理論代替雙線性對,構(gòu)造了一個密文策略的屬性多重加密方法。該方案可以同時加密多條消息,提高屬性加解密效率,抵抗量子攻擊并滿足正確性要求。最后在LWE困難問題下證明了該方案的安全性。下一步將引入更為靈活的訪問結(jié)構(gòu),并把方案拓展到大規(guī)模屬性全集上。

[1] SAHAI A,WATERS B.Fuzzy Identity-based Encryption[C]//Proceedings of International Conference on Theory & Appli-cations of Cryptographic Techniques.Berlin,Germany: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 & Communications Security.New York,USA:ACM Press,2006:89-98.

[3] KAPADIA A,TSANG P P,SMITH S W.Attribute-based Publishing with Hidden Credentials and Hidden Policies[C]//Proceedings of Network and Distributed System Security Symposium.Washington D.C.,USA:IEEE Press,2007:179-192.

[4] BETHENCOURT J,SAHAI A,WATERS B.Ciphertext-policy Attribute-based Encryption[C]//Proceedings of IEEE Symposium on Security and Privacy.Washington D.C.,USA:IEEE Press,2007:321-334.

[5] LI Jin,REN Kui,ZHU Bo,et al.Privacy-aware Attribute-based Encryption with User Accountability[C]// Proceedings of International Conference on Information Security.New York,USA:ACM Press,2009:347-362.

[6] BERNSTEIN D J,BUCHMANN J,DAHMEN E.Post Quantum Cryptography[M].Berlin,Germany:Springer,2011.

[7] MICCIANCIO D,REGEV O.Lattice-based Cryptography[M].Berlin,Germany:Springer,2009.

[8] AJTAI M.Generating Hard Instances of Lattice Problems[C]//Proceedings of the 28th ACM Symposium on Theory of Computing.New York,USA:ACM Press,1996:99-108.

[9] AGRAWAL S,BOYEN X,VAIKUNTANATHAN V,et al.Functional Encryption for Threshold Functions (or Fuzzy IBE) from Lattices[M].Berlin,Germany:Springer,2012.

[10] ZHANG Jiang,ZHANG Zhenfeng,GE Aijun.Ciphertext Policy Attribute-based Encryption from Lattices[C]//Proceedings of ACM Symposium on Information,Computer and Communications Security.New York,USA:ACM Press,2012:16-17.

[11] BOYEN X.Attribute-based Functional Encryption on Lattices[M].Berlin,Germany:Springer,2013.

[12] REGEV O.On Lattices,Learning with Errors,Random Linear Codes,and Cryptography[J].Journal of the ACM,2009,56(6):34.

[13] ZHANG Yanhua,HU Yupu,JIANG Mingming.An Attribute-based Signature Scheme from Lattice Assumption[J].Wuhan University Journal of Natural Sciences,2015,20(3):207-213.

[14] 郭振洲.基于屬性的加密方案的研究[D].大連:大連理工大學,2012.

[15] 馮 芳.格上基于屬性的加密算法研究[D].西安:西安理工大學,2015.

[16] 龐遼軍,姜正濤,王育民.基于一般訪問結(jié)構(gòu)的多重秘密共享方案[J].計算機研究與發(fā)展,2006,43(1):33-38.