格上基于可編程哈希函數(shù)的HIBE方案

葉 青,王明明,湯永利,秦攀科,王永軍

(河南理工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,河南 焦作 454000)

0 概述

1984年,SHAMIR A提出了基于身份的公鑰密碼體制[1],在該體制中,公鑰是用來(lái)表示用戶身份標(biāo)志的一組任意的字符串,如E-mail地址或電話號(hào)碼等,相應(yīng)的私鑰則由私鑰生成器(Private-Key Generator,PKG)生成?；谏矸莸募用?Identity-Based Encryption,IBE)方案的提出,消除了傳統(tǒng)公鑰加密方案對(duì)用戶證書(shū)的依賴,極大地簡(jiǎn)化了密鑰管理系統(tǒng)?；诜旨?jí)身份的加密(Hierarchical Identity-Based Encryption,HIBE)是一種公鑰加密方案[2-3],其中,用戶實(shí)體被安排在一棵定向樹(shù)上,每個(gè)用戶對(duì)應(yīng)于樹(shù)上的不同節(jié)點(diǎn),且可以從相應(yīng)的父節(jié)點(diǎn)處得到用戶私鑰,同時(shí)還可以將該私鑰派生給相應(yīng)的子節(jié)點(diǎn),子節(jié)點(diǎn)利用派生后的用戶私鑰解密消息或者繼續(xù)將私鑰派生給相應(yīng)的子節(jié)點(diǎn),但是不可以解密樹(shù)上其他節(jié)點(diǎn)的密文。上述派生過(guò)程是單向的,即子節(jié)點(diǎn)無(wú)法用自己的私鑰來(lái)恢復(fù)父節(jié)點(diǎn)私鑰。較早的HIBE方案[4-5]大多基于數(shù)論難題(如大整數(shù)因子分解難題和有限域離散對(duì)數(shù)難題)而構(gòu)建,隨著量子計(jì)算機(jī)的發(fā)展,基于數(shù)論難題的HIBE方案都能夠在多項(xiàng)式時(shí)間內(nèi)被攻破,因此,研究抗量子攻擊的替代密碼方案成為該領(lǐng)域亟需解決的問(wèn)題。近年來(lái),基于格構(gòu)造的新型密碼系統(tǒng)因具有運(yùn)算簡(jiǎn)單、存在最壞情況下的隨機(jī)實(shí)例、較高的漸進(jìn)效率以及抗量子攻擊的特點(diǎn),成為后量子時(shí)代密碼領(lǐng)域的研究熱點(diǎn)之一[6-7]。2008年,文獻(xiàn)[8]構(gòu)造出格上基于身份的加密方案。2010年,文獻(xiàn)[9]采用盆景樹(shù)系統(tǒng)構(gòu)造出一個(gè)標(biāo)準(zhǔn)模型下的HIBE方案。同年,文獻(xiàn)[10-11]分別提出了標(biāo)準(zhǔn)模型下格上固定維度的HIBE方案和標(biāo)準(zhǔn)模型下格上HIBE方案。2012年,文獻(xiàn)[12]提出一種適應(yīng)性安全的標(biāo)準(zhǔn)模型下的高效格基(H)IBE方案。2014年,文獻(xiàn)[13]將廣播加密與HIBE方案相結(jié)合,提出一種格上基于分級(jí)身份基的廣播加密方案。但是,上述方案大多存在陷門(mén)生成計(jì)算復(fù)雜度較高(算法執(zhí)行過(guò)程復(fù)雜,且輸出矩陣維度較高)以及主公鑰尺寸較大的問(wèn)題。

2012年,文獻(xiàn)[14]提出了一種新的格上陷門(mén)生成算法(MP12陷門(mén)生成算法)以及與之對(duì)應(yīng)的原像采樣算法(MP12原像采樣算法),相比之前廣泛應(yīng)用的陷門(mén)生成算法GPV08[15],該陷門(mén)算法的生成過(guò)程簡(jiǎn)單,復(fù)雜度僅相當(dāng)于2個(gè)隨機(jī)矩陣的一次乘運(yùn)算,且不涉及計(jì)算代價(jià)高的矩陣求逆操作和HNF(Hermite Normal Form)。MP12原像采樣算法比較簡(jiǎn)單高效,算法支持并行運(yùn)算且輸入項(xiàng)為小整數(shù),對(duì)離線空間的需求較低。文獻(xiàn)[16-17]基于MP12陷門(mén)函數(shù)對(duì)格上IBE方案進(jìn)行改進(jìn),提出一種陷門(mén)生成與派生相結(jié)合的格上IBE方案,該方案復(fù)雜度較低且實(shí)用性較強(qiáng)。

