基于NTRU的單向抗合謀代理重加密方案*

張明武,杜 林

1.湖北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,武漢430068

2.密碼科學(xué)技術(shù)國家重點(diǎn)實(shí)驗(yàn)室,北京100878

3.廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室,桂林541004

1 引言

代理重加密是一種非對稱公鑰加密體制,一個(gè)半可信的代理使用重加密密鑰將授權(quán)者公鑰加密的密文轉(zhuǎn)換成可用被授權(quán)者私鑰解密的密文[1,2].這一轉(zhuǎn)換特性使其在公鑰加密領(lǐng)域得以大展身手,如在分布式文件系統(tǒng)、數(shù)字版權(quán)保護(hù)、加密垃圾郵件過濾、云計(jì)算中的應(yīng)用等,使用云服務(wù)器作為半可信代理人進(jìn)行代理重加密過程如圖1所示.而為了實(shí)現(xiàn)代理重加密方案,則需要給代理者一個(gè)重加密密鑰,但在重加密密鑰的設(shè)計(jì)中需要考慮的是,防止代理者與被授權(quán)者合謀獲得授權(quán)者的私鑰或代理者與授權(quán)者合謀獲得被授權(quán)者的私鑰,最重要的是要保證被授權(quán)者解密的正確性.

最初的代理重加密方案是由Blaze等人[2]在歐洲密碼學(xué)年會(huì)上提出的,但是該方案無法抵抗合謀攻擊,即被授權(quán)者能與代理者合謀獲取授權(quán)者的私鑰,此外該方案是雙向重加密的,即代理者既能將A的密文轉(zhuǎn)換成B的密文,也能將B的密文轉(zhuǎn)換成A能解密的密文.Ateniese等人[3]利用雙線性配對(bilinear-pairing)構(gòu)造出首個(gè)單向代理重加密方案,該方案是單跳的,且能抗合謀攻擊,而且在標(biāo)準(zhǔn)模型下達(dá)到了CPA安全,該方案基于雙線性對上判定性Diffie-Hellman假設(shè).Canetti和Hohenberger[4]于2007年首次提出了基于標(biāo)準(zhǔn)模型的選擇密文安全(CCA)安全雙向代理重加密方案,為了達(dá)到CCA級別安全性,密文設(shè)計(jì)中采用了一次性簽名方案,但該方案無法抵擋合謀攻擊.Liu等人[5]提出了一種用于文件共享系統(tǒng)的多條件代理廣播重加密(MC-PBRE)方案,在標(biāo)準(zhǔn)模型中達(dá)到了CCA安全,此外,該方案可以抵抗合謀攻擊.Paul等人[6]提出一種新的抗共謀 IB-PRE方案,該方案是基于 Diffie-Hellman假設(shè),且在隨機(jī)預(yù)言機(jī)模型下達(dá)到了自適應(yīng)CCA安全性[7].

圖1 云服務(wù)器代理重加密Figure 1 Cloud-server based proxy re-encryption

以上方案的安全基礎(chǔ)都是基于數(shù)論中的大素?cái)?shù)因子分解、離散對數(shù)或雙線性群上的困難問題假設(shè).1994年美國貝爾實(shí)驗(yàn)室的科學(xué)家 Peter Shor提出了一種破解上述困難問題的算法[8],從理論上證明了這種算法可以在極短的時(shí)間內(nèi)破解上述問題,雖然其前提條件是大規(guī)模量子計(jì)算機(jī)的使用,但隨著量子計(jì)算機(jī)技術(shù)的快速發(fā)展,這種破解的可能性正在極速變大.因此,研發(fā)針對量子攻擊的公鑰加密技術(shù)刻不容緩.所幸的是,學(xué)界已經(jīng)研究出了數(shù)種抗量子密碼,它們大體上可以分為四類,即基于編碼的算法(Codebased)、基于多變量多項(xiàng)式的加密算法(Multi-variable polynomial)、基于安全散列函數(shù)的算法(Secure Hash-based),以及格基加密算法(Lattice-based).其中,基于格密碼系統(tǒng)在過去十年中得到了最為廣泛的關(guān)注.與大素?cái)?shù)分解和離散對數(shù)問題不同,目前還沒有量子算法可以借助量子計(jì)算機(jī)在多項(xiàng)式時(shí)間內(nèi)對其進(jìn)行破解,而且,格密碼系統(tǒng)在最壞情況假設(shè)條件下依然具備安全性.

