理想格上基于身份的加密算法研究

黄文晋,唐春明,贾惠文

(广州大学 a.数学与信息科学学院;b.广州数学中心;c.广东省广州市共建信息安全技术重点实验室，广东 广州 510006)

随着网络通信的用户数量骤增以及网络环境对安全性的要求越来越高，公钥密码基础设施(Public Key Infrastructure,PKI)由于必须依赖数字证书，需要越来越强的存储能力、查询能力以及越来越高的安全性，其繁重的管理系统适应不了当今的网络环境。基于身份的加密机制(Identity-Based Encryption,IBE)是一种经典的公钥加密方案，其概念首次由Shamir提出，IBE允许用户的身份信息作为公钥，比如用户的邮箱地址等等[1]，加密时可以直接使用接收方的身份标识作为公钥，为公钥信息的管理提供了便利，解决了PKI效率低的问题。2001年，Boneh等[2]正式给出IBE的定义和安全模型，后来基于双线性映射和二次剩余假设构造的IBE方案被相继提出，但都无法抵抗量子攻击。

格密码(Lattices Cryptography)是一种后量子密码，经过十几年的快速发展，有着显著的特征和优势：能抵抗量子攻击、并行运算，以及格上某些困难问题存在最坏情况到平均情况的归约，给格密码方案提供了安全的保障。格密码的研究工作由Ajtai开始,他提出了格的困难问题可以作为格密码方案构造的安全基础[3]，目前格的困难问题有2个：① Ajtai提出的小整数解问题[3](Small Integer Solution Problem,SIS)，还有非齐次版本的变体(Inhomogeneous Small Integer Solution Problem,ISIS)；②Regev[4]提出的容错学习问题(Learning With Errors Problem,LWE)，他们都给出最坏情况下基于格的问题向平均情况下SIS问题和LWE问题的规约。在2007年和2009年，有学者分别提出这两种困难问题的基于环结构的变体[5-6]，即R-SIS问题和R-LWE问题，其优点是储存更低，运算效率更高，同时也存在最坏情况下基于理想格的问题向平均情况下R-SIS问题和R-LWE问题规约的优良特性。

第一个基于格的IBE方案由Gentry等[7]提出，是基于 Dual-Regev加密算法设计的。后来，有学者对此进行了研究和改进。2010年，Agrawal等[8]构建了基于格的IBE方案，称为ABB方案，他们使用的公钥矩阵是由两部分组成，私钥是分两步骤采样而得的，虽然后来有很多学者都一直沿用这种方案，但是公钥和私钥内存开销大，不切实际。2014年，Ducas等[9]构造了一种基于NTRU格的IBE方案，公钥矩阵是由NTRU格构建的，因此算法效率高。2018年，Bert等[10]提出基于R-SIS和R-LWE构建的IBE方案(Bert-Fouque-Roux-Sabt,BFRS)，他们利用了MP提出的(Micciancio-Peikert,MP)的原像采样算法[11]，并结合GM(Genise-Micciancio，GM)提出了G-格采样和扰动向量的方法[12]，对私钥的提取作了改进和优化，虽然效率比Ducas等提出的基于NTRU格构建的IBE方案要高，但是公钥和用户私钥的尺寸还是不够小。而最近的研究工作由钱心缘等[13]提出了一种基于R-SIS和R-LWE构造的IBE方案(本文简称QW方案)，对BRFS方案进行了优化，并且采用了分块复用技术，降低了密文膨胀率，但是这种技术始终存在不能降低所有用户私钥的内存空间、用户私钥的内存开销仍然比较大的缺点，还有，笔者认为QW方案中私钥提取算法的安全性还不够高。

结合以上的分析以及针对以上方案的不足，本文运用非球形高斯采样[14]的原理，对用户私钥提取算法进行改进，从而提升格上的IBE方案的空间效率。非球形高斯的原像采样原理由Jia等[14]在2020年提出，这种原像的分布不会泄露陷门信息，并且他们给出了2种模式：①第一种模式可以提升安全性，同时降低签名尺寸；②第二种模式在安全性几乎不变的情况下进一步降低签名尺寸。本文运用以上的原理和方法，在理想格上研究，对QW方案的用户私钥提取算法作改进，减小私钥的内存开销，提升方案的空间效率，力图提升方案的安全性。

