格上基于可编程哈希函数的HIBE方案

叶 青,王明明,汤永利,秦攀科,王永军

(河南理工大学 计算机科学与技术学院,河南 焦作 454000)

0 概述

1984年,SHAMIR A提出了基于身份的公钥密码体制[1],在该体制中,公钥是用来表示用户身份标志的一组任意的字符串,如E-mail地址或电话号码等,相应的私钥则由私钥生成器(Private-Key Generator,PKG)生成。基于身份的加密(Identity-Based Encryption,IBE)方案的提出,消除了传统公钥加密方案对用户证书的依赖,极大地简化了密钥管理系统。基于分级身份的加密(Hierarchical Identity-Based Encryption,HIBE)是一种公钥加密方案[2-3],其中,用户实体被安排在一棵定向树上,每个用户对应于树上的不同节点,且可以从相应的父节点处得到用户私钥,同时还可以将该私钥派生给相应的子节点,子节点利用派生后的用户私钥解密消息或者继续将私钥派生给相应的子节点,但是不可以解密树上其他节点的密文。上述派生过程是单向的,即子节点无法用自己的私钥来恢复父节点私钥。较早的HIBE方案[4-5]大多基于数论难题(如大整数因子分解难题和有限域离散对数难题)而构建,随着量子计算机的发展,基于数论难题的HIBE方案都能够在多项式时间内被攻破,因此,研究抗量子攻击的替代密码方案成为该领域亟需解决的问题。近年来,基于格构造的新型密码系统因具有运算简单、存在最坏情况下的随机实例、较高的渐进效率以及抗量子攻击的特点,成为后量子时代密码领域的研究热点之一[6-7]。2008年,文献[8]构造出格上基于身份的加密方案。2010年,文献[9]采用盆景树系统构造出一个标准模型下的HIBE方案。同年,文献[10-11]分别提出了标准模型下格上固定维度的HIBE方案和标准模型下格上HIBE方案。2012年,文献[12]提出一种适应性安全的标准模型下的高效格基(H)IBE方案。2014年,文献[13]将广播加密与HIBE方案相结合,提出一种格上基于分级身份基的广播加密方案。但是,上述方案大多存在陷门生成计算复杂度较高(算法执行过程复杂,且输出矩阵维度较高)以及主公钥尺寸较大的问题。

2012年,文献[14]提出了一种新的格上陷门生成算法(MP12陷门生成算法)以及与之对应的原像采样算法(MP12原像采样算法),相比之前广泛应用的陷门生成算法GPV08[15],该陷门算法的生成过程简单,复杂度仅相当于2个随机矩阵的一次乘运算,且不涉及计算代价高的矩阵求逆操作和HNF(Hermite Normal Form)。MP12原像采样算法比较简单高效,算法支持并行运算且输入项为小整数,对离线空间的需求较低。文献[16-17]基于MP12陷门函数对格上IBE方案进行改进,提出一种陷门生成与派生相结合的格上IBE方案,该方案复杂度较低且实用性较强。

2012年,文献[18]提出了可编程哈希函数(Programmable Hash Function,PHF)的概念,构建了基于双线性映射的加密方案与基于RSA的签名方案,这2个方案的共同特点是签名尺寸相较以往签名方案有所减小,安全性也得到提高,但却增加了公钥尺寸。针对该问题,2015年,文献[19]提出了不对称PHF的概念,并利用该函数构建一种标准模型下的线性全同态签名方案,同时证明新签名方案的公钥尺寸明显小于文献[18]的签名方案。2016年,文献[20]提出了格上PHF的概念,其不仅继承了传统PHF的特点,而且结合了格的分区证明技巧,该文献用格上PHF重新构建了格上的签名方案和IBE方案,相较以往相关方案,基于格上PHF的新签名方案的主公钥尺寸明显减小。

为降低标准模型下HIBE方案的陷门生成计算复杂度,减小主公钥尺寸,本文结合格上PHF[20]和MP12陷门函数[14]构建一种新的HIBE方案。将IBE方案[20]扩展为HIBE方案,利用PHF设计系统建立算法和加密算法,方案中的陷门由MP12陷门函数生成,以降低计算复杂度。在此基础上,利用标准模型下格上基于判定性容错学习(DLWE)问题来验证该方案满足INDr-aID-CPA安全。

