新的基于Niederreiter密碼體制的簽名方案

王 眾，韓益亮，劉文超，陳 林

(武警工程大學(xué)密碼工程學(xué)院，西安710016)

E-mail:104832006@qq.com

1 引言

1994年，Peter Shor提出了一種在量子計(jì)算機(jī)上運(yùn)行的算法——Shor算法［1］，使得分解大整數(shù)和求解 Abel群上的離散對(duì)數(shù)問題在多項(xiàng)式時(shí)間內(nèi)不再困難，那么傳統(tǒng)的公鑰密碼如RSA、橢圓曲線密碼ECC，以及DSA，屬性基的公鑰密碼等等將不再像以前那么可靠［2］，而且隨著量子計(jì)算機(jī)的發(fā)展，傳統(tǒng)的公鑰密碼將被輕易攻破，這也意味著密碼學(xué)界的半壁江山將受到巨大的沖擊.現(xiàn)在已知的可以抵抗量子計(jì)算機(jī)攻擊的密碼體制有基于編碼的密碼體制，基于格的密碼體制LWE(Learning With Errors)，基于Hash函數(shù)的密碼體制以及基于多變量的密碼體制.

基于編碼的公鑰密碼體制是在有限域上多元多項(xiàng)式環(huán)上定義和運(yùn)算的，此類密碼體制的算法核心是對(duì)一種糾錯(cuò)碼C的應(yīng)用，主要的特征即為添加一個(gè)錯(cuò)誤到碼字中或根據(jù)碼C的校驗(yàn)矩陣計(jì)算伴隨式.基于編碼的密碼體制主要用到的是糾錯(cuò)碼的性質(zhì)因此具有抗量子的特性和簡(jiǎn)單的加解密過程［3］，是當(dāng)今抗量子密碼方案的優(yōu)良候選者之一.1978年，McEliece第一個(gè)運(yùn)用這種方法創(chuàng)造公鑰密碼體制，提出首個(gè)基于編碼理論設(shè)計(jì)的公鑰加密方案，其中私鑰為一個(gè)二元不可約Goppa碼，公鑰為該碼的生成矩陣被隨機(jī)化處理之后的結(jié)果［4］.Niederreiter在1986年又提出了著名的基于Goppa碼的Niederreiter密碼體制［5］.該方案從另一個(gè)角度利用了隨機(jī)線性碼的譯碼困難問題，McEliece公鑰密碼方案隱藏的是Goppa碼的生成矩陣，而該方案隱藏的是Goppa碼的校驗(yàn)矩陣，此時(shí)公鑰尺寸有所變小，并且兩者的安全性是相同的.受到McEliece體制和Niederreiter體制的啟發(fā)，許多新方案也陸陸續(xù)續(xù)產(chǎn)生.到目前的研究階段，基于編碼理論的公鑰密碼學(xué)研究的重點(diǎn)主要放在了對(duì)碼的選擇上，以保證安全性的同時(shí)，提高實(shí)用性，降低方案的密鑰尺寸，由最開始的Goppa碼、Reed-Solomon 碼［6］，到現(xiàn)在的 QC-MDPC 碼［7］，LDPC(Low Density Parity Check codes)碼［8］以及 QC-LDPC 碼等等［9］.

