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

黃文晉,唐春明,賈惠文

(廣州大學(xué) a.數(shù)學(xué)與信息科學(xué)學(xué)院;b.廣州數(shù)學(xué)中心;c.廣東省廣州市共建信息安全技術(shù)重點(diǎn)實(shí)驗(yàn)室，廣東 廣州 510006)

隨著網(wǎng)絡(luò)通信的用戶數(shù)量驟增以及網(wǎng)絡(luò)環(huán)境對(duì)安全性的要求越來(lái)越高，公鑰密碼基礎(chǔ)設(shè)施(Public Key Infrastructure,PKI)由于必須依賴數(shù)字證書(shū)，需要越來(lái)越強(qiáng)的存儲(chǔ)能力、查詢能力以及越來(lái)越高的安全性，其繁重的管理系統(tǒng)適應(yīng)不了當(dāng)今的網(wǎng)絡(luò)環(huán)境?；谏矸莸募用軝C(jī)制(Identity-Based Encryption,IBE)是一種經(jīng)典的公鑰加密方案，其概念首次由Shamir提出，IBE允許用戶的身份信息作為公鑰，比如用戶的郵箱地址等等[1]，加密時(shí)可以直接使用接收方的身份標(biāo)識(shí)作為公鑰，為公鑰信息的管理提供了便利，解決了PKI效率低的問(wèn)題。2001年，Boneh等[2]正式給出IBE的定義和安全模型，后來(lái)基于雙線性映射和二次剩余假設(shè)構(gòu)造的IBE方案被相繼提出，但都無(wú)法抵抗量子攻擊。

格密碼(Lattices Cryptography)是一種后量子密碼，經(jīng)過(guò)十幾年的快速發(fā)展，有著顯著的特征和優(yōu)勢(shì)：能抵抗量子攻擊、并行運(yùn)算，以及格上某些困難問(wèn)題存在最壞情況到平均情況的歸約，給格密碼方案提供了安全的保障。格密碼的研究工作由Ajtai開(kāi)始,他提出了格的困難問(wèn)題可以作為格密碼方案構(gòu)造的安全基礎(chǔ)[3]，目前格的困難問(wèn)題有2個(gè)：① Ajtai提出的小整數(shù)解問(wèn)題[3](Small Integer Solution Problem,SIS)，還有非齊次版本的變體(Inhomogeneous Small Integer Solution Problem,ISIS)；②Regev[4]提出的容錯(cuò)學(xué)習(xí)問(wèn)題(Learning With Errors Problem,LWE)，他們都給出最壞情況下基于格的問(wèn)題向平均情況下SIS問(wèn)題和LWE問(wèn)題的規(guī)約。在2007年和2009年，有學(xué)者分別提出這兩種困難問(wèn)題的基于環(huán)結(jié)構(gòu)的變體[5-6]，即R-SIS問(wèn)題和R-LWE問(wèn)題，其優(yōu)點(diǎn)是儲(chǔ)存更低，運(yùn)算效率更高，同時(shí)也存在最壞情況下基于理想格的問(wèn)題向平均情況下R-SIS問(wèn)題和R-LWE問(wèn)題規(guī)約的優(yōu)良特性。

