基于改進版Niederreiter的雙公鑰密碼方案

王眾 韓益亮

摘 要：基于編碼的密碼體制可以有效地抵抗量子計算攻擊，具有較好的可操作性以及數據壓縮能力，是后量子時代密碼方案的可靠候選者之一。針對量子時代中計算機數據的安全保密問題，對編碼密碼中的Niederreiter密碼方案改進版進行深入研究，提出了一種與雙公鑰加密方式相結合的密碼方案。所提方案的安全性相比Niederreiter方案改進版以及基于準循環低密度奇偶校驗碼（QC-LDPC）的Niederreiter雙公鑰加密方案得到提升，在密鑰量方面相比傳統Niederreiter密碼方案的公鑰量至少下降了32%，相比基于QC-LDPC碼的Niederreiter雙公鑰加密方案也有效下降，在量子時代保證計算機數據安全表現出較強的可靠性。

關鍵詞：編碼密碼;Niederreiter密碼體制;系統碼;安全性分析;效率分析

Abstract： The code-based cryptosystem can effectively resist quantum computing attacks with good operability and data compression capability， and is one of the reliable candidates for the post-quantum era cryptographic scheme. Aiming at the security and confidentiality of computer data in the quantum era， the in-depth study of an improved Niederreiter cryptographic scheme in code-based cryptography was carried out， and a cryptographic scheme with combination of dual public-key encryption method was proposed. The security of the proposed scheme was improved compared with the improved Niederreiter scheme and the Niederreiter dual public-key encryptographic scheme based on Quasi-Cyclic Low-Density Parity-Check （QC-LDPC） code. The amount of keys in the scheme is at least 32% lower than that of traditional Niederreiter scheme， and is also effectively reduced compared with that of the Niederreiter dual public-key encryptographic scheme based on QC-LDPC code， which shows the strong reliability for ensuring computer data security in the quantum age.

Key words： code-based cryptography; Niederreiter cryptosystem; system code; security analysis; efficiency analysis

0 引言

量子技術的概念近來越來越多地進入人們的視線，量子技術的計算能力在給人們帶來計算性能很強的并行計算、解決許多棘手問題的同時，也構成了不容忽視的安全威脅。密碼學中的傳統公鑰密碼在量子計算機出現后不會再像現在那么安全可靠，比如基于經典數論理論的RSA（Rivest-Shamir-Adleman）公鑰加密算法、橢圓曲線密碼（Elliptic Curve Cryptography， ECC）、屬性基密碼等，將會在量子計算機出現后不再可靠[1]。目前可以較為有效地抵抗量子計算攻擊的密碼體制主要有以下四種：基于編碼的密碼體制、基于格的密碼體制LWE（Learning With Errors）、基于Hash函數的密碼體制以及基于多變量的密碼體制。基于編碼的密碼體制具有較高的計算效率以及可操作性，是量子時代一種可靠的安全選擇。

基于編碼的公鑰密碼體制是在有限域上多元多項式環上定義和運算的，此類密碼體制的算法核心是對一種糾錯碼C的應用，主要的特征即為添加一個錯誤到碼字中或根據碼C的校驗矩陣計算伴隨式。1978年，美國科學家McEliece[2]第一個運用這種方法設計公鑰密碼算法，提出首個基于編碼理論的公鑰加密方案，其中私鑰為一個二元不可約Goppa碼，公鑰為該碼的生成矩陣被隨機化處理之后的結果。1986年，Niederreiter[3]提出了著名的基于Goppa碼的Niederreiter密碼體制。該方案的安全性被證明是與McEliece體制是相同的，Niederreiter體制的主要思想是從另一個角度利用隨機線性碼的譯碼困難問題，該方案隱藏的是Goppa碼的校驗矩陣，Niederreiter體制相比McEliece體制，公鑰存儲量有所下降，而且具有更高的傳信率。2018年，劉相信等[4]提出了一種對Niederreiter公鑰密碼系統的改進，可以隱藏明文的漢明重量來有效抵抗信息集譯碼（Information Set Decoding， ISD）攻擊等針對編碼密碼體制的攻擊，但是其安全性仍然可以在保障效率的前提下得到進一步提升。到目前的研究階段，基于編碼理論的公鑰密碼學的研究重點主要放在了對碼的選擇上，以保證安全性的同時，提高實用性，降低方案的密鑰尺寸，由最開始的Goppa碼、Reed-Solomon碼[5]，到現在的準循環中密度奇偶校驗（Quasi-Cyclic Medium-Density Parity-Check， QC-MDPC）碼[6]、低密度奇偶校驗（Low Density Parity Check， LDPC）碼[7]以及準循環低密度奇偶校驗（Quasi-Cyclic Low-Density Parity-Check， QC-LDPC）碼[8]等，通過不斷優化碼字的選擇，編碼密碼的公鑰量切實得到有效減少，但是安全性并沒有得到明顯的提升。