1990年，王新梅設(shè)計(jì)了第一個(gè)基于編碼密碼的簽名方案，即Xinmei方案［10］.這個(gè)簽名方案是基于Rao-Nam密碼系統(tǒng)設(shè)計(jì)的，但是Rao-Nam［11］密碼系統(tǒng)不能抵抗明文攻擊的選擇，導(dǎo)致該方案很快受到損害.目前，主要有三類基于編碼密碼的簽名方案:CFS 方案［12］，Stern 方案［13］，KKS 方案［14］，以及其改進(jìn)方案和具有特殊功能的方案，如盲簽名方案，環(huán)簽名方案和群簽名方案.2013年，F(xiàn)augere等人指出，可以將高幾率的Goppa碼與隨機(jī)線性碼區(qū)分開來，這引發(fā)了對(duì)現(xiàn)有基于編碼密碼簽名方案的安全性的質(zhì)疑［15］.2016年，Phesso和Tillich利用簽名位的一些相關(guān)性來有效地攻擊基于Niederreiter公鑰密碼系統(tǒng)的現(xiàn)有簽名方案，原因在于Niederreiter公鑰密碼系統(tǒng)固有的一些缺陷［16］.因此，學(xué)者們?cè)噲D設(shè)計(jì)一些新的安全有效的基于編碼密碼的簽名方案.大多數(shù)方案的安全性和有效性通過一些特殊的方式得到改善，如擾亂校驗(yàn)子，優(yōu)化哈希函數(shù)，加快嵌入式硬件的簽名速度，這些方式提供了一定的參考價(jià)值［17-20］.然而，這些方法實(shí)際上是針對(duì)現(xiàn)有方案進(jìn)行了優(yōu)化，并且沒有糾正方案所基于的Niederreiter公鑰密碼系統(tǒng)中固有的一些缺陷，使得簽名方案仍然易受到區(qū)分攻擊以及ISD攻擊.劉相信等提出了一種新的Niederreiter公鑰密碼方案，可以隱藏明文的漢明重量來有效抵抗ISD攻擊以及區(qū)分攻擊［21］，也為本文的新簽名方案提供了思路.

本文參考CFS簽名方案提出了一種新的基于Niederreiter公鑰密碼體制的簽名方案.新方案可以真正隱藏用戶密鑰，并非像之前的方案那樣單純地用置換矩陣去隱藏密鑰，這種方式?jīng)]有真正地隱藏密鑰信息，又由于對(duì)明文重量t有所隱藏，保證了方案的效率.經(jīng)過分析新方案能夠有效抵抗區(qū)分攻擊相對(duì)CFS簽名方案有較高安全性.本文第二節(jié)介紹了編碼密碼所基于的困難問題以及Niederreiter公鑰密碼方案和CFS簽名方案;第三節(jié)提出新的簽名方案，并闡明具體的簽名與驗(yàn)證過程;第四節(jié)進(jìn)行安全性分析;第五節(jié)對(duì)方案效率進(jìn)行分析;最后一節(jié)總結(jié)全文.

2 相關(guān)知識(shí)

2.1 SDP問題

校驗(yàn)子譯碼問題(The Syndrome Decoding Problem)給定一個(gè)(n，k)維的線性碼，它的最小漢明距離為d，該碼的校驗(yàn)矩陣為，它的糾錯(cuò)能力為t，且t滿足方程d=2t+1.當(dāng)給定一個(gè)向量時(shí)，尋找一個(gè)錯(cuò)誤向量e∈，它的漢明重量要小于等于t，且與向量v以及矩陣H滿足方程v=eHT，尋找錯(cuò)誤向量e這個(gè)問題已被證明為NP困難問題.

2.2 Niederreiter公鑰密碼系統(tǒng)

設(shè)(n－k)×n階矩陣H為二元(n，k，d)Goppa碼的校驗(yàn)矩陣，其中 n=2a，d=2t+1，k=n － at，且該 Goppa 碼的譯碼算法為αH(t).

密鑰生成:隨機(jī)選取 GF(2)上的可逆矩陣 S，其階為(n－k)×(n－k)，再選取置換矩陣T，其階為n×n.計(jì)算公鑰珚H=SHT，即為三個(gè)矩陣作運(yùn)算，而S，H，T三個(gè)矩陣則作為私鑰保存.

加密過程:設(shè)加密信息為m，m∈GF(2n)，且其漢明重量為t.計(jì)算密文 c，直接將明文 m與公鑰作運(yùn)算即得:c=m珚HT.

解密過程:當(dāng)接受者接受到密文c后，首先利用可逆矩陣S進(jìn)行運(yùn)算，即mTTHT，進(jìn)而利用Goppa碼的譯碼算法αH(t)進(jìn)行譯碼得到珚m=mTT，所以明文通過m=珚m(TT)－1得到.