第一個(gè)基于格的IBE方案由Gentry等[7]提出，是基于 Dual-Regev加密算法設(shè)計(jì)的。后來(lái)，有學(xué)者對(duì)此進(jìn)行了研究和改進(jìn)。2010年，Agrawal等[8]構(gòu)建了基于格的IBE方案，稱為ABB方案，他們使用的公鑰矩陣是由兩部分組成，私鑰是分兩步驟采樣而得的，雖然后來(lái)有很多學(xué)者都一直沿用這種方案，但是公鑰和私鑰內(nèi)存開(kāi)銷(xiāo)大，不切實(shí)際。2014年，Ducas等[9]構(gòu)造了一種基于NTRU格的IBE方案，公鑰矩陣是由NTRU格構(gòu)建的，因此算法效率高。2018年，Bert等[10]提出基于R-SIS和R-LWE構(gòu)建的IBE方案(Bert-Fouque-Roux-Sabt,BFRS)，他們利用了MP提出的(Micciancio-Peikert,MP)的原像采樣算法[11]，并結(jié)合GM(Genise-Micciancio，GM)提出了G-格采樣和擾動(dòng)向量的方法[12]，對(duì)私鑰的提取作了改進(jìn)和優(yōu)化，雖然效率比Ducas等提出的基于NTRU格構(gòu)建的IBE方案要高，但是公鑰和用戶私鑰的尺寸還是不夠小。而最近的研究工作由錢(qián)心緣等[13]提出了一種基于R-SIS和R-LWE構(gòu)造的IBE方案(本文簡(jiǎn)稱QW方案)，對(duì)BRFS方案進(jìn)行了優(yōu)化，并且采用了分塊復(fù)用技術(shù)，降低了密文膨脹率，但是這種技術(shù)始終存在不能降低所有用戶私鑰的內(nèi)存空間、用戶私鑰的內(nèi)存開(kāi)銷(xiāo)仍然比較大的缺點(diǎn)，還有，筆者認(rèn)為QW方案中私鑰提取算法的安全性還不夠高。

結(jié)合以上的分析以及針對(duì)以上方案的不足，本文運(yùn)用非球形高斯采樣[14]的原理，對(duì)用戶私鑰提取算法進(jìn)行改進(jìn)，從而提升格上的IBE方案的空間效率。非球形高斯的原像采樣原理由Jia等[14]在2020年提出，這種原像的分布不會(huì)泄露陷門(mén)信息，并且他們給出了2種模式：①第一種模式可以提升安全性，同時(shí)降低簽名尺寸；②第二種模式在安全性幾乎不變的情況下進(jìn)一步降低簽名尺寸。本文運(yùn)用以上的原理和方法，在理想格上研究，對(duì)QW方案的用戶私鑰提取算法作改進(jìn)，減小私鑰的內(nèi)存開(kāi)銷(xiāo)，提升方案的空間效率，力圖提升方案的安全性。

1 基本理論

本部分介紹本文所需要的理論，包括格的相關(guān)定義及其理論、IBE的基本架構(gòu)、加解密原理和理想格上的原像采樣算法。

1.1 格及其相關(guān)理論

定義1(格[15]) 給定一組n維線性無(wú)關(guān)的向量b1,b2,…,bm，格定義為

其中b1,b2,…,bm是格Λ的一組基，若定義B為格Λ的基矩陣，列由b1,b2,…,bm組成，則格Λ可以由B生成，表示為

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

格Λ的秩為m，維數(shù)為n，當(dāng)n=m時(shí)稱其為滿秩格。

定義2(分圓多項(xiàng)式環(huán)[16-17]) 令n為正整數(shù)，有理數(shù)域上n次分圓域?yàn)?ξ)，同構(gòu)于Cn=[x]/Φn(x)，其中ξ是n次本原單位根，令φ(n)為n的歐拉函數(shù)，Cn為上φ(n)維向量空間，Φn(x)為上φ(n)次不可約多項(xiàng)式。而Φ2n(x)為2n次分圓多項(xiàng)式，其中n為2的冪次方，定義R≡[x]/Φ2n(x)，即R≡[x]/xn+1。令q≥2且為正整數(shù)，定義Rq≡R/qR，表示多項(xiàng)式環(huán)R中每個(gè)多項(xiàng)式的系數(shù)模q，即Rq≡q[x]/xn+1，本文基本在Rq下進(jìn)行討論和研究。

定義4(多項(xiàng)式的系數(shù)嵌入[18])R和Rq為定義2中的多項(xiàng)式環(huán)，設(shè)p(x)∈R(Rq),多項(xiàng)式的系數(shù)嵌入定義為一個(gè)從多項(xiàng)式環(huán)到整數(shù)向量的映射

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

