基于Niederreiter密碼體制的抗量子簽密方案

王 眾,韓益亮

(武警工程大學(xué) 密碼工程學(xué)院,西安 710086)

0 概述

目前,人們的日常生活已經(jīng)離不開復(fù)雜網(wǎng)絡(luò)與頻繁通信,在享受網(wǎng)絡(luò)通信帶來便利的同時,網(wǎng)絡(luò)安全問題日益突出,如何保障用戶的隱私、所發(fā)送信息的不可否認(rèn)性以及通信過程的安全性成為網(wǎng)絡(luò)通信領(lǐng)域的研究重點。密碼學(xué)中的簽密技術(shù)[1]可以提供簽名以及加密的功能,其原理是在簽密時用發(fā)送方的私鑰進(jìn)行簽名,用接收方的公鑰進(jìn)行加密,解簽密時用發(fā)送方的公鑰進(jìn)行簽名驗證以保證信息的不可否認(rèn)性,用接收方的私鑰進(jìn)行解密以保證信息的機密性。雖然簽密技術(shù)能夠在一個邏輯步驟內(nèi)完成簽名與加密,為信息提供良好的安全保護(hù),但是,隨著量子技術(shù)的發(fā)展以及量子計算機研究的不斷推進(jìn),基于經(jīng)典數(shù)論問題的公鑰密碼方案,如RSA公鑰加密算法、橢圓曲線密碼(Elliptic Curves Cryptography,ECC)和屬性基密碼等,未來將無法再為復(fù)雜龐大的網(wǎng)絡(luò)通信提供可靠的安全保證。

近年來,量子技術(shù)在密鑰安全領(lǐng)域得到應(yīng)用[2]。現(xiàn)有能夠抵御量子計算攻擊的密碼體制有基于編碼的密碼體制[3]、基于格的密碼體制LWE(Learning With Errors)[4]、基于Hash函數(shù)的密碼體制[5]以及基于多變量的密碼體制[6]。上述密碼體制均是在困難問題的基礎(chǔ)上而建立,量子計算機與電子計算機在面對這些問題時都不能在有限的資源條件下將其攻破,因此,這類密碼體制可以有效抵抗量子計算攻擊。其中,基于編碼的密碼體制具有易于操作以及計算效率較高的特性,因此備受學(xué)者們的青睞,該密碼體制所依賴的困難問題是碼字的譯碼問題,較早的基于編碼的公鑰密碼算法由文獻(xiàn)[7]所編造,其私鑰主要為一個二元即約Goppa碼的生成矩陣,相對應(yīng)的公鑰為該矩陣被隨機處理之后的矩陣。另外一個經(jīng)典的編碼密碼算法Niederreiter由文獻(xiàn)[8]提出,該算法為文獻(xiàn)[7]算法的對偶體制,兩者的安全性完全相同,但Niederreiter算法在傳信率方面具有一定的優(yōu)勢。截止目前,仍沒有能夠有效攻擊這2種算法的方法。編碼密碼仍在不斷發(fā)展之中,為了保證編碼密碼的安全性、實用性并降低方案的密鑰尺寸,由較早的Goppa碼、Reed-Solomon碼[9],到現(xiàn)在的準(zhǔn)循環(huán)中密度奇偶校驗(QC-MDPC)碼[10]、低密度奇偶校驗(LDPC)碼[11]以及準(zhǔn)循環(huán)低密度奇偶校驗(QC-LDPC)碼[12]等,通過優(yōu)化碼字的選擇來不斷減少編碼密碼的公鑰量,但是,其安全性并未得到實質(zhì)上的提升。