雙公鑰的思想是對明文進行二次加密，這種方法可以很好地提高公鑰密碼體制的安全性。2008年，張穎等[9]就曾利用雙公鑰對McEliece體制進行改進，使安全性有較好的提升，但是畢竟使用了雙公鑰的方式加密，會使得密鑰量增加，實用性不強。2016年，李沖等[10]提出了基于QC-LDPC碼的雙公鑰Niederreiter密碼方案，由于QC-LDPC碼的采用，能夠使得雙公鑰方案的密鑰量有所下降，安全性有較高提升，但是，密鑰量和安全性仍有較大的提升空間。本文嘗試將Niederreiter體制的改進版與雙公鑰的加密方式相結合，并采用系統碼，在增加方案安全性的同時，保證有效的實用性。

1 相關工作

1.1 SDP問題

校驗子譯碼問題（Syndrome Decoding Problem， SDP） 給定一個（n，k）的線性碼，它的最小漢明距離為d，該碼的校驗矩陣為H∈F（n-k）×n2，它的糾錯能力為t且t滿足方程d=2t+1。當給定一個向量v∈F（n-k）×n2時，尋找一個錯誤向量e∈Fn2，它的漢明重量要小于等于t，且與向量v以及矩陣H滿足方程v=eHT，尋找錯誤向量e這個問題已被證明為NP困難問題[11]。

通過上述對Niederreiter密碼方案改進版的闡述，可以發現許多針對Niederreiter方案的攻擊方法例如像ISD攻擊等的代價由于對重量t進行隱藏后變得較大，正是由于t的選擇變得靈活后，那么在選碼時便可選擇適當的維度來避免密鑰量過大，具體分析請參考文獻[4]，但文獻[4]若采用雙公鑰的加密方法能進一步加強方案的安全性，并通過選取系統碼來進行構造，避免方案的密鑰量過大，增加方案的實用性。

2 基于改進版Niederreiter的雙公鑰密碼方案

2.1 參數生成

選取兩個二元即約系統碼G1、G2維度分別為（n，k）和（n-k，k），糾錯能力分別為t1、t2，兩個碼對應的校驗矩陣為（n-k）×n維的H1和（n-2k）×（n-k）維的H2，且H2可以拆分為H2=H3+H4，其中矩陣H3、H4為隨機拆分得到的。兩個碼的譯碼算法為β1Ht（）和β2Ht（）。隨機選取一個（n-k）×（n-k）維可逆矩陣S，與一個n×n的置換矩陣T，并計算H=SH1T。再隨機選擇三個（n-2k）×（n-2k）的可逆矩陣A、B、C，以及（n-k）×（n-k）維的置換矩陣Q，并計算H′=AH3Q，H″=BH4Q，H=CH2Q。公開密鑰即為（H，H′，H″，H，t1，t2），私鑰即為（S，T，A，B，C，Q， β1Ht（）， β2Ht（））。

2.2 加密過程

首先利用系統碼G1所產生的公鑰H對n維明文m進行第一步加密，產生密文c1，c1=mHT。此處注意，在對G2進行選擇時，它的糾錯能力t2需要滿足t2>wt（c1），以方便后面的譯碼解密，且這一點在選碼時易于實現。

完成第一步后，進行第二步加密。將c1看作新的明文，用G2所產生的一系列公鑰對其進行加密。首先將進行拆分，c1=c2+c3，計算x1=c2H′T，x2=c2H″T，x3=c3HT，將（x1，x2，x3）作為密文，發送給接收者。

2）完成第一步解密得到c1后，第二步解密就是普通的Niederreiter密碼體制的譯碼解密。運用私鑰S，T和碼G1的譯碼算法β1Ht（）進行解密，具體如下：