從傳統(tǒng)的Niederreiter公鑰密碼系統(tǒng)可以看出，該系統(tǒng)的公鑰珚H是通過矩陣間的運(yùn)算得到的，通過左乘一個(gè)可逆矩陣，右乘一個(gè)置換矩陣來對(duì)矩陣H進(jìn)行隱藏，但是根據(jù)矩陣間運(yùn)算的性質(zhì)“左行右列”可以知道，矩陣左邊乘一個(gè)矩陣相當(dāng)于對(duì)該矩陣進(jìn)行了行變換，并不能改變Goppa碼的性質(zhì)，右邊再乘以一個(gè)矩陣也只是進(jìn)行了列變換，因此并不能真正起到隱藏矩陣H的作用，使得Niederreiter公鑰密碼系統(tǒng)易受到區(qū)分攻擊.

2.3 CFS 簽名方案

Courtois，F(xiàn)iniasz和Sendrier提出的基于Niederreiter密碼體制的CFS簽名方案是為數(shù)不多的安全編碼基簽名方案.具體的初始化與簽名驗(yàn)證過程如下:

初始化過程:取C是有限域GFq上線性(n，k，d)Goppa碼，n=2a，d=2t+1，k=n－at.(n－k) ×n階矩陣 H 為二元(n，k，d)Goppa碼的校驗(yàn)矩陣，隨機(jī)選取GF(2)上的可逆矩陣S，其階為(n－k)×(n－k)，再選取置換矩陣T，其階為n×n.設(shè)一個(gè)哈希函數(shù)h:{0，1}*→F(n－k)2，即將任意長(zhǎng)度的0，1串映射到長(zhǎng)度為n的0，1串上.Goppa的快速譯碼算法為βHt()，ε為待簽名消息.將(h，t，珚H=SHT)公開，將(S，T，H，βHt())保密.

3 新Niederreiter簽名方案

新Niederreiter簽名方案相對(duì)于直接基于Niederreiter創(chuàng)建的簽名方案主要有兩點(diǎn)大的不同.其一是對(duì)置換矩陣T進(jìn)行了改動(dòng)，使其為隨機(jī)矩陣，存在的要求便是它的列重最大值固定;其二，簽名消息數(shù)量增加，且錯(cuò)誤向量的合理漢明重量值t不公開，最后需要通過三個(gè)等式對(duì)簽名進(jìn)行驗(yàn)證.

3.1 初始化過程

3.2 簽名及驗(yàn)證過程

對(duì)消息x進(jìn)行簽名:

1)計(jì)算x的哈希值c:c=h1(x).

4 安全性分析

4.1 區(qū)分攻擊

現(xiàn)有的編碼密碼方案以及簽名方案并沒有真正地將私鑰信息隱藏，這就會(huì)導(dǎo)致攻擊者趁虛而入，區(qū)分攻擊便是利用這一點(diǎn)來對(duì)編碼密碼體制進(jìn)行攻擊的有效手段.區(qū)分攻擊的思想是將一個(gè)隨機(jī)矩陣與公開碼字的生成矩陣或者校驗(yàn)矩陣也即公鑰區(qū)分開來.根據(jù)密碼方案或者簽名方案的略微不同，可加以實(shí)施具體的區(qū)分操作，進(jìn)而恢復(fù)密鑰，且其花費(fèi)的代價(jià)較小，較為有效.

新Niederreiter簽名方案在簽名驗(yàn)證時(shí)，不同于傳統(tǒng)的Niederreiter密碼體制運(yùn)用一個(gè)可逆矩陣一個(gè)置換矩陣來對(duì)矩陣H進(jìn)行隱藏，而是運(yùn)用了兩個(gè)可逆矩陣，將置換矩陣替換成為了一個(gè)隨機(jī)的可逆矩陣Q.置換矩陣的運(yùn)用只是對(duì)矩陣進(jìn)行了簡(jiǎn)單的列變換，而隨機(jī)可逆矩陣的運(yùn)用使得矩陣HQ不再是某個(gè)線性碼的校驗(yàn)矩陣，而具有一定的隨機(jī)性.新簽名方案的主要簽名信息有兩個(gè)，且在驗(yàn)證時(shí)需要三個(gè)等式進(jìn)行，攻擊者無法將公鑰與隨機(jī)矩陣區(qū)分開來，進(jìn)而無法恢復(fù)密鑰.