在現(xiàn)有公鑰密碼系統(tǒng)中,例如RSA公鑰加密體制,它的安全性是來自生成密鑰需要選擇2個(gè)既是質(zhì)數(shù)又能形成分解困難問題實(shí)例的隨機(jī)大數(shù),但是在這個(gè)過程中存在選擇錯(cuò)誤數(shù)字而導(dǎo)致安全性下降的可能性.而在格密碼系統(tǒng)中,所有可能的密鑰選擇方式都能夠形成足夠的困難性.基于格有兩個(gè)經(jīng)典的困難問題,一個(gè)是最短向量問題 (Shortest Vector Problem,SVP),即在格內(nèi)找到最短的非零向量,另一個(gè)是最近向量問題 (Closet vector problem,CVP),即在格中找到一個(gè)距離目標(biāo)向量最近的非零向量.目前,NTRU(Number Theory Research Unit)加密體制以及基于帶錯(cuò)誤學(xué)習(xí)問題 (Learning With Error,LWE)[9]的加密方案是基于格密碼系統(tǒng)發(fā)展實(shí)用前景最好的兩種加密算法.Hoffstein、Pipher和Silverman[10]于1996年提出首個(gè)基于格的NTRU加密體制.從那時(shí)起,它一直是最實(shí)用的基于格的公鑰密碼體制,并被IEEESTD 1363.1-2008[11]和ANSI X9.98-2010[12]標(biāo)準(zhǔn)化.NTRU得到廣泛研究和應(yīng)用的另一個(gè)原因是它相對于傳統(tǒng)的公鑰密碼系統(tǒng)來說,具有十分顯著的計(jì)算性能優(yōu)勢[13].例如,在GPU上分別執(zhí)行NTRU、RSA和ECC,效率上比較:NTRU比RSA快1000倍,比ECC快100倍[14].NTRU高效的原因可以由其底層操作的簡單性來解釋,NTRU算法中使用系數(shù)相對較小的多項(xiàng)式,運(yùn)算操作為加法和卷積乘法,即使在約束器件中也可以有效地執(zhí)行運(yùn)算操作[15].隨后一些基于格上的加密體制紛紛被提出,如Aono等人[16]設(shè)計(jì)一種新的基于LWE困難問題的代理重加密方案,該方案在標(biāo)準(zhǔn)模型下達(dá)到了CPA安全,且具有單向性和多跳性.

基于NTRU密碼體制的安全性可被規(guī)約為最壞情況下的格困難問題,即安全性是基于最壞情況假設(shè)的.這和傳統(tǒng)基于平均情況下困難問題的加密體制相比較,能夠在安全性上給予進(jìn)一步的保障,安全性可以規(guī)約到最短向量問題.Nnez[17]等人提出了第一個(gè)基于NTRU的代理重加密方案,但提出的方案是雙向重加密的,且不能抵抗被授權(quán)者與代理者或授權(quán)者與代理者之間的合謀攻擊.