利用譯碼算法β1Ht（）對mTTH1T譯碼即可得到mTT，利用私鑰T進行運算得到m=mTTTT-1。

從上述的加解密過程可以看出，加密時，先對明文進行傳統的Niederreiter加密，得到密文后，采用改進版Niederreiter再進行加密。解密時，先對改進版Niederreiter解密得到第一次加密的密文，再利用傳統的Niederreiter解密方式進行解密得到最后的明文即可。

3 安全性分析

3.1 直接攻擊

所謂直接攻擊，是指在擁有密文c和公鑰H′后，通過直接求解方程c=mH′T來求得明文的攻擊方法，但是Niederreiter密碼體制所依賴的是SDP校驗子譯碼問題，該問題為NP困難問題，因此直接通過方程來求解明文m是十分困難的。本文方案采用了雙公鑰的加密方法，使得破解的工作量至少翻倍，又由于第二次加密采用了改進的Niederreiter密碼體制，使得安全性又有了新的提升。

3.2 直接譯碼攻擊

直接譯碼攻擊是指通過公鑰H，H′，H″，H得到S，H1，T和A，H3與B，H4以及C，H2和Q，然后通過碼的快速譯碼算法得到明文m來攻破該體制。由矩陣的相關理論可以得知，矩陣的分解不是唯一的，比如像從矩陣H中分解出S，H1，T，它們各自可能的個數分別為2（n-2k）2∏n-2ki=1（1-2-i）、1t2nt2和（n-k）！，由此可見，當n和t的取值比較大時，矩陣可能的數目十分巨大，這導致敵手在多項式時間內是難以通過公鑰分解出私鑰的，而本文方案有4個公鑰矩陣，工作量會變為4倍，相比Niederreiter方案改進版[4]的三個公鑰矩陣和基于QC-LDPC碼的Niederreiter雙公鑰加密方案[11]的兩個矩陣，工作量加倍，安全性增強。

3.3 信息集譯碼（ISD）攻擊

李元興等[12]指出，可以通過解線性方程組的方法來攻破Niederreiter密碼體制。所謂信息集譯碼攻擊即ISD攻擊是指：給定明文m=（m1，m2，…，mn），以及加密方程c=mHT，任意選擇明文m=（m1，m2，…，mn）中的k個分量，并將其刪除，并相應刪除公鑰矩陣H中的k列，那么可得到新的方程即為c=m1×（n-k）HT（n-k）×（n-k），此時，若矩陣HT（n-k）×（n-k）可逆，那么可求得m1×（n-k）=c×HT-1（n-k）×（n-k），然后查看wt（m1×（n-k））是否為公開的漢明重量t，若為t，則在相應的k個位置上補零即可得到最后的明文m。當矩陣HT（n-k）×（n-k）不可逆或者最后求得的m1×（n-k）的漢明重量不符合要求時，需要重新選擇矩陣HT（n-k）×（n-k）進行以上運算。ISD攻擊對于編碼密碼來說是一種較為強力的攻擊方法，并且還被不斷深化與研究[13-17]。在文獻[18]中，已經證明采用雙公鑰方式進行兩次普通Niederreiter加密的方法可以有效抵抗此類攻擊，攻擊成功的工作因子為W=[（n-k）3Ckn-k-t2/Ckn]·[（n-2k）3Ckn/Ckn-t1]，因此當n，t選取較大時攻擊者在多項式時間內難以攻破雙公鑰的Niederreiter密碼體制。