ψ(h)=

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

定義6(離散高斯函數(shù)[10]) 對(duì)于任意的x∈n，中心為c∈n，寬度參數(shù)為s>0的離散高斯函數(shù)定義為拓展寬度參數(shù)s的定義，協(xié)方差矩陣為Σ>0(Σ表示為正定矩陣，且Σ=BBT)，中心為c∈n的離散高斯函數(shù)定義為

定義8(對(duì)偶格，光滑參數(shù)[14,19]) 格Λ?n的對(duì)偶格定義為：Λ*={w|w,Λ?}。而光滑參數(shù)ηε(Λ)由ε>0參數(shù)化，定義為使得ρ1/s(Λ*)≤1+ε成立的s的最小值。對(duì)于Σ>0，且格Λ?span(Σ)，若則定義

定義11(DecisionR-LWEq,,m問(wèn)題[21-22]) 給定m個(gè)獨(dú)立的樣本(ai,bi)∈Rq×Rq，對(duì)于由(ai,bi)組成的需判斷來(lái)自哪種分布：(1)As,分布：其中秘密s←U(Rq)(每個(gè)樣本(ai,bi)中的s是固定)，噪音e←；上的均勻隨機(jī)分布。

R-SIS問(wèn)題、R-ISIS問(wèn)題和DecisionR-LWE問(wèn)題的困難性：R-SIS問(wèn)題和R-ISIS問(wèn)題是等價(jià)的；R-SIS問(wèn)題和DecisionR-LWE的困難性與GapSVPγ/SIVP 困難問(wèn)題等價(jià)的[20-22]。

引理1[7]設(shè)格Λ?m，其基矩陣為B，令ε>0，格Λ的光滑參數(shù)存在上界

引理4[13]設(shè)n階多項(xiàng)式x∈Rq，y∈Rq，x的系數(shù)嵌入(x1,…,xn)服從中心點(diǎn)為0，方差為η的高斯分布，而y的系數(shù)嵌入(y1,…,yn)服從中心點(diǎn)為0，方差為ξ的高斯分布，則z=xy∈Rq服從中心點(diǎn)為0，方差為nηζ的近似高斯分布。因?yàn)楦鶕?jù)定義2的說(shuō)明，z=xy∈Rq的系數(shù)嵌入為

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

因此，z=xy的每一項(xiàng)系數(shù)為zi=x0yi+x1yi-1+…+xiy0-xi+1yn-1-xi+2yn-2-…-xn-1yi+1是n個(gè)分布為中心點(diǎn)為0，方差為ηζ的線性組合，因此，z=xy的系數(shù)嵌入服從中心點(diǎn)為0，方差為n·ηζ的高斯分布。

1.2 基于身份的加密機(jī)制[7,10]

基于身份的加密機(jī)制包含4個(gè)算法：Setup、Extract、Encrypt和Decrypt。身份信息用作用戶的公鑰使用，在IBE中需要一個(gè)私鑰生成中心(Private Key Generator,PKG)，PKG根據(jù)安全參數(shù)λ給出主公鑰(Master Public Key,MPK)和主私鑰(Master Secret Key,MSK)，并用msk為每一個(gè)用戶提取相應(yīng)的私鑰。

(1) Setup，給定安全參數(shù)λ，算法Setup生成mpk和msk，Setup(1λ)→(mpk,msk)。

(2) Extract，輸入安全參數(shù)λ、mpk、msk和一個(gè)用戶身份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]提出，本文使用基于環(huán)結(jié)構(gòu)的版本。需要的參數(shù)有：多項(xiàng)式的階n，維數(shù)m，以及高斯參數(shù)s,α。

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

加密：設(shè)有一個(gè)多項(xiàng)式明文M∈R2，密文塊(b,c)是m+1維的R-LWE樣本，其中b=as+e，秘密s←U(Rq)，e←DRm,α，c=us+e′+?q/2」·M，e′←DR,α。

解密：解密密文需要通過(guò)私鑰x進(jìn)行計(jì)算，