本文貢獻(xiàn):本文在Nnez等人方案的基礎(chǔ)上提出一種新的基于NTRU的代理重加密方案.本文方案對比原方案有以下幾個(gè)方面的優(yōu)勢:一是能夠抗合謀攻擊.在原方案中代理者與被授權(quán)者可以合謀獲取授權(quán)者的私鑰或是代理者能與授權(quán)者合謀獲取被授權(quán)者的私鑰,而本方案中對該缺陷做了改進(jìn),使得代理者無法與被授權(quán)者合謀獲得授權(quán)者的私鑰,代理者也無法與授權(quán)者合謀獲得被授權(quán)者的私鑰.二是設(shè)計(jì)單向的重加密能力,原方案是雙向重加密的,而單向重加密方案比雙向重加密的隱私性和安全性更好,主要原因是雙向重加密可以由單向重加密構(gòu)成,反之則不能,我們提出的方案是支持單向重加密.三是本文方案支持多跳性,即代理者具有對密文執(zhí)行多次重加密運(yùn)算能力,以實(shí)現(xiàn)多次密文代理轉(zhuǎn)換的解密能力.

2 預(yù)備知識

2.1 符號定義

本節(jié)主要介紹文中所使用的一些符號的具體含義,如下所示.

b列向量n多項(xiàng)式環(huán)的維度

q正整數(shù),在加解密過程中減小多項(xiàng)式的系數(shù)fp私鑰f在模p運(yùn)算中的乘法逆元

Z 整數(shù)域 Z[x]環(huán)

? 整數(shù)系數(shù)多項(xiàng)式集合p素?cái)?shù),在加解密過程中減小多項(xiàng)式的系數(shù)

Rnn維歐氏空間fq私鑰f在模q運(yùn)算中的乘法逆元

2.2 代理重加密方案的定義

在本節(jié)中,首先給出基于Canetti和Hohenberger[4]的重加密方案的基本定義,一個(gè)代理重加密由6個(gè)多項(xiàng)式時(shí)間的算法構(gòu)成:

方案算法具體功能如下:

算法1代理重加密算法PRE=(Setup,KeyGen,Encrypt,ReKeyGen,ReEnc,Decrypt)? Setup(λ):輸入安全參數(shù)λ,輸出公共參數(shù)pp.? KeyGen(pp):密鑰生成算法給用戶i輸出公鑰pki和私鑰ski.? Encrypt(pkA,m):加密算法的輸入為授權(quán)者A的公鑰pkA和明文m輸出則為密文CA.? ReKeyGen(skA,pkB):重加密密鑰生成算法輸入A的私鑰skA和被授權(quán)者B的公鑰pkB,輸出重加密密鑰rkA?→B.? ReEnc(CA,rkA?→B):重加密算法的輸入為密文CA和重加密密鑰rkA?→B,輸出則為代理者加密后的密文CB.? Decrypt(CB,skB):解密算法的輸入為密文CB和被授權(quán)者B的私鑰skB,該算法的輸出為明文m.

代理重加密方案PRE的正確性滿足下面兩個(gè)條件:

(1)授權(quán)者A使用私鑰skA解密:

(2)被授權(quán)者B使用私鑰skB解密:

如果以上兩種解密算法均能得到正確明文,則可以證明該方案滿足正確性要求.

2.3 多跳性

重加密方案滿足多跳性:半可信代理者可以多次使用不同的重加密密鑰,對密文執(zhí)行多次重加密運(yùn)算.下面給出多跳性的具體定義:

算法2代理重加密方案多跳性定義? 第一次加密:用戶A由密鑰生成算法得到公鑰pkA和私鑰skA,由明文空間中選擇明文m,再由加密運(yùn)算Encrypt(pkA,m)得到密文C1.? N?1次重加密過程:由密鑰生成算法得到一系列公私鑰對(pki,ski),其中2≤i≤N,隨后由重加密密鑰生成算法得到一系列的重加密密鑰rkj?→j+1,其中1≤j≤N?1,隨后執(zhí)行N?1次重加密過程:第一次重加密:C2=ReEnc(C1,rk1?→2)第二次重加密:C3=ReEnc(ReEnc(C1,rk2?→3))...第 N ?1次重加密:CN=ReEnc(CN?1,rkN?1?→N)第N位接收者執(zhí)行解密運(yùn)算Decrypt(CN,skN)→m.