1 基本理论

本部分介绍本文所需要的理论，包括格的相关定义及其理论、IBE的基本架构、加解密原理和理想格上的原像采样算法。

1.1 格及其相关理论

定义1(格[15]) 给定一组n维线性无关的向量b1,b2,…,bm，格定义为

其中b1,b2,…,bm是格Λ的一组基，若定义B为格Λ的基矩阵，列由b1,b2,…,bm组成，则格Λ可以由B生成，表示为

Λ=L(B)={Bx|x∈m}，

格Λ的秩为m，维数为n，当n=m时称其为满秩格。

定义2(分圆多项式环[16-17]) 令n为正整数，有理数域上n次分圆域为(ξ)，同构于Cn=[x]/Φn(x)，其中ξ是n次本原单位根，令φ(n)为n的欧拉函数，Cn为上φ(n)维向量空间，Φn(x)为上φ(n)次不可约多项式。而Φ2n(x)为2n次分圆多项式，其中n为2的幂次方，定义R≡[x]/Φ2n(x)，即R≡[x]/xn+1。令q≥2且为正整数，定义Rq≡R/qR，表示多项式环R中每个多项式的系数模q，即Rq≡q[x]/xn+1，本文基本在Rq下进行讨论和研究。

定义4(多项式的系数嵌入[18])R和Rq为定义2中的多项式环，设p(x)∈R(Rq),多项式的系数嵌入定义为一个从多项式环到整数向量的映射

p(x)p=(p0,…,pn-1)。

ψ(h)=

(v0,…,vn-1)(v0,0,…,v0,n-1,…,vl-1,0,…,vl-1,n-1)。

定义6(离散高斯函数[10]) 对于任意的x∈n，中心为c∈n，宽度参数为s>0的离散高斯函数定义为拓展宽度参数s的定义，协方差矩阵为Σ>0(Σ表示为正定矩阵，且Σ=BBT)，中心为c∈n的离散高斯函数定义为

定义8(对偶格，光滑参数[14,19]) 格Λ⊂n的对偶格定义为：Λ*={w|w,Λ⊆}。而光滑参数ηε(Λ)由ε>0参数化，定义为使得ρ1/s(Λ*)≤1+ε成立的s的最小值。对于Σ>0，且格Λ⊂span(Σ)，若则定义

定义11(DecisionR-LWEq,,m问题[21-22]) 给定m个独立的样本(ai,bi)∈Rq×Rq，对于由(ai,bi)组成的需判断来自哪种分布：(1)As,分布：其中秘密s←U(Rq)(每个样本(ai,bi)中的s是固定)，噪音e←；上的均匀随机分布。

R-SIS问题、R-ISIS问题和DecisionR-LWE问题的困难性：R-SIS问题和R-ISIS问题是等价的；R-SIS问题和DecisionR-LWE的困难性与GapSVPγ/SIVP 困难问题等价的[20-22]。

引理1[7]设格Λ⊂m，其基矩阵为B，令ε>0，格Λ的光滑参数存在上界

引理4[13]设n阶多项式x∈Rq，y∈Rq，x的系数嵌入(x1,…,xn)服从中心点为0，方差为η的高斯分布，而y的系数嵌入(y1,…,yn)服从中心点为0，方差为ξ的高斯分布，则z=xy∈Rq服从中心点为0，方差为nηζ的近似高斯分布。因为根据定义2的说明，z=xy∈Rq的系数嵌入为

(z1,…,zn)=(x0,…,xn)·

因此，z=xy的每一项系数为zi=x0yi+x1yi-1+…+xiy0-xi+1yn-1-xi+2yn-2-…-xn-1yi+1是n个分布为中心点为0，方差为ηζ的线性组合，因此，z=xy的系数嵌入服从中心点为0，方差为n·ηζ的高斯分布。

1.2 基于身份的加密机制[7,10]

基于身份的加密机制包含4个算法：Setup、Extract、Encrypt和Decrypt。身份信息用作用户的公钥使用，在IBE中需要一个私钥生成中心(Private Key Generator,PKG)，PKG根据安全参数λ给出主公钥(Master Public Key,MPK)和主私钥(Master Secret Key,MSK)，并用msk为每一个用户提取相应的私钥。