雙公鑰加密技術(shù)是公鑰加密算法中有效提高算法安全性的手段之一,有較多學(xué)者將編碼密碼與雙公鑰加密思想相結(jié)合。文獻(xiàn)[13]利用雙公鑰對文獻(xiàn)[7]算法進(jìn)行改進(jìn),安全性有較好的提升,但是其通過雙公鑰的方式加密,增加了密鑰量,實用性不高。文獻(xiàn)[14]提出基于QC-LDPC碼的雙公鑰Niederreiter密碼方案,由于采用了QC-LDPC碼,使得雙公鑰方案的密鑰量有所下降,安全性有較高提升,但是,該方案的密鑰量和安全性仍有較大的提升空間。文獻(xiàn)[15]提出基于改進(jìn)Niederreiter密碼體制的雙公鑰加密方案,該方案可以有效抵抗ISD攻擊并采用雙公鑰加密的方式進(jìn)一步提升安全性,但采用系統(tǒng)碼避免雙公鑰加密的方式降低了運行效率。本文通過對Xinmei簽名方案[16]與基于改進(jìn)Niederreiter密碼的雙公鑰加密方案進(jìn)行研究,提出一種抗量子簽密方案,通過采用系統(tǒng)碼的方式在增加方案安全性的同時保證其有效性與實用性。

1 相關(guān)知識

1.1 SDP問題

1.2 基于改進(jìn)Niederreiter的雙公鑰加密方案

王眾等提出的基于改進(jìn)Niederreiter的雙公鑰加密方案[15],在第2步加密時對錯誤向量e的重量進(jìn)行了隱藏,使得該方案可以較好地抵抗ISD攻擊,且其采用雙公鑰的加密方式提高了安全性。該方案具體步驟如下:

3)解密過程。當(dāng)接收者收到密文(x1,x2,x3)后,進(jìn)行以下解密操作:

(1)運用私鑰A、B、C、Q以及譯碼算法β2Ht(),進(jìn)行第1步解密:

(1)

(2)

(3)

(2)完成第1步解密得到c1后,第2步解密就是普通的Niederreiter密碼體制的譯碼解密。運用私鑰S、T和碼G1的譯碼算法β1Ht()進(jìn)行解密,具體如下:

(4)

1.3 Xinmei簽名方案修正

王新梅教授于1990年在編碼密碼的基礎(chǔ)上提出Xinmei簽名方案[16],隨后又有許多學(xué)者提出了對該方案的攻擊以及改進(jìn)方法,王新梅根據(jù)這些攻擊方法在2000年提出了針對Xinmei簽名方案的修正版[18],以使其可以對選擇性明文攻擊(簡稱AW攻擊)等進(jìn)行有效的防御。

設(shè)用戶在有限域GFq上選擇一個(n,k,t)二元即約Goppa碼,該碼的校驗矩陣H的維度為(n-k)×n,生成矩陣G為k×n維,其中,t代表錯誤向量所允許的最大譯碼漢明重量。用戶再選擇2個可逆置換矩陣P與T,其中,P為k×k維,T為n×n維。Xinmei簽名方案修正版的具體過程如下:

2)簽名過程。待簽名信息為kbit的向量m,隨機生成一個nbit的向量z,z的漢明重量滿足wt(z)≤t,h為Hash函數(shù),發(fā)送方進(jìn)行如下簽名:

E(m)=(z+h(z,m)PG)T=c

(5)

簽名后產(chǎn)生簽密文c,并將(m,c)發(fā)送給接收方。

3)解簽名過程。當(dāng)接收方收到(m,c)后,進(jìn)行如下的簽名驗證過程:

(1)右乘公鑰矩陣V:

D1(c)=cV=[(z+h(z,m)PG)T]T-1HT=

zT-1HT

(6)

(2)運用譯碼算法Y對D1(c)進(jìn)行譯碼得到z。需要注意的是,若wt(z)>t,則說明傳輸過程有誤,無法正確譯碼,需要發(fā)送方重新發(fā)送。

(3)右乘公鑰矩陣J:

(7)

(4)根據(jù)上述結(jié)果再進(jìn)行如下運算:

D3(c)=D2(c)+zW=h(z,m)°

(8)

當(dāng)且僅當(dāng)h(z,m)°=h(z,m)時,簽名驗證過程成功。

1.4 安全模型

根據(jù)文獻(xiàn)[19-20],本文提出基于編碼密碼的簽密方案的安全模型。

定義2若在下述機密性游戲中,攻擊者在任何多項式時間中贏得游戲的優(yōu)勢是可以忽略的,則說明該簽密方案滿足選擇明文攻擊下的不可區(qū)分性,也即IND-CPA安全。

設(shè)多項式時間內(nèi)的攻擊者為α,α贏得下述游戲的優(yōu)勢為Advα,該機密性攻擊游戲包括以下步驟:

1)挑戰(zhàn)者選擇合適參數(shù)并運行系統(tǒng),產(chǎn)生發(fā)送者以及接收者的公私鑰對(pkS,skS)、(pkR,skR),然后將發(fā)送方與接收方的公鑰(pkS,pkR)以及發(fā)送方的私鑰skS發(fā)送給攻擊者α。

2)攻擊者產(chǎn)生2個明文(m0,m1),并將該明文對以及公鑰對(pkS,pkR)發(fā)送給挑戰(zhàn)者。挑戰(zhàn)者投擲一枚均勻的硬幣,選擇(m0,m1)中的一個mb,將公鑰對(pkS,pkR)與mb發(fā)送給簽密預(yù)言機,簽密預(yù)言機將產(chǎn)生的簽密文返回給挑戰(zhàn)者,由挑戰(zhàn)者返回至攻擊者α。

3)攻擊者收到返回的簽密文后,輸出1 bit 的b1。當(dāng)b=b1時,攻擊者α贏得游戲,該獲勝優(yōu)勢定義為:

(9)

定義3若在下述不可偽造性攻擊游戲中,攻擊者在任何多項式時間中贏得游戲的優(yōu)勢是可以忽略不計的,則說明本文簽密方案在適應(yīng)性選擇消息攻擊下滿足不可偽造性安全,也即EUF-CMA安全。

設(shè)多項式時間內(nèi)的攻擊者為η,η贏得下述游戲的優(yōu)勢為Advη,該不可偽造性游戲包括以下步驟:

1)挑戰(zhàn)者選擇參數(shù)并運行系統(tǒng),產(chǎn)生發(fā)送者S以及接收者R的公私鑰對(pkS,skS)、(pkR,skR),然后將接收方的(pkR,skR)與pkS發(fā)送給攻擊者η,并把發(fā)送者的公私鑰對(pkS,skS)發(fā)送給簽密預(yù)言機。

2)攻擊者可進(jìn)行簽密詢問,并驗證簽密文的合法性。

3)攻擊者提交挑戰(zhàn)信息m以及偽造的簽密文n,并把接收方與發(fā)送方的公鑰對(pkS,pkR)提交給挑戰(zhàn)者,攻擊者提交信息(m,n,pkS,pkR)給挑戰(zhàn)者。挑戰(zhàn)者知道發(fā)送方的私鑰skS,對簽密文n進(jìn)行解簽密運算,產(chǎn)生明文m。針對m,若攻擊者之前未對其進(jìn)行過簽密詢問,則說明攻擊者挑戰(zhàn)成功,對明文進(jìn)行了偽造。

攻擊者η的優(yōu)勢可以表示如下:

pkR,m),skR,pkS)]

(10)

2 基于改進(jìn)Niederreiter雙公鑰加密的簽密方案

2.1 簽密方案構(gòu)造

本文基于改進(jìn)Niederreiter雙公鑰加密方案與Xinmei簽名方案修正版進(jìn)行簽密方案構(gòu)造,具體的參數(shù)選擇、公私鑰生成以及簽密解簽密過程如下:

(2)c=(z+f(r||m)PAG1A)TA。

(3)FB·c→(x1,x2,x3)。

(4)Output (x1,x2,x3)。

3)解簽密過程,具體計算如下:

(3)Y(D1(c),t1)→z

Whilewt(z)≤t1continue

Else Receive error occurred,sender A resend

(5)D3(c)=D2(c)+zW=f(r||m)。

Outputm。

Else output⊥。

2.2 正確性分析

當(dāng)接收者收到簽密文(x1,x2,x3)后,首先需要使用自己的私鑰對其進(jìn)行解密,解密成功后得到向量c,由簽密步驟2可知,c的產(chǎn)生是由Xinmei簽名算法對函數(shù)f的結(jié)果f(r||m)進(jìn)行簽名所得,其中,隨機向量z是由隨機向量r和明文m通過安全Hash函數(shù)所產(chǎn)生。

3 安全性分析

3.1 不可偽造性

Pr[B]=Pr[X1∩X2∩X3]≤1/(qf+qSC+qH)·

(11)