本文采用雙公鑰的Niederreiter加密方式，在第一次加密時是采用的普通的Niederreiter密碼方案，第二次加密時則是采用的改進的Niederreiter密碼方案。改進的Niederreiter密碼體制的最大特點就是對加密的消息c1的漢明重量進行了隱藏，將其進行了拆分，成為了兩部分c1=c2+c3，并相應地將校驗矩陣H2進行了拆分H2=H3+H4，與拆分后的明文進行加密運算。采用ISD攻擊的一個關鍵所在就是要掌握明文的漢明重量，這樣才能確認是否攻擊成功。改進的Niederreiter密碼體制加密后的密文為xi=ciHT的形式，并非c1，那么ci的漢明重量也就更加靈活，取值范圍從0到n-k，那么攻擊者也就不能判斷wt（xiHT-1（n-2k）×（n-2k））是否符合要求，因此，對于一個漢明重量為ti的加密信息ci=（c1，c2，…，cn-k），右乘一個（n-k）×（n-2k）的矩陣HT，相當于在HT中選取相應的ti行，而0≤ti≤n-k，因此，采用解線性方程組攻擊第二次加密的代價為C0n-k+C1n-k+C2n-k+…+Cn-k-1n-k+Cn-kn-k=2n-k。綜上可知，ISD攻擊針對基于改進版Niederreiter的雙公鑰密碼方案的工作因子為W=2n-k·[（n-k）3Ckn-k-t2/Ckn]，相比基于QC-LDPC碼的雙公鑰Niederreiter密碼方案[11]有較大提升。Niederreiter改進版[4]只有一次加密的過程，它的工作因子為C0n-k+C1n-k+C2n-k+…+Cn-k-1n-k+Cn-kn-k=2n-k，從上面對本文方案工作因子的分析可以看出，二次加密的信息為第一次加密的密文，因此安全性較其有較大的提升。

4 效率分析

4.1 系統碼優勢

采用雙公鑰的加密方式，可以有效地提高系統的安全性;但是也會存在一個較為明顯的弊端，就是密鑰量的增加，而密鑰量對于基于編碼的密碼體制而言，本身就是一個缺陷。Niederreiter密碼體制在相同的安全性下相比McEliece體制的密鑰量有所減少;但是相對傳統的公鑰密碼像背包密碼等，它的密鑰量還是很大。如何有效提高編碼密碼體制的效率，減小公鑰量是個至關重要的問題。目前基于編碼理論的公鑰密碼學研究的重點主要放在了對碼的選擇上，由最開始的Goppa碼、Reed-Solomon碼，到現在的QC-MDPC碼、LDPC（Low Density Parity Check）碼以及QC-LDPC碼等，來減少編碼密碼的公鑰量。本文方案就采用系統碼來有效減少密鑰量。

系統碼的生成矩陣或者校驗矩陣，可以通過一系列行列變換變換為G=（Ik|Q）或H=（-QT|In-k），其中Q為一個k×（n-k）階的矩陣，那么它的轉置即為（n-k）×k階矩陣，而矩陣Ik，與In-k均為單位矩陣，由此，可以看出，系統碼在存儲時，只需對k×（n-k）階的矩陣Q或（n-k）×k階矩陣-QT（負號代表矩陣中的元素為其逆元）進行存儲即可，若不采用系統碼構造，則需對k×n階矩陣或（n-k）×n階矩陣進行存儲。在本文方案中，有四個公開的密鑰矩陣H、H′、H″、H，除了矩陣H的維度為（n-k）×n階，其余三個矩陣均為（n-2k）×（n-k）階，在采用系統碼后，對H進行存儲的維度為（n-k）×k階，對H進行存儲的維度為（n-2k）×k階，而對H′、H″進行存儲的維度與H的維度不同，是因為H由系統碼G2的校驗矩陣H2通過行列變換得到的，可以節約存儲，而H′、H″是由系統碼G2的校驗矩陣H2進行拆分得到的H3、H4通過行列變換得到，H3、H4未必滿足系統碼的性質，因此H′、H″的維度仍為（n-2k）×（n-k）階。以n=1024，k=1024-10t，t=55為例，普通Niederreiter密碼體制所存儲公鑰矩陣的尺寸為p1=（n-k）×n=56.32×104，而本文的雙公鑰Niederreiter密碼方案的公鑰尺寸為p2=（n-k）×k+（n-2k）×k+2×（n-2k）×（n-k）=38.03×104。由該例子可以看出，本文的雙公鑰Niederreiter密碼方案由于系統碼的采用不僅保證了安全性的提升，并有效降低了32%的公鑰量。表1為本文方案密鑰尺寸與改進版Niederreiter密碼方案進行比較。

改進版Niederreiter由于可對重量t進行隱藏，因此只需選取一個維度較小的碼字，而本文方案第二步采用的是改進版Niederreiter，因此可以選擇維度較小的系統碼，第一步選擇一個符合第2章描述的系統碼即可，因此相比改進版Niederreiter，密鑰量只多在一個系統碼上。由表1可以看出，本文方案由于采用的是系統碼，因此選擇兩個碼后，密鑰尺寸會有一定增加，但是在合理范圍內，并獲得更高的安全性。具體的安全性優勢已在第3章中進行了分析。