如果第N位接收者執(zhí)行解密運(yùn)算后得到結(jié)果為m,則證明該方案滿足多跳正確性.

2.4 最短向量問題和最近向量問題

設(shè)b1,b2,···,bm∈Rn,是一組線性無關(guān)的向量,則集合L={x1?b1+x2?b2+···+xm?bm|xi∈Z}為向量b1,b2,···,bm在 Rn中的格,向量b1,b2,···,bm為格L的一組格基.

最短向量問題(SVP):在格L中尋找一個(gè)最短的非零向量,即在格L尋找一個(gè)非零向量v∈L,使它的歐幾里得范數(shù)||v||最小.而SVP已經(jīng)被證明是NP困難問題[18,19].

最近向量問題(CVP):給定一個(gè)不在格L中的向量w∈Rn,尋找一個(gè)向量v∈L,使它最接近w,即尋找一個(gè)向量v∈L,使得歐幾里得范數(shù)||v?w||最小.

3 本文方案

在本節(jié)中,我們首先介紹傳統(tǒng)NTRU加密方案,隨后給出改進(jìn)NTRU加密方案的代理重加密方案.

3.1 NTRU 加密方案

NTRU加密體制是由Ho ff stein等提出,算法是基于卷積多項(xiàng)式環(huán)?=Z[x]/(xn?1)的加密體制,?表示最高次數(shù)不超過n?1的所有整系數(shù)多項(xiàng)式集合,n一般為素?cái)?shù).NTRU體制中別的公共參數(shù)還有p和q,p一般選擇為3,q一般為2的冪次方,q越大,則方案的安全性越高.一般來說,NTRU體制中的所有運(yùn)算都是在模q和模p中進(jìn)行的.NTRU中多項(xiàng)式的運(yùn)算有加法和乘法,設(shè)其中一個(gè)元素為:

加法運(yùn)算為:f+g=(f0+g0)+(f1+g1)?x+···+(fn?1+gn?1)?xn?1

乘法運(yùn)算為:f?g=h,其中,在NTRU算法中定義乘法運(yùn)算為卷積運(yùn)算.

在NTRU體制中,私鑰sk是由多項(xiàng)式環(huán)中隨機(jī)選取一個(gè)多項(xiàng)式(f∈?)得到的,私鑰的系數(shù)一般為0、?1和1,此外,該多項(xiàng)式還需滿足以下條件,需要在?(modq)和?(modp)中分別具有逆元,即存在fq和fp使得私鑰滿足f?fq≡1(modq)和f?fp≡1(modp),則fq和fp就是私鑰的逆元.下面給出NTRU的詳細(xì)算法.

3.2 基于NTRU的代理重加密方案

? 密鑰產(chǎn)生 (KeyGen):密鑰生成算法的輸出是為授權(quán)者A,被授權(quán)者B分別生成一對公私鑰(pki,ski).對于授權(quán)者A,首先從?中隨機(jī)選取小多項(xiàng)式fA(即系數(shù)一般為0、?1和1),此外,多項(xiàng)式fA要同時(shí)滿足

隨后再由?中隨機(jī)選取小多項(xiàng)式gA,計(jì)算公鑰pkA=p?gA?(modq),授權(quán)者A的私鑰就是fA.同理可知被授權(quán)者B的公私鑰分別為(pkB=p?gB?(modq),skB=fB).

?重加密密鑰生成算法(ReKeyGen):該算法是基于Nnez等人設(shè)計(jì)的重加密密鑰算法.在原方案中,該算法的輸入是授權(quán)者A的私鑰fA和被授權(quán)者B的私鑰fB,依據(jù)重加密密鑰的生成協(xié)議,首先由授權(quán)者A從?中隨機(jī)選取多項(xiàng)式r′隨后發(fā)送r′?fA(modq)給被授權(quán)者B,r′發(fā)送給代理者C.被授權(quán)者B發(fā)送r′?fA?(modq)給代理者C,代理者C就可以得到重加密密鑰 rkA?→B=fA?(modq),但是原方案設(shè)計(jì)的重加密密鑰無法抵抗合謀攻擊,該缺陷在 4.2節(jié)會(huì)詳細(xì)介紹.