其中,qSC、qDSC、qH、qf分別代表攻擊者η所能進(jìn)行的簽密詢問、解簽密詢問以及對預(yù)言機H和f詢問的最大次數(shù),分別設(shè)立4個詢問列表Hlist、flist、SClist、DSClist來對詢問進(jìn)行記錄。

1)預(yù)言機H詢問。攻擊者η進(jìn)行H詢問,向H預(yù)言機中輸入r||m,首先查詢表中是否有相應(yīng)記錄,存在記錄則返回給攻擊者;不存在則生成z,將其記錄在表Hlist中并返回給攻擊者。

2)預(yù)言機f詢問。攻擊者η進(jìn)行f詢問,向f預(yù)言機中輸入r||m,首先查詢表中是否有相應(yīng)記錄,存在記錄則返回給攻擊者;不存在則生成v,將其記錄在表flist中并返回給攻擊者。

4)解簽密詢問(DSC)。向解簽密預(yù)言機進(jìn)行詢問時,輸入簽密文n,首先查看表DSClist中是否有相應(yīng)記錄m,若存在則返回給詢問者,否則執(zhí)行解簽密算法得到r,通過r的值,在表Hlist、flist中進(jìn)行查詢得到明文m。

不可偽造性攻擊游戲的過程如下:

1)運行簽密系統(tǒng),生成必要參數(shù)。

2)攻擊者進(jìn)行預(yù)言機H詢問和預(yù)言機f詢問。

3)攻擊者提交明文m與偽造的簽密文n,并對n進(jìn)行解簽密詢問,若詢問返回結(jié)果為m,并且沒有對其進(jìn)行過簽密詢問,則說明攻擊者成功贏得游戲。

證明在簽密詢問時,首先查詢表SClist中是否有相應(yīng)記錄,若存在相應(yīng)記錄則返回給詢問者,否則需要產(chǎn)生對應(yīng)的結(jié)果。在沒有記錄的情況下,要調(diào)用預(yù)言機H與f來產(chǎn)生相應(yīng)的z與v的值,若H與f中已經(jīng)存在對應(yīng)于m的z或v的值,則說明模擬過程失敗,需要預(yù)言機SC、H與f對同一明文進(jìn)行成功的詢問,這樣才能完成簽密詢問,將此記為事件X1,其發(fā)生的概率為:

Pr[X1]=1/(qf+qSC+qH)

(12)

在解簽密時,輸入簽密文n,首先查看表DSClist中是否有相應(yīng)記錄m,若存在則返回給詢問者,不存在則執(zhí)行解簽密算法得到r,由r的值在表Hlist、flist中進(jìn)行查詢找到相應(yīng)的明文m,若沒有相應(yīng)的記錄,則說明模擬失敗。將通過r的值可在表Hlist、flist中進(jìn)行查詢找到明文m記為事件X2,其發(fā)生的概率為:

Pr[X2]=(qH/22n)·(qf/22n)=(qH·qf)/22n

(13)

(14)

由上述分析可知,攻擊算法B需要在以上3個相互獨立的事件都成立的前提下才可以成功,其優(yōu)勢表示如下:

Pr[B]=Pr[X1∩X2∩X3]≤1/(qf+qSC+qH)·

綜上,本文簽密方案滿足EUF-CMA安全。

3.2 機密性

證明將本文簽密方案所涉及的SDP問題實例交由攻擊算法K嘗試解決,攻擊算法K作為攻擊者α在游戲中的挑戰(zhàn)者,而α作為攻擊算法K的子程序。具體步驟如下:

1)攻擊算法B得到SDP問題實例中發(fā)送方以及接收方的公私鑰對(pkS,skS)、(pkR,skR),然后將發(fā)送方與接收方的公鑰(pkS,pkR)以及發(fā)送方的私鑰skS發(fā)送給攻擊者α。

2)攻擊者產(chǎn)生2個明文(m0,m1),并將該明文對以及公鑰對(pkS,pkR)發(fā)送給挑戰(zhàn)者。挑戰(zhàn)者投擲一枚均勻的硬幣,選擇(m0,m1)中的一個mb,將公鑰對(pkS,pkR)與mb發(fā)送給簽密預(yù)言機,簽密預(yù)言機將產(chǎn)生的簽密文返回給挑戰(zhàn)者,由挑戰(zhàn)者返回至攻擊者α。