2012年,文獻(xiàn)[18]提出了可編程哈希函數(shù)(Programmable Hash Function,PHF)的概念,構(gòu)建了基于雙線性映射的加密方案與基于RSA的簽名方案,這2個(gè)方案的共同特點(diǎn)是簽名尺寸相較以往簽名方案有所減小,安全性也得到提高,但卻增加了公鑰尺寸。針對(duì)該問(wèn)題,2015年,文獻(xiàn)[19]提出了不對(duì)稱PHF的概念,并利用該函數(shù)構(gòu)建一種標(biāo)準(zhǔn)模型下的線性全同態(tài)簽名方案,同時(shí)證明新簽名方案的公鑰尺寸明顯小于文獻(xiàn)[18]的簽名方案。2016年,文獻(xiàn)[20]提出了格上PHF的概念,其不僅繼承了傳統(tǒng)PHF的特點(diǎn),而且結(jié)合了格的分區(qū)證明技巧,該文獻(xiàn)用格上PHF重新構(gòu)建了格上的簽名方案和IBE方案,相較以往相關(guān)方案,基于格上PHF的新簽名方案的主公鑰尺寸明顯減小。

為降低標(biāo)準(zhǔn)模型下HIBE方案的陷門(mén)生成計(jì)算復(fù)雜度,減小主公鑰尺寸,本文結(jié)合格上PHF[20]和MP12陷門(mén)函數(shù)[14]構(gòu)建一種新的HIBE方案。將IBE方案[20]擴(kuò)展為HIBE方案,利用PHF設(shè)計(jì)系統(tǒng)建立算法和加密算法,方案中的陷門(mén)由MP12陷門(mén)函數(shù)生成,以降低計(jì)算復(fù)雜度。在此基礎(chǔ)上,利用標(biāo)準(zhǔn)模型下格上基于判定性容錯(cuò)學(xué)習(xí)(DLWE)問(wèn)題來(lái)驗(yàn)證該方案滿足INDr-aID-CPA安全。

1 預(yù)備知識(shí)

1.1 符號(hào)說(shuō)明與相關(guān)定義

表1所示為本文的相關(guān)符號(hào)說(shuō)明。

表1 符號(hào)說(shuō)明Table 1 Symbol description

定義3(離散高斯分布) 對(duì)于任意σ>0,定義以向量c為中心、σ為參數(shù)的格Λ上的離散高斯分布為:

1.2 相關(guān)算法與困難問(wèn)題

本文HIBE方案在系統(tǒng)建立階段,由MP12陷門(mén)生成算法和(1,v,β)-PHF得到主公鑰和主私鑰;在用戶私鑰生成階段,由MP12原像采樣算法得到用戶私鑰,由陷門(mén)派生算法得到不同分級(jí)深度用戶對(duì)應(yīng)的陷門(mén);在加密階段,由具有高最小熵[16]性質(zhì)的(u,v,β,γ,δ)-PHF得到密文。本文方案的安全性基于DLWE問(wèn)題的難解性。

2 方案結(jié)構(gòu)與模型

2.1 方案結(jié)構(gòu)

一個(gè)HIBE方案一般包括4個(gè)多項(xiàng)式時(shí)間算法:Setup,Extract,Enc,Dec[9-11],相較于普通的IBE方案,HIBE方案在Extract算法中增加了用戶私鑰派生算法。HIBE方案具體結(jié)構(gòu)如下。

1)系統(tǒng)建立算法Setup(1n):輸入安全參數(shù)n,輸出系統(tǒng)主公鑰mmpk和主私鑰mmsk。

2)用戶私鑰生成算法Extract(mmpk,mmsk,ID|l):輸入主公鑰mmpk、主私鑰mmsk及分級(jí)深度為l的用戶身份ID|l,輸出用戶私鑰Ssk。

3)加密算法Enc(mmpk,M,ID|l):輸入主公鑰mmpk、信息M和用戶身份ID|l,輸出相應(yīng)的密文C。

4)解密算法Dec(C,Ssk):輸入用戶私鑰Ssk和密文C,輸出信息M。

2.2 安全模型

HIBE方案的安全屬性包括正確性和安全性[9-11]。其中,正確性要求輸入明文M和主公鑰mmpk((mmpk,mmsk)=Setup(1n)),對(duì)于任意身份ID加密產(chǎn)生的密文C=Enc(mmpk,M,ID),有等式M=Dec(C,Ssk)成立,其中,Ssk(Extract(mmpk,mmsk,ID|l)=Ssk)是用戶私鑰。

3 方案描述

4 安全性證明

4.1 正確性證明

4.2 安全性分析