4.2 重量t優勢

本文的雙公鑰Niederreiter密碼方案另一個優勢特點就是在第二步加密時采用的改進版Niederreiter密碼方案，如3.3節所述，它可以很好地將加密信息的漢明重量進行隱藏，所達到的效果就是使得ISD攻擊的代價對于（n，k，t）維的碼為C0n+C1n+C2n+…+Cn-1n+Cnn=2n，這相比傳統Niederreiter密碼方案在安全性方面有很大的提升。為了提高方案的使用效率，就可以考慮在選碼時降低漢明重量t的選擇，沒有必要再去選擇t過大的碼，而可以達到同樣的安全性要求，這就相比基于QC-LDPC碼的雙公鑰Niederreiter密碼方案[10]在選擇碼時可以減小碼的維度，以達到降低公鑰尺寸的目的。將第二步加密時的選碼與基于QC-LDPC碼的雙公鑰Niederreiter密碼方案[10]的第二步選碼進行比較，結果如表2所示。

由表2可以看出，本文方案相比QC-LDPC碼方案可以選擇較小維度的碼字以達到同QC-LDPC碼方案同樣的安全級別，使得公鑰的尺寸有很大幅度的下降，如表1中在80b安全級下，本文方案密鑰尺寸為5040b而QC-LDPC碼方案為28408b。

由于最后的密文是由G2碼的公鑰產生，因此G1碼在選擇時也可以選擇較小的漢明重量t，而不會影響到整個雙公鑰體系的安全，但是G1、G2碼的選擇由于解密時還要考慮譯碼問題，如2.2節所述，需要結合實際情況進行選擇。結合4.1節的分析，可以看出本文的雙公鑰Niederreiter密碼方案不僅安全性得到較大的提升，而且在公鑰尺寸這兩處的表述有疑問，“公鑰尺寸”此處是否應該為“效率”，因為后面已經提及了“公鑰尺寸”是下降的?；貜停褐苯觿h除“公鑰尺寸方面也有一定的提升”直接連接“公鑰尺寸相比……”一句方面也有一定的提升，公鑰尺寸相比基于QC-LDPC碼的雙公鑰Niederreiter密碼方案有效降低下降這處的表述不嚴謹，降低是否應為下降？請明確，相比傳統的Niederreiter密碼方案至少下降了32%，能夠在更多的場景中有效運用。

5 結語

基于編碼的密碼體制是抗量子計算時代的優良候選者之一，雙公鑰的加密方式旨在增加密碼方案的安全性。本文對改進版Niederreiter密碼方案以及雙公鑰加密方式進行深入研究，將二者進行結合，并采用系統碼，提出了一個雙公鑰Niederreiter密碼方案。本文方案在安全性方面相比改進版Niederreiter得到顯著提升，可以良好地抵抗ISD等針對編碼密碼體制的攻擊。本文方案在公鑰量方面，相比Niederreiter密碼方案至少下降了32%，而相比基于QC-LDPC碼的雙公鑰Niederreiter密碼方案也有效降低。優良的性質使得本文方案在今后的抗量子密碼時代能夠為計算機安全提供可靠的安全保障，但是需要注意的一點便是在選擇系統碼時要結合實際情況以及應用場景選擇合適的參數，以保證方案的正確性。

參考文獻 （References）

[1] RIVEST R L， SHAMIR A， ADLEMAN L. A method for obtaining digital signatures and public-key cryptosystems [J]. Communications of the ACM， 1978， 21（2）： 120-126.

[2] McELIECE R J. A public-key cryptosystem based on algebraic coding theory [J]. DSN Progress Report， 1978， 42（44）： 114-116.

[3] NIEDERREITER H. Knapsack-type cryptosystems and algebraic coding theory [J]. Problems of Control and Information Theory， 1986， 15（2）： 159-166.

[4] 劉相信，楊曉元.Niederreiter公鑰密碼方案的改進[J].計算機應用，2018，38（7）：1956-1959.（LIU X X， YANG X Y. Improvement of the Niederreiter public key system [J]. Journal of Computer Applications， 2018， 38（7）： 1956-1959.）

