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

湯海婷,汪學明

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

0 概述

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

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

1 屬性加密和格理論

1.1 CP-ABE方案形式化描述

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

1.2 格的基本定義

1.3 高斯分布

1.4 LWE問題

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

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

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

2.1 方案描述

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

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

2.2 方案具體構造

首先假設系統有y個屬性,記松弛屬性集合為Ω,它的個數為|Ω|=k。k表示同時加密的消息的數量。系統屬性集合記為U={1,2,…,y},由文獻[16],假設訪問策略為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和公共參數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,訪問控制結構Lpolicy。

3 正確性證明

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

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

在解密算法中,計算:

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

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

4 安全性

4.1 安全性證明

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

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

Init:

1)敵手A給挑戰者β發送了一個待挑戰的訪問結構Lpolicy。

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

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

Setup:

Phase1:

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

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

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

4.2 參數估計

本文構造的方案結合文獻[10,14]和一些相關算法,如果要保證方案的正確性和安全性,需要對參數進行如下設置:

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

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

logaq+w(logan)。

5)在解密階段,需要:

5 結束語

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

[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] 龐遼軍,姜正濤,王育民.基于一般訪問結構的多重秘密共享方案[J].計算機研究與發展,2006,43(1):33-38.