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

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

0 概述

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

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

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

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

1 預(yù)備知識

1.1 符號說明與相關(guān)定義

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

表1 符號說明Table 1 Symbol description

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

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

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

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

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

一個HIBE方案一般包括4個多項式時間算法: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及分級深度為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)),對于任意身份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是一個有高最小熵的(1,v,β,Nnegl(n),δ)-PHF,則會得到:

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

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

(6)

Γ5=0

(7)

5 性能分析

表2 各方案的陷門比較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

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

6 結(jié)束語

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