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

王 眾,韓益亮

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

0 概述

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

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

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

1 相關知識

1.1 SDP問題

1.2 基于改進Niederreiter的雙公鑰加密方案

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

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

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

(1)

(2)

(3)

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

(4)

1.3 Xinmei簽名方案修正

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

設用戶在有限域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函數,發送方進行如下簽名:

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

(5)

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

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

(1)右乘公鑰矩陣V:

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

zT-1HT

(6)

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

(3)右乘公鑰矩陣J:

(7)

(4)根據上述結果再進行如下運算:

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

(8)

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

1.4 安全模型

根據文獻[19-20],本文提出基于編碼密碼的簽密方案的安全模型。

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

設多項式時間內的攻擊者為α,α贏得下述游戲的優勢為Advα,該機密性攻擊游戲包括以下步驟:

1)挑戰者選擇合適參數并運行系統,產生發送者以及接收者的公私鑰對(pkS,skS)、(pkR,skR),然后將發送方與接收方的公鑰(pkS,pkR)以及發送方的私鑰skS發送給攻擊者α。

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

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

(9)

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

設多項式時間內的攻擊者為η,η贏得下述游戲的優勢為Advη,該不可偽造性游戲包括以下步驟:

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

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

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

攻擊者η的優勢可以表示如下:

pkR,m),skR,pkS)]

(10)

2 基于改進Niederreiter雙公鑰加密的簽密方案

2.1 簽密方案構造

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

(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 正確性分析

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

3 安全性分析

3.1 不可偽造性

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

(11)

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

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

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

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

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

1)運行簽密系統,生成必要參數。

2)攻擊者進行預言機H詢問和預言機f詢問。

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

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

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

(12)

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

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

(13)

(14)

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

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

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

3.2 機密性

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

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

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

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

(15)

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

3.3 相關攻擊分析

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

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

4 效率分析

4.1 加密方案優勢

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

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

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

4.2 密鑰與密文量分析

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

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

Table 2 Key and ciphertext analysis of four schemes bit

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

5 結束語

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