res=c-bTx=us+e′+?q/2」·M-(aTs+eT)x，=e′-eTx+?q/2」·M，計(jì)算得出res的系數(shù)嵌入resi，若resi與0的距離小于與?q/2」的距離，則resi=0，否則resi=1。

若R-LWEq,m,DR,α困難問(wèn)題成立，則Dual-Regev公鑰加密方案是IND-CPA安全的[25]。

1.3 G-格的陷門(mén)與原像采樣算法[11-12]

IBE機(jī)制中，PKG生成的用戶公鑰需要由G-格來(lái)構(gòu)造[11]，提取用戶的私鑰則需要由MP提出的原像采樣算法[11]來(lái)求解。下面對(duì)G-格陷門(mén)[11]以及MP提出的原像采樣算法[11]作簡(jiǎn)要的介紹。

理想格上，g-向量是由常量多項(xiàng)式組成的，定義為

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

原像采樣算法問(wèn)題，是如何求解一個(gè)短的原像x∈Rm，使得aTx=u成立的問(wèn)題，在QW方案中，原像采樣算法沿用的是GM提出的G-格采樣方法和擾動(dòng)向量采樣算法[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]為了進(jìn)一步減小原像采樣算法中原像的尺寸，以及提高算法的安全性，提出了一種基于非球形高斯分布的原像采樣方法。

擾動(dòng)向量p服從的協(xié)方差矩陣為

(1)

根據(jù)引理2，不考慮關(guān)于n的可忽略概率，原像的l2范數(shù)下界為

(2)

根據(jù)引理3，原像的存儲(chǔ)尺寸的下界為

(3)

下面給出基于非球型高斯的原像采樣算法[14]，用NS-SamplePre、TrapGen、NS-GM-SampleP、GM-SamplePolyG分別表示運(yùn)用非球面高斯采樣原理的原像采樣算法、陷門(mén)生成算法、擾動(dòng)采樣算法以及g-格采樣算法(以下所表示的矩陣都是由塊矩陣組成的)。

返回：(a,T)

然后基于非球面高斯原理[14]進(jìn)行原像采樣，如算法2.2：

(2)計(jì)算v=h-1(u-ap)，

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

返回：x∈R2+k-l。

其中，算法NS-GM-SampleP按照算法GM-SampleP[12]執(zhí)行，但擾動(dòng)向量p服從的協(xié)方差矩陣為

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

針對(duì)QW方案的用戶私鑰尺寸大，本文在理想格上運(yùn)用基于非球形高斯的原像采樣算法[14]，對(duì)QW方案中的用戶私鑰提取算法做了改進(jìn)，而加密算法和解密算法不是本文改進(jìn)的地方，因此，本文不沿用QW方案中的壓縮技術(shù)、解壓技術(shù)以及不引入明文擴(kuò)張參數(shù)。

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

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

b.生成目標(biāo)u←U(Rq)。

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

a.利用散列函數(shù)計(jì)算用戶的身份標(biāo)識(shí)hid=H(id)。

得到用戶私鑰skid=x。

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

a.按照算法Setup計(jì)算aid。

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

c.計(jì)算輔助密文b=aids+e，然后計(jì)算密文塊：c=us+e′+?q/2」·M。

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

對(duì)密文塊解密：res=c′-b′Tx，res∈Rq為明文塊，設(shè)res的系數(shù)嵌入為resi，若resi與0的距離小于與?q/2」的距離，則resi=0，否則resi=1。

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

3.2 方案的正確性分析與誤差分析

(4)

其中t為高斯函數(shù)的尾切參數(shù)[10]。

3.3 方案的安全性分析

為了證明本文的IBE方案是IND-sID-CPA的，采用安全游戲序列的方法，需要攻擊者A和具備IND-sID-CPA能力的挑戰(zhàn)者B進(jìn)行4輪安全游戲，而在最后一輪游戲中，攻擊者A很難從密文塊中得到明文信息[13]，最后一輪攻擊者的優(yōu)勢(shì)為0，因此，本部分只考慮前三輪游戲，然后計(jì)算攻擊者A擁有的優(yōu)勢(shì)，從而證明本文的IBE方案是IND-sID-CPA的。