[5] 張俊.編碼的構造與譯碼問題及其在密碼學中的應用[D].天津：南開大學，2014：23-39.（ZHANG J. The problem of coding construction and decoding and its application in cryptography [D]. Tianjin： Nankai University， 2014： 23-39.）

[6] 李澤慧，楊亞濤，李子臣.基于QC-MDPC碼的公鑰密碼方案設計[J].計算機應用研究，2015，32（3）：881-884.（LI Z H， YANG Y T， LI Z C. Design of public key cryptography based on QC-MDPC code [J]. Application Research of Computers， 2015， 32（3）： 881-884.）

[7] 曹東，趙生妹，宋耀良.一種基于量子準循環LDPC碼的McEliece公鑰密碼算法[J].南京郵電大學學報（自然科學版），2011，31（2）：64-68.（CAO D， ZHAO S M， SONG Y L. A McEliece public key cryptography algorithm based on quantum quasi-cyclic LDPC Code[J]. Journal of Nanjing University of Posts and Telecommunications （Natural Science Edition）， 2011， 31（2）： 64-68.）

[8] 王延麗.基于QC-LDPC碼的McEliece公鑰密碼體制研究[D].西安：西安電子科技大學，2013：1-5.（WANG Y L. Research on McEliece public key cryptosystem based on QC-LDPC code [D]. Xian： Xidian University， 2013： 1-5.）

[9] 張穎，岳殿武.基于代數幾何碼的公鑰密碼體制[J].通信學報，2008，29（6）：75-81.（ZHANG Y， YUE D W. Public key cryptosystem based on algebraic geometry codes [J]. Journal on Communications， 2008， 29（6）： 75-81.）

[10] 李沖，韓益亮.基于QC-LDPC碼的雙公鑰Niederreiter密碼方案[J].計算機應用研究，2016，33（11）：3446-3449.（LI C， HAN Y L. Double public key Niederreiter cryptography scheme based on QC-LDPC code [J]. Application Research of Computers， 2016， 33（11）： 3446-3449.）

[11] 范武英，任方.基于校驗子譯碼問題的偽隨機序列研究綜述[J].西安郵電大學學報，2017，22（2）：1-6.（FAN W Y， REN F. Review of pseudo-random sequence based on syndrome decoding problem[J]. Journal of Xian University of Posts and Telecommunications， 2017， 22（2）： 1-6.）

[12] 李元興，王新梅.關于代數碼Niederreiter公鑰密碼體制的安全性及參數優化[J].電子學報，1993，21（7）：33-36.（LI Y X， WANG X M. On the security and parameter optimization of algebraic Niederreiter public key cryptography [J]. Acta Electronica Sinica， 1993， 21（7）： 33-36.）

[13] PRANGE E. The use of information sets in decoding cyclic codes[J]. IRE Transactions on Information Theory， 1962， 8（5）： 5-9.

[14] MAY A， OZEROV I. On computing nearest neighbors with applications to decoding of binary linear codes[C]// EUROCRYPT 2015： Proceedings of the 2015 Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin： Springer， 2015： 203-228.

[15] 李夢東，蔡坤錦，邵玉芳.信息集攻擊算法的改進[J].密碼學報，2016，3（5）：505-515.（LI M D， CAI K J， SHAO Y F. An improved algorithm of information set decoding [J]. Journal of Cryptologic Research， 2016， 3（5）： 505-515.）

[16] TORRES R C， SENDRIER N. Analysis of information set decoding for a sub-linear error weight [C]// PQCrypto2016： Proceedings of the 2016 International Workshop on Post-Quantum Cryptography. Berlin： Springer， 2016： 144-161.

[17] KACHIGAR G， TILLICH J P. Quantum information set decoding algorithms[C]// PQCrypto 2017： Proceedings of the 2017 International Workshop on Post-Quantum Cryptography. Berlin： Springer， 2017： 69-89.

[18] 楊磊鑫，杜偉章.利用雙公鑰的Niederreiter公鑰密碼體制的改進[J].長沙理工大學學報（自然科學版），2010，7（4）：74-77.（YANG L X， DU W Z. Improvement of Niederreiter public key cryptosystem using double public key [J]. Journal of Changsha University of Science and Technology （Natural Science）， 2010， 7（4）： 74-77.）