3)攻擊者收到返回的簽密文后,輸出1 bit 的b1作為猜測。

(15)

因此,本文簽密方案滿足IND-CPA安全。

3.3 相關(guān)攻擊分析

針對編碼密碼體制,目前較為有效的攻擊手段包括直接譯碼攻擊和信息集譯碼攻擊(ISD)等。

本文簽密方案采用基于改進(jìn)Niederreiter的雙公鑰加密方案實現(xiàn)加密功能,在機密性上能夠為簽密方案提供較好的保障。

4 效率分析

4.1 加密方案優(yōu)勢

本文簽密方案通過基于改進(jìn)Niederreiter的雙公鑰加密方案實現(xiàn)加密功能,其采用系統(tǒng)碼進(jìn)行構(gòu)造,以雙公鑰加密方式進(jìn)行加密,密鑰量會有所增加但仍在可接受的范圍內(nèi),安全性得到較大提升。將文獻(xiàn)[14-15]中的2種方案進(jìn)行比較,結(jié)果如表1所示。基于改進(jìn)Niederreiter的雙公鑰加密方案在第2步加密時采用了改進(jìn)版Niederreiter方法,對重量t有隱藏功能,允許其選擇維度較小的碼字而達(dá)到與普通Niederreiter同樣的安全級別。

表1 文獻(xiàn)[14-15]方案中的第2步加密密鑰尺寸對比

從表1可以看出,在達(dá)到282bit安全級別時,文獻(xiàn)[14]方案的密鑰尺寸為20 904 bit,而文獻(xiàn)[15]方案為5 040 bit,密鑰尺寸有明顯下降,在2128bit安全級別下兩者具有同樣的效果,即隱藏重量t能夠顯著提升本文簽密方案的效率。

4.2 密鑰與密文量分析

在有限域GFq上選取二元系統(tǒng)碼G1、G2,維度分別為(120,40)、(80,40),進(jìn)行如表2所示的對比。由表2可以看出,本文簽密方案在私鑰量與密文量方面相比先簽名后加密的方法有較大的提升。私鑰量下降是因為在簽密方案構(gòu)造時,其中n×n維的矩陣T在簽名以及加密中共用,從而減少了一個n×n維的矩陣,也即14 400 bit的私鑰量。在密文量方面,先簽名后加密或者先加密后簽名的方法會產(chǎn)生簽名以及密文,而本文簽密方案是對簽名進(jìn)行加密,只有對簽名進(jìn)行正確驗證后才可以得到相應(yīng)的明文信息,簽密方案的簽密文即對簽名進(jìn)行加密后的密文(x1,x2,x3),由1.2節(jié)對加密方案的描述可知該簽密文的大小為120 bit,即本文方法的密文量相比先簽名后加密的方法減少了50%。

表2 4種方案的密鑰與密文分析

Table 2 Key and ciphertext analysis of four schemes bit

方案公鑰量私鑰量密文量文獻(xiàn)[15]方案1120032000120Xinmei簽名方案1600019200120先簽名后加密方案2720051200240本文簽密方案2720036800120

5 結(jié)束語

本文通過對Niederreiter密碼體制進(jìn)行研究,采用基于改進(jìn)Niederreiter的雙公鑰加密方案來構(gòu)造抗量子簽密方案。相比改進(jìn)Niederreiter方案以及基于QC-LDPC碼的雙公鑰Niederreiter密碼方案,該加密方案在安全性方面得到較大的提升,且其采用系統(tǒng)碼來保證雙公鑰的加密方式不會帶來過大的密鑰量。在此基礎(chǔ)上,本文將基于改進(jìn)Niederreiter的雙公鑰加密方案與Xinmei簽名方案相結(jié)合,提出一種基于編碼密碼的簽密方案。分析結(jié)果表明,該方案能夠滿足EUF-CMA與IND-CPA安全,相比先簽名后加密或者先加密后簽名的方案,其私鑰量和密文量均較低,在后量子時代具有良好的使用前景。下一步嘗試在該簽密方案中增加如混合簽密、代碼簽密等功能,以適應(yīng)更加復(fù)雜的網(wǎng)絡(luò)環(huán)境。