綜合以上3輪安全游戲，由于本方案的設(shè)計(jì)是基于R-ISISq,β,ω問(wèn)題DecisonR-LWEq,,ω問(wèn)題的困難性，攻擊者A具有的優(yōu)勢(shì)：λ)，可見(jiàn)攻擊者A優(yōu)勢(shì)是可忽略的，因此本方案是IND-sID-CPA的。

4 方案的結(jié)果與分析

本方案運(yùn)用了基于非球形高斯的原像采樣原理后，其中模式2可以減小用戶私鑰x的尺寸，模式1可以減小用戶私鑰x的l2范數(shù)的上界，同時(shí)也可以降低用戶私鑰的尺寸。表1為2種方案在用戶私鑰x的尺寸以及用戶私鑰x的l2范數(shù)上界的對(duì)比。

表1 用戶私鑰尺寸和范數(shù)上界的對(duì)比Table 1 Comparison of the upper bound of the norm and size of the user’s private key

通過(guò)以上分析，本文將在2種模式下與QW方案比較，計(jì)算用戶私鑰skid的尺寸(以kB為單位)，以及評(píng)估ISIS問(wèn)題的安全性和LWE問(wèn)題的安全性。

5 結(jié) 論

本文運(yùn)用基于非球形高斯的原像采樣算法[14]，對(duì)QW方案的私鑰提取算法進(jìn)行了改進(jìn)，在保證IBE的正確性的情況下，降低其私鑰skid的尺寸，以及提升了ISIS問(wèn)題的安全性，但未能提升方案的安全性。

但本研究的貢獻(xiàn)在于有效降低了用戶私鑰的尺寸，提升了方案的空間效率。由表2所示，本方案的模式1中，在42.6-bit的安全性下，用戶私鑰的尺寸由21.75 kB減小至13.31 kB，ISIS問(wèn)題的安全性由127.9-bit提升至172.8-bit；在109.8-bit的安全性下，用戶私鑰的尺寸由50.36 kB減小至32.25 kB，ISIS問(wèn)題的安全性由286.7-bit提升至373.8-bit，雖然模式1可以提高ISIS問(wèn)題的安全性，但由于LWE問(wèn)題的安全性相對(duì)較低，因此，無(wú)法提升方案的安全性。本方案的模式2在 ISIS問(wèn)題的安全性幾乎一樣的情況下可以更有效地降低用戶私鑰skid的尺寸，在42.6-bit的安全性下，用戶私鑰的尺寸由21.75 kB減小至10.18 kB；在109.8-bit的安全性下，用戶私鑰的尺寸由50.36 kB減小至21.86 kB，節(jié)省了大約60%的內(nèi)存空間，相比于模式1，模式2能更有效地節(jié)省用戶私鑰的內(nèi)存開(kāi)銷(xiāo)。綜合表2可得，本方案的用戶私鑰可以節(jié)省大約40%～60%的內(nèi)存空間。

表2 QW方案[13]與本方案在用戶私鑰尺寸與安全性上的對(duì)比Table 2 Comparison of the secret key size and security

綜上所述，本研究運(yùn)用了基于非球形高斯的原像采樣算法[14]，對(duì)QW方案的私鑰提取算法進(jìn)行了改進(jìn)，本方案的2種模式均可有效地減少用戶私鑰的內(nèi)存開(kāi)銷(xiāo)。雖然無(wú)法提升IBE方案的安全性，但實(shí)驗(yàn)結(jié)果表明，模式1可以提升ISIS的安全性，并且減小了用戶私鑰的尺寸；模式2在ISIS安全性幾乎一樣的情況下，能更有效地節(jié)省用戶私鑰的內(nèi)存開(kāi)銷(xiāo)。