(1) Setup，给定安全参数λ，算法Setup生成mpk和msk，Setup(1λ)→(mpk,msk)。

(2) Extract，输入安全参数λ、mpk、msk和一个用户身份id，然后利用私钥提取算法，输出属于该用户的私钥(Secret Key,SK)，skid←Extract(mpk,msk,id)。

(3) Encrypt，输入mpk，用户身份id、明文M，输出密文C，C←Encrypt(mpk,id,M)。

(4) Decrypt，输入sk、C，输出明文M，M←Decrypt(skid,C)。

Dual-Regev公钥加密最先由Gentry等[7]提出，本文使用基于环结构的版本。需要的参数有：多项式的阶n，维数m，以及高斯参数s,α。

mpk和sk的生成：mpk=(a,u)，其中u←U(Rq)，用户私钥x←DRm,s，且满足aTx=u∈Rq。

加密：设有一个多项式明文M∈R2，密文块(b,c)是m+1维的R-LWE样本，其中b=as+e，秘密s←U(Rq)，e←DRm,α，c=us+e′+⎣q/2」·M，e′←DR,α。

解密：解密密文需要通过私钥x进行计算，

res=c-bTx=us+e′+⎣q/2」·M-(aTs+eT)x，=e′-eTx+⎣q/2」·M，计算得出res的系数嵌入resi，若resi与0的距离小于与⎣q/2」的距离，则resi=0，否则resi=1。

若R-LWEq,m,DR,α困难问题成立，则Dual-Regev公钥加密方案是IND-CPA安全的[25]。

1.3 G-格的陷门与原像采样算法[11-12]

IBE机制中，PKG生成的用户公钥需要由G-格来构造[11]，提取用户的私钥则需要由MP提出的原像采样算法[11]来求解。下面对G-格陷门[11]以及MP提出的原像采样算法[11]作简要的介绍。

理想格上，g-向量是由常量多项式组成的，定义为

gT=(1,b,…,bk-1)∈R1×k,

原像采样算法问题，是如何求解一个短的原像x∈Rm，使得aTx=u成立的问题，在QW方案中，原像采样算法沿用的是GM提出的G-格采样方法和扰动向量采样算法[12]，不妨记作GM-SamplePolyG算法[12]和GM-SampleP算法[12]，其步骤如下：

算法1.1[10-12]SamplePre(a,u,T,h,s,σ)

输出：x∈Rm，使得aTx=u成立，

(1)p←GM-SampleP(q,s,σ,T)，v=h-1(u-ap)，

返回：x。

aTp+hh-1(u-aTp)=u。

2 基于非球形高斯的原像采样[14]

Jia等[14]为了进一步减小原像采样算法中原像的尺寸，以及提高算法的安全性，提出了一种基于非球形高斯分布的原像采样方法。

扰动向量p服从的协方差矩阵为

(1)

根据引理2，不考虑关于n的可忽略概率，原像的l2范数下界为

(2)

根据引理3，原像的存储尺寸的下界为

(3)

下面给出基于非球型高斯的原像采样算法[14]，用NS-SamplePre、TrapGen、NS-GM-SampleP、GM-SamplePolyG分别表示运用非球面高斯采样原理的原像采样算法、陷门生成算法、扰动采样算法以及g-格采样算法(以下所表示的矩阵都是由块矩阵组成的)。

返回：(a,T)

然后基于非球面高斯原理[14]进行原像采样，如算法2.2：

(2)计算v=h-1(u-ap)，

(3)采样z←GM-SamplePolyG(σ,v)，

返回：x∈R2+k-l。

其中，算法NS-GM-SampleP按照算法GM-SampleP[12]执行，但扰动向量p服从的协方差矩阵为

3 基于非球形高斯的IBE方案

针对QW方案的用户私钥尺寸大，本文在理想格上运用基于非球形高斯的原像采样算法[14]，对QW方案中的用户私钥提取算法做了改进，而加密算法和解密算法不是本文改进的地方，因此，本文不沿用QW方案中的压缩技术、解压技术以及不引入明文扩张参数。

3.1 基于非球形高斯的IBE方案

(1)Setup(1λ)→(mpk,msk)

b.生成目标u←U(Rq)。

(2)New-Extract(mpk,msk,id)→skid

