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

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

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

0 概述

1984年,SHAMIR A提出了基于身份的公鑰密碼體制[1],在該體制中,公鑰是用來表示用戶身份標志的一組任意的字符串,如E-mail地址或電話號碼等,相應的私鑰則由私鑰生成器(Private-Key Generator,PKG)生成。基于身份的加密(Identity-Based Encryption,IBE)方案的提出,消除了傳統(tǒng)公鑰加密方案對用戶證書的依賴,極大地簡化了密鑰管理系統(tǒng)。基于分級身份的加密(Hierarchical Identity-Based Encryption,HIBE)是一種公鑰加密方案[2-3],其中,用戶實體被安排在一棵定向樹上,每個用戶對應于樹上的不同節(jié)點,且可以從相應的父節(jié)點處得到用戶私鑰,同時還可以將該私鑰派生給相應的子節(jié)點,子節(jié)點利用派生后的用戶私鑰解密消息或者繼續(xù)將私鑰派生給相應的子節(jié)點,但是不可以解密樹上其他節(jié)點的密文。上述派生過程是單向的,即子節(jié)點無法用自己的私鑰來恢復父節(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)造出一個標準模型下的HIBE方案。同年,文獻[10-11]分別提出了標準模型下格上固定維度的HIBE方案和標準模型下格上HIBE方案。2012年,文獻[12]提出一種適應性安全的標準模型下的高效格基(H)IBE方案。2014年,文獻[13]將廣播加密與HIBE方案相結(jié)合,提出一種格上基于分級身份基的廣播加密方案。但是,上述方案大多存在陷門生成計算復雜度較高(算法執(zhí)行過程復雜,且輸出矩陣維度較高)以及主公鑰尺寸較大的問題。

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

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

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

1 預備知識

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原像采樣算法得到用戶私鑰,由陷門派生算法得到不同分級深度用戶對應的陷門;在加密階段,由具有高最小熵[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,輸出相應的密文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

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

6 結(jié)束語

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