本方案改進(jìn)了重加密密鑰生成算法.首先,本算法的輸入也是授權(quán)者A和被授權(quán)者B的私鑰,分別為fA和fB.首先授權(quán)者A從 ?中隨機(jī)選取r1和e1,隨后授權(quán)者A計(jì)算a=r1?(fA+p?e1)(modq)并將其發(fā)送給被授權(quán)者B,將r1發(fā)送給云服務(wù)器C.被授權(quán)者B收到a后,計(jì)算b=a?(modq),隨后被授權(quán)者B將b發(fā)送給云服務(wù)器C.

在云服務(wù)器C收到b和r1之后,計(jì)算重加密密鑰

? 加密(Encrypt):該算法的輸入是授權(quán)者A的公鑰pkA和需要加密的明文m.該算法的過程是首先由?中隨機(jī)選取多項(xiàng)式r2,計(jì)算密文CA=pkA?r2+m(modq),最終輸出密文CA.

? 重加密(ReEnc):該算法的輸入是密文CA和重加密密鑰rkA?→B.該算法的加密過程是CB=rkA?→B2?CA(modq)由于 pkA=p?gA?(modq),故得到最終密文

? 解密(Decrypt):該算法的輸入是密文CB和被授權(quán)者的私鑰skB.該算法的解密過程是

4 方案分析

在本節(jié)中,我們分析所提出方案的正確性、安全性、多跳性和單向性.

4.1 正確性分析

方案的正確性驗(yàn)證從兩個(gè)方面證明:

(1)授權(quán)者A從密文CA成功恢復(fù)出明文,即計(jì)算:

隨后對上式的最終結(jié)果進(jìn)行模p運(yùn)算:

由于fA(modp)≡1(modp),所以最終可以恢復(fù)出原明文m.

(2)被授權(quán)者B收到云代理服務(wù)器的重加密后密文CB后,計(jì)算:

隨后對上式的最終結(jié)果進(jìn)行模p運(yùn)算,得到:

在談及新能源混合動(dòng)力汽車之前，先了解一下傳統(tǒng)意義技術(shù)層面上對混合動(dòng)力汽車的定義—混合動(dòng)力汽車也被稱為復(fù)合動(dòng)力汽車，其動(dòng)力輸出部分或全部依靠車載的內(nèi)燃機(jī)提供，并根據(jù)對其他動(dòng)力源(如電動(dòng)源)的依賴程度分為弱混、輕混、中混和重混(全混)，根據(jù)其動(dòng)力輸出的分配方式分為并聯(lián)、串聯(lián)和混聯(lián)。

因?yàn)閒A≡1(modp),所以最終可以得出原明文m.提出的方案滿足正確性要求.

4.2 安全性

本文方案是建立在NTRU方案的基礎(chǔ)上,其安全性也等同于NTRU的安全性,由于NTRU密碼體制缺乏形式化的安全性證明,因此本文通過幾種攻擊方式來驗(yàn)證方案的安全性.

針對私鑰的攻擊:通過此攻擊方式,攻擊者試圖找到秘鑰或可用于解密的密鑰的替代密鑰.假設(shè)在多項(xiàng)式時(shí)間內(nèi),攻擊者可以很容易得到這樣一對多項(xiàng)式 (f′,g′),使其滿足g′=f′?fq?g(modq),那么該攻擊者可以破解私鑰.而該問題等價(jià)于最短向量問題(SVP),而SVP問題是一個(gè)多項(xiàng)式時(shí)間的NP困難問題,顯然在多項(xiàng)式時(shí)間內(nèi),攻擊者不可能破解求出私鑰.