用Fi表示挑戰(zhàn)者在游戲i(i∈{0,1,…,5})中輸出1的事件。由Game0得到:

(1)

|Pr[F1]-Pr[F0]|≤Nnegl(n)

(2)

(3)

Pr[F3]=Pr[F2]

Γ3=Γ2

(4)

|Pr[F4]-Pr[F3]|≤ε′

|Γ4-Γ3|≤ε′

(5)

如果n是一個(gè)有高最小熵的(1,v,β,Nnegl(n),δ)-PHF,則會(huì)得到:

|Pr[F5]-Pr[F4]|≤Nnegl(n)

|Γ5-Γ4|≤Nnegl(n)

(6)

Γ5=0

(7)

5 性能分析

表2 各方案的陷門(mén)比較Table 2 Comparison of trapdoors of each scheme

表3 各方案的主公鑰及密文尺寸比較Table 3 Comparison of main public keys and ciphertext sizes of each scheme

表4 各方案的安全性比較Table 4 Safety comparison of each scheme

在陷門(mén)尺寸和陷門(mén)計(jì)算復(fù)雜度方面,由于文獻(xiàn)[9-11]方案采用GPV08陷門(mén)函數(shù),而本文方案采用MP12陷門(mén)函數(shù),MP12陷門(mén)在生成過(guò)程中不涉及計(jì)算代價(jià)較高的矩陣求逆操作,其計(jì)算復(fù)雜度僅相當(dāng)于2個(gè)隨機(jī)矩陣的一次乘運(yùn)算,且陷門(mén)質(zhì)量較好(即最大奇異值較低),因此,本文方案的陷門(mén)尺寸和陷門(mén)計(jì)算復(fù)雜度明顯低于文獻(xiàn)[9-11]方案。在主公鑰尺寸方面,本文方案的主公鑰主要由MP12陷門(mén)函數(shù)以及(1,v,β)-PHF函數(shù)生成,小尺寸和低維度的陷門(mén)是造成主公鑰尺寸較小的一個(gè)原因,同時(shí)用由(1,v,β)-PHF函數(shù)生成的公鑰K的集合替代文獻(xiàn)[9-11]方案中由原像采樣算法所得的矩陣集合,原像采樣算法由于輸入項(xiàng)為小整數(shù)且無(wú)法支持并行運(yùn)算,導(dǎo)致算法復(fù)雜度高,得到的矩陣維數(shù)大,而PHF函數(shù)計(jì)算復(fù)雜度低,得到的矩陣維數(shù)小,因此,本文方案的主公鑰尺寸相比文獻(xiàn)[9-11]方案有明顯減小,即隨著格維度n的增加,文獻(xiàn)[9-11]方案的主公鑰尺寸呈O(n3)和O(n)增長(zhǎng),而本文方案呈O(logbn)增長(zhǎng)。假設(shè)b≥2,則有O(logbn)≤O(n)≤O(n3)。在密文大小方面,本文方案的密文主要由(u,v,β,γ,δ)-PHF函數(shù)得到,而文獻(xiàn)[9]方案主要由輸入矩陣維度較大且計(jì)算復(fù)雜度較高的密鑰封裝算法得到,文獻(xiàn)[10-11]需要通過(guò)計(jì)算復(fù)雜度較高的原像采樣算法得到密文,且密文尺寸和密文計(jì)算效率與用戶主公鑰尺寸直接相關(guān),因此,本文方案密文尺寸較小。在安全性方面,文獻(xiàn)[10-11]方案均可達(dá)到選擇身份安全(即INDr-sID-CPA),而文獻(xiàn)[9]方案及本文方案可達(dá)到自適應(yīng)性安全(即INDr-aID-CPA),INDr-aID-CPA的安全性高于INDr-sID-CPA。

6 結(jié)束語(yǔ)

本文提出一種格上基于PHF的HIBE方案。利用計(jì)算復(fù)雜度較低的MP12陷門(mén)函數(shù)生成陷門(mén),由抗碰撞性良好的PHF得到主公鑰、主私鑰以及密文。實(shí)驗(yàn)結(jié)果表明,該方案的陷門(mén)尺寸、陷門(mén)生成計(jì)算復(fù)雜度較低,且滿足INDr-aID-CPA安全。本文方案的不足之處在于,隨著分級(jí)深度的增加,陷門(mén)維度及派生后的用戶私鑰維度將會(huì)增加,派生復(fù)雜度增加會(huì)導(dǎo)致方案整體效率降低。為解決該問(wèn)題,下一步考慮將本文方案與標(biāo)準(zhǔn)模型下格上固定維度的陷門(mén)派生函數(shù)相結(jié)合。此外,將方案的安全性提高至INDr-aID-CCA安全也是今后的研究方向。