a.利用散列函数计算用户的身份标识hid=H(id)。

得到用户私钥skid=x。

(3)Encrypt(mpk,id,M=(m1,…,mn)∈R2)→C。

a.按照算法Setup计算aid。

b.采样R-LWE的秘密s←U(Rq)以及噪声e←DRm,α,e′←DR,α。

c.计算辅助密文b=aids+e，然后计算密文块：c=us+e′+⎣q/2」·M。

(4)QW-Decrypt(skid,(b,c))→res=(res1,…,resn)

对密文块解密：res=c′-b′Tx，res∈Rq为明文块，设res的系数嵌入为resi，若resi与0的距离小于与⎣q/2」的距离，则resi=0，否则resi=1。

最后得到明文块res=(res1,…,resn)，完成解密。

3.2 方案的正确性分析与误差分析

(4)

其中t为高斯函数的尾切参数[10]。

3.3 方案的安全性分析

为了证明本文的IBE方案是IND-sID-CPA的，采用安全游戏序列的方法，需要攻击者A和具备IND-sID-CPA能力的挑战者B进行4轮安全游戏，而在最后一轮游戏中，攻击者A很难从密文块中得到明文信息[13]，最后一轮攻击者的优势为0，因此，本部分只考虑前三轮游戏，然后计算攻击者A拥有的优势，从而证明本文的IBE方案是IND-sID-CPA的。

综合以上3轮安全游戏，由于本方案的设计是基于R-ISISq,β,ω问题DecisonR-LWEq,,ω问题的困难性，攻击者A具有的优势：λ)，可见攻击者A优势是可忽略的，因此本方案是IND-sID-CPA的。

4 方案的结果与分析

本方案运用了基于非球形高斯的原像采样原理后，其中模式2可以减小用户私钥x的尺寸，模式1可以减小用户私钥x的l2范数的上界，同时也可以降低用户私钥的尺寸。表1为2种方案在用户私钥x的尺寸以及用户私钥x的l2范数上界的对比。

表1 用户私钥尺寸和范数上界的对比Table 1 Comparison of the upper bound of the norm and size of the user’s private key

通过以上分析，本文将在2种模式下与QW方案比较，计算用户私钥skid的尺寸(以kB为单位)，以及评估ISIS问题的安全性和LWE问题的安全性。

5 结 论

本文运用基于非球形高斯的原像采样算法[14]，对QW方案的私钥提取算法进行了改进，在保证IBE的正确性的情况下，降低其私钥skid的尺寸，以及提升了ISIS问题的安全性，但未能提升方案的安全性。

但本研究的贡献在于有效降低了用户私钥的尺寸，提升了方案的空间效率。由表2所示，本方案的模式1中，在42.6-bit的安全性下，用户私钥的尺寸由21.75 kB减小至13.31 kB，ISIS问题的安全性由127.9-bit提升至172.8-bit；在109.8-bit的安全性下，用户私钥的尺寸由50.36 kB减小至32.25 kB，ISIS问题的安全性由286.7-bit提升至373.8-bit，虽然模式1可以提高ISIS问题的安全性，但由于LWE问题的安全性相对较低，因此，无法提升方案的安全性。本方案的模式2在 ISIS问题的安全性几乎一样的情况下可以更有效地降低用户私钥skid的尺寸，在42.6-bit的安全性下，用户私钥的尺寸由21.75 kB减小至10.18 kB；在109.8-bit的安全性下，用户私钥的尺寸由50.36 kB减小至21.86 kB，节省了大约60%的内存空间，相比于模式1，模式2能更有效地节省用户私钥的内存开销。综合表2可得，本方案的用户私钥可以节省大约40%～60%的内存空间。

表2 QW方案[13]与本方案在用户私钥尺寸与安全性上的对比Table 2 Comparison of the secret key size and security

综上所述，本研究运用了基于非球形高斯的原像采样算法[14]，对QW方案的私钥提取算法进行了改进，本方案的2种模式均可有效地减少用户私钥的内存开销。虽然无法提升IBE方案的安全性，但实验结果表明，模式1可以提升ISIS的安全性，并且减小了用户私钥的尺寸；模式2在ISIS安全性几乎一样的情况下，能更有效地节省用户私钥的内存开销。