抵抗合謀攻擊:在原方案重加密密鑰格式為 rkA?→B=fA?(modq),不能抵抗合謀攻擊.在本方案中,我們改進(jìn)了重加密密鑰的生成算法,即 rkA?→B2=fA?+p?e1?(modq),如果代理者C要與授權(quán)者A或被授權(quán)者B合謀獲得被授權(quán)者B或授權(quán)者A的私鑰,可由下列引理證明實(shí)現(xiàn)該種攻擊不存在.

引理1對比原方案,本方案代理者C與授權(quán)者A不能合謀獲得被授權(quán)者B的私鑰.

證明:在原方案中,代理者C用自己的重加密密鑰rkA?→B與授權(quán)者A的私鑰fA作計(jì)算:

可以得到被授權(quán)者的私鑰fB,即原方案不能抵抗代理者C和授權(quán)者A的合謀攻擊.

本方案中,代理者C擁有重加密密鑰 rkA?→B,首先是求重加密密鑰rkA?→B的乘法逆元,由其結(jié)構(gòu)可以看出,顯然不能得到一個(gè)有效的逆元,或者是使用重加密密鑰rkA?→B與授權(quán)者A的私鑰fA的逆作計(jì)算:

引理2本方案代理者C與被授權(quán)者B不能合謀獲得授權(quán)者A的私鑰.

證明:在原方案中,代理者C用自己的重加密密鑰rkA?→B與被授權(quán)者B的私鑰fB作計(jì)算:

可以獲得授權(quán)者A的私鑰fA,即原方案不能抵抗代理者C和被授權(quán)者B的合謀攻擊.

本方案中,由引理1知重加密密鑰rkA?→B沒有一個(gè)有效的逆元,因此與被授權(quán)者B的私鑰fB作計(jì)算:

顯然,由于隨機(jī)多項(xiàng)式p?e1的存在,兩者合謀不能得到授權(quán)者A的私鑰.

在原方案中,代理者C既能與授權(quán)者A合謀獲取被授權(quán)者B的私鑰,又能與被授權(quán)者B合謀獲取授權(quán)者A的私鑰.而本方案通過改進(jìn)重加密密鑰生成算法,使得該方案中的代理者C不能與授權(quán)者A或被授權(quán)者B合謀獲得被授權(quán)者B或授權(quán)者A的私鑰信息.

4.3 方案多跳性

代理者執(zhí)行第一次重加密:

代理者執(zhí)行第二次重加密:

代理者執(zhí)行第N?1次重加密:

第N位接收者收到經(jīng)過N?1次重加密后的密文CN后,先對密文執(zhí)行解密運(yùn)算,得到:

經(jīng)上述驗(yàn)證,本方案在經(jīng)過N?1次重加密后,最終仍能恢復(fù)出明文消息,本方案滿足多跳性.

4.4 單向性

在原方案中云服務(wù)器C與授權(quán)者A、被授權(quán)者B通過重加密密鑰生成協(xié)議生成重加密密鑰rkA?→B=fA?(modq),此時(shí) rkA?→B可以將授權(quán)者A的公鑰加密的密文轉(zhuǎn)換成由被授權(quán)者B的私鑰解密的重加密密文.但該方案的重加密密鑰是可以由云服務(wù)器C通過對重加密密鑰進(jìn)行逆變換,生成一個(gè)新的重加密密鑰可將被授權(quán)者B的公鑰加密的數(shù)據(jù)轉(zhuǎn)換成由授權(quán)者A的私鑰解密的重加密密文,因此原方案是雙向重加密方案.

5 總結(jié)

本文提出了一種新的重加密方案,它基于NTRU實(shí)現(xiàn)高效重加密,達(dá)到單向性、多跳性和抗合謀攻擊的特點(diǎn).由于其抗量子攻擊、抗合謀攻擊和高效運(yùn)算的能力,對于在安全系統(tǒng)中特別是在受限的計(jì)算設(shè)備環(huán)境中,該方案具有較大優(yōu)勢.