1 预备知识

1.1 符号说明与相关定义

表1所示为本文的相关符号说明。

表1 符号说明Table 1 Symbol description

定义3(离散高斯分布) 对于任意σ>0,定义以向量c为中心、σ为参数的格Λ上的离散高斯分布为:

1.2 相关算法与困难问题

本文HIBE方案在系统建立阶段,由MP12陷门生成算法和(1,v,β)-PHF得到主公钥和主私钥;在用户私钥生成阶段,由MP12原像采样算法得到用户私钥,由陷门派生算法得到不同分级深度用户对应的陷门;在加密阶段,由具有高最小熵[16]性质的(u,v,β,γ,δ)-PHF得到密文。本文方案的安全性基于DLWE问题的难解性。

2 方案结构与模型

2.1 方案结构

一个HIBE方案一般包括4个多项式时间算法:Setup,Extract,Enc,Dec[9-11],相较于普通的IBE方案,HIBE方案在Extract算法中增加了用户私钥派生算法。HIBE方案具体结构如下。

1)系统建立算法Setup(1n):输入安全参数n,输出系统主公钥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加密产生的密文C=Enc(mmpk,M,ID),有等式M=Dec(C,Ssk)成立,其中,Ssk(Extract(mmpk,mmsk,ID|l)=Ssk)是用户私钥。

3 方案描述

4 安全性证明

4.1 正确性证明

4.2 安全性分析

用Fi表示挑战者在游戏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陷门函数,而本文方案采用MP12陷门函数,MP12陷门在生成过程中不涉及计算代价较高的矩阵求逆操作,其计算复杂度仅相当于2个随机矩阵的一次乘运算,且陷门质量较好(即最大奇异值较低),因此,本文方案的陷门尺寸和陷门计算复杂度明显低于文献[9-11]方案。在主公钥尺寸方面,本文方案的主公钥主要由MP12陷门函数以及(1,v,β)-PHF函数生成,小尺寸和低维度的陷门是造成主公钥尺寸较小的一个原因,同时用由(1,v,β)-PHF函数生成的公钥K的集合替代文献[9-11]方案中由原像采样算法所得的矩阵集合,原像采样算法由于输入项为小整数且无法支持并行运算,导致算法复杂度高,得到的矩阵维数大,而PHF函数计算复杂度低,得到的矩阵维数小,因此,本文方案的主公钥尺寸相比文献[9-11]方案有明显减小,即随着格维度n的增加,文献[9-11]方案的主公钥尺寸呈O(n3)和O(n)增长,而本文方案呈O(logbn)增长。假设b≥2,则有O(logbn)≤O(n)≤O(n3)。在密文大小方面,本文方案的密文主要由(u,v,β,γ,δ)-PHF函数得到,而文献[9]方案主要由输入矩阵维度较大且计算复杂度较高的密钥封装算法得到,文献[10-11]需要通过计算复杂度较高的原像采样算法得到密文,且密文尺寸和密文计算效率与用户主公钥尺寸直接相关,因此,本文方案密文尺寸较小。在安全性方面,文献[10-11]方案均可达到选择身份安全(即INDr-sID-CPA),而文献[9]方案及本文方案可达到自适应性安全(即INDr-aID-CPA),INDr-aID-CPA的安全性高于INDr-sID-CPA。

6 结束语

本文提出一种格上基于PHF的HIBE方案。利用计算复杂度较低的MP12陷门函数生成陷门,由抗碰撞性良好的PHF得到主公钥、主私钥以及密文。实验结果表明,该方案的陷门尺寸、陷门生成计算复杂度较低,且满足INDr-aID-CPA安全。本文方案的不足之处在于,随着分级深度的增加,陷门维度及派生后的用户私钥维度将会增加,派生复杂度增加会导致方案整体效率降低。为解决该问题,下一步考虑将本文方案与标准模型下格上固定维度的陷门派生函数相结合。此外,将方案的安全性提高至INDr-aID-CCA安全也是今后的研究方向。