4.2 正確性

對(duì)本文方案的正確性進(jìn)行驗(yàn)證，即當(dāng)接收者接收到經(jīng)過發(fā)送者私鑰處理的信息后，能夠通過發(fā)送者的公鑰對(duì)簽名信息進(jìn)行驗(yàn)證.

當(dāng)接收者收到消息 x 的簽名 Sig=(e1，e2，i0，i1，i2)后，根據(jù)已知的步驟進(jìn)行驗(yàn)證，如下所示:

4.3 不可偽造性

當(dāng)簽名者想要偽造一個(gè)合法簽名 Sig=(e1，e2，i0，i1，i2)時(shí)，相當(dāng)于對(duì)該簽名方案所基于的密碼體制進(jìn)行解密.想要對(duì)該方案進(jìn)行解密，運(yùn)用已知的攻擊編碼密碼體制的方法像區(qū)分攻擊，根據(jù)4.1節(jié)的分析可知該方法是難以針對(duì)新方案的.且新方案相對(duì)傳統(tǒng)的方案將校驗(yàn)矩陣進(jìn)行了拆分，進(jìn)一步提升了破譯的難度.在偽造 Sig=(e1，e2，i0，i1，i2)時(shí)，要挑選出符合漢明重量要求的兩個(gè)錯(cuò)誤向量，而合理e1，e2的重量是不公開的，因此攻擊者想要偽造合理的簽名向量的概率極低，嘗試的次數(shù)大概為 C0n+C1n+C2n+ … +Cn－1n+Cnn=2n［21］.困難性相比CFS簽名方案有所增加，并且需要在集合{0，1，2，…}中挑選合適的i0，i1，i2，才能滿足驗(yàn)證的要求，選中的概率是極低的.由上述分析可知，新簽名方案相比CFS簽名方案安全性有較大提高且具有簽名的不可偽造性.

5 效率分析

新方案的構(gòu)造相比于CFS簽名方案，在提升安全性的前提下，能夠保證相對(duì)較高的效率，相比于CFS簽名方案，增加的工作量在于兩個(gè)哈希函數(shù)運(yùn)算與一個(gè)譯碼過程，這些工作量會(huì)對(duì)運(yùn)行效率造成些許影響但在合理的范圍內(nèi).新簽名方案由于對(duì)重量t具有一定的隱藏功能因此在對(duì)t的選擇上沒有像CFS簽名方案那樣必須保證重量t足夠大，才具有一定的安全性.文獻(xiàn)［16］中指出，當(dāng)t大于等于10時(shí)，CFS方案才具有一定的計(jì)算復(fù)雜性，也就是說，必須要嘗試10!=362880次才可以成功簽名.新Niederreiter簽名方案簽名成功的概率為(1/t!)2，由于使用到兩次譯碼算法，因此是CFS簽名方案的平方，但由于t在選擇上的靈活性，可以選擇較小一些的漢明重量t使得新簽名方案有較高效率而不會(huì)降低方案的安全性.具體比較見表1.

表1 效率對(duì)比表Table 1 Efficiency comparison table

6 結(jié)論

本文從傳統(tǒng)的Niederreiter公鑰密碼體制入手，結(jié)合CFS簽名方案，提出了新Niederreiter簽名方案，該方案不同于以往的簽名方案，運(yùn)用隨機(jī)的可逆矩陣代替原來Niederreiter密碼體制中的置換矩陣，這一改變使得新方案對(duì)于區(qū)分攻擊起到了良好的防御作用，又由于將私鑰校驗(yàn)矩陣進(jìn)行了拆分處理，并對(duì)簽名錯(cuò)誤向量的重量進(jìn)行了隱藏，使得攻擊者在偽造簽名時(shí)成功的概率相對(duì)CFS簽名方案有了極大的下降.新Niederreiter簽名方案在效率方面可以通過對(duì)重量t的合理選擇來增強(qiáng)效率.