李 喆，韓益亮，李 魚，朱率率，楊曉元

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

2019年10月26日，第十三屆全國人大常委會(huì)第十四次會(huì)議通過了《中華人民共和國密碼法》，通過制度的形式把信息安全的重要性上升為國家意志。現(xiàn)在社會(huì)中的銀行交易、無人駕駛、衛(wèi)星通信、指揮控制等方面，密碼學(xué)具有不可替代的作用。隨著科學(xué)技術(shù)的飛速發(fā)展，量子計(jì)算機(jī)逐漸進(jìn)入人們的視野，其強(qiáng)大的計(jì)算能力備受青睞，量子計(jì)算機(jī)強(qiáng)大的計(jì)算能力在諸多方面帶來了極大的便利，但是其強(qiáng)大的計(jì)算能力也對經(jīng)典計(jì)算機(jī)(圖靈機(jī))條件下基于數(shù)論的密碼體制帶來了嚴(yán)重的威脅。目前，大部分密碼體制都依賴于經(jīng)典計(jì)算機(jī)在多項(xiàng)式時(shí)間內(nèi)無法有效解決的兩個(gè)計(jì)算困難問題，即大整數(shù)分解和離散對數(shù)問題。Shor[1]提出了可以在多項(xiàng)式時(shí)間內(nèi)破解大整數(shù)問題和離散對數(shù)問題的量子算法，這一算法使得經(jīng)典的公鑰密碼方案極不安全，RSA[2]、離散橢圓曲線方案(Elliptic Curve Cryptography, ECC)[3]等密碼體制的安全性受到挑戰(zhàn)。因此，為了應(yīng)對量子計(jì)算機(jī)帶來的挑戰(zhàn)，許多密碼學(xué)者嘗試構(gòu)造可以抵御量子計(jì)算的新型密碼體制，即抗量子計(jì)算密碼體制(Post-Quantum Cryptography, PQC)。PQC主要有五種[4]：基于編碼的公鑰密碼體制、基于格的公鑰密碼體制、基于哈希樹的公鑰密碼體制、基于多變量的公鑰密碼體制、超奇異橢圓曲線同源密碼。

2015年，美國和歐盟分別推動(dòng)抗量子密碼的標(biāo)準(zhǔn)化進(jìn)程[5]。2018年，美國國家標(biāo)準(zhǔn)與技術(shù)研究院(National Institute of Standards and Technology, NIST)面向全球征集抗量子密碼，舉辦第一輪PQC算法征集會(huì)議，基于編碼的密碼體制占有很大的比例[6]。2019年，NIST評選第二輪后量子密碼算法，基于編碼的密碼方案依然具有很大的比重[7]。在未來的研究過程中，基于編碼的密碼體制依然是研究的熱點(diǎn)。

為了使我國后量子密碼算法同步推進(jìn)，國家密碼局于2018年面向全國征求密碼算法，目前，全國密碼算法設(shè)計(jì)競賽第一輪算法評選結(jié)果已經(jīng)揭曉，第二輪算法評選正在進(jìn)行中，預(yù)計(jì)于2022年左右開展抗量子密碼算法標(biāo)準(zhǔn)化工作。

基于編碼的密碼體制最初是由McEliece[8]提出的，其一般性譯碼問題屬于一般線性碼的非確定性多項(xiàng)式完全問題。到目前為止，原始的方案依然具有安全性。該體制采用Goppa碼，具有加解密速度快、計(jì)算復(fù)雜度低的優(yōu)點(diǎn)。但現(xiàn)實(shí)中沒有大量使用該體制的原因是，其密鑰儲存空間太大、碼率低。Niederreiter[9]提出了基于GRS碼的Niederreiter密碼體制，相較于McEliece體制，該體制密鑰存儲空間減少，但仍然不能投入到實(shí)際使用中。因此，許多學(xué)者為了減小密鑰的尺寸，推動(dòng)提高密碼方案的實(shí)用化，改進(jìn)McEliece體制，提出了用其他結(jié)構(gòu)更加緊湊的編碼代替Goppa碼，例如準(zhǔn)循環(huán)低密度奇偶校驗(yàn)碼(Quasi-Cyclic Low-Density Parity Check, QC-LDPC)碼[10]、Polar碼[11]、中密度奇偶校驗(yàn)碼(Medium Density Parity Check, MDPC)碼[12]、Gabidulin碼[13]、低秩奇偶校驗(yàn)(Low Rank Parity Check， LRPC)碼[14]，改進(jìn)的密碼方案減少了密鑰長度，但容易受到攻擊[15]。

后來，基于編碼的方案進(jìn)一步發(fā)展，一些學(xué)者對McEliece體制的結(jié)構(gòu)進(jìn)行變型。Wang[16]在生成矩陣的每一列中都嵌入了隨機(jī)列并構(gòu)造了一種線性隨機(jī)碼的加密方案RLCE。Kim等[17]通過將McEliece和Niederreiter相結(jié)合，利用秩度量的編碼構(gòu)造了McNie密碼方案。劉相信等[18]通過隱藏明文的漢明重量，將校驗(yàn)矩陣拆分構(gòu)造了一種新型密碼方案。Mostafa[19]通過利用錯(cuò)誤向量的漢明重量大于編碼最小距離的性質(zhì)，構(gòu)造了一種不同的密碼方案。

本文根據(jù)編碼的性質(zhì)，總結(jié)了基于漢明度量編碼和基于秩度量的加密方案，歸納了目前發(fā)展的現(xiàn)狀，展望了未來的發(fā)展方向。介紹了目前基于McEliece方案進(jìn)行結(jié)構(gòu)改變的新型密碼方案，為將來研究抗量子密碼方案提供了新的方向。綜述了目前對基于編碼的密碼方案主流的攻擊方法。

1 基于糾錯(cuò)碼的密碼體制

1.1 McEliece加密體制

該密碼體制包括密鑰生成(公鑰、私鑰)、加密過程、解密過程三部分。

1)密鑰生成過程如下：

①隨機(jī)生成長度為n，維度為k的k×n階生成矩陣G，其中最小距離d≥2t+1；

②生成k×k階隨機(jī)非奇異可逆矩陣S；

③生成n×n階二元隨機(jī)置換矩陣P。

G左乘隨機(jī)非奇異可逆矩陣S，右乘隨機(jī)置換矩陣P，得到擾亂后的k×n階矩陣Gpub，Gpub=SGP。其中，公鑰為Gpub和t；私鑰為S、DC、P，DC是編碼C的譯碼算法。

2)加密過程如下：

①隨機(jī)選擇錯(cuò)誤向量e∈Fn，其中，F(xiàn)n為有限域上的n維線性向量空間，wt(e)≤t；

②發(fā)送方利用接收方的公鑰Gpub對發(fā)送的消息m進(jìn)行加密，得到密文c。c=mGpub⊕e，其中m∈Fk。

3)解密過程如下：

①接收方收到密文c，利用自己的私鑰對密文進(jìn)行解密；

②cP-1=(mS)G⊕eP-1。

利用編碼的譯碼算法進(jìn)行譯碼，mS=DC(cP-1)，m1=mS，m=m1S-1。

目前，這一方案的研究目標(biāo)和發(fā)展方向主要有以下三類：

1)采用Goppa碼的原始方案，到目前為止都足夠安全，下一步的關(guān)注點(diǎn)是，在保證安全性的基礎(chǔ)上，分析目前存在的攻擊類型，合理選用參數(shù)，對Goppa碼進(jìn)行變型，如交織Goppa碼；

2)進(jìn)一步分析原始方案存在的攻擊，尤其是要關(guān)注側(cè)信道攻擊，在模擬仿真平臺上實(shí)現(xiàn)密碼方案，通過側(cè)信道攻擊檢驗(yàn)方案的安全性；

3)分析McEliece密碼體制延展性以及消息重放攻擊，進(jìn)一步研究方案保證其安全性。

1.2 Niederreiter密碼體制

Niederreiter采用McEliece的對偶形式提出了Niederreiter體制，與McEliece公鑰密碼體制不同的是，Niederreiter密碼體制采用一致校驗(yàn)矩陣來構(gòu)造加密算法。同樣地，該密碼體制包括密鑰生成(公鑰、私鑰)、加密過程、解密過程三部分。

1)密鑰生成過程如下：

①系統(tǒng)參數(shù)：n,t∈N。

②生成M：(n-k)×(n-k)階可逆矩陣。

③生成H：糾正t個(gè)錯(cuò)誤的編碼C的(n-k)×n階校驗(yàn)矩陣。

④生成P：n×n階隨機(jī)置換矩陣。

⑤計(jì)算Hpub=MHP。

2)加密過程如下：

計(jì)算s=HpubeT，其中，e∈{0,1}n。

3)解密過程如下：

計(jì)算M-1s=HPeT，利用伴隨式譯碼算法恢復(fù)PeT，計(jì)算eT=P-1PeT。

McEliece體制的公鑰為k×nbit，Niederreiter公鑰體制的公鑰為(n-k)×nbit，采用這種對偶變型的密碼方案，可以有效減小密鑰長度。在McEliece體制中，攻擊者可以通過兩個(gè)被加密消息之間的關(guān)系來確定錯(cuò)誤位置。而Niederreiter公鑰體制并不存在延展性，所以不會(huì)遭到密文的延展性攻擊和消息重放攻擊。

目前，這一方案的研究目標(biāo)和發(fā)展方向主要有以下兩類：

1)研究重點(diǎn)逐漸聚焦在采用Niederreiter 密碼體制進(jìn)行簽名方案的構(gòu)造；

2)研究改進(jìn)Niederreiter 密碼體制在硬件上面的實(shí)現(xiàn)，提高效率和實(shí)用性。

1.3 研究現(xiàn)狀

目前關(guān)于McEliece密碼體制的研究大概分為兩類：

1)研究改進(jìn)McEliece原始方案的結(jié)構(gòu)分析其原始方案的底層編碼，選擇性能更優(yōu)的碼字來替代原始方案的Goppa碼，達(dá)到減小密鑰長度的目的，使其投入到實(shí)際運(yùn)用中；

2)研究分析McEliece原始方案及其變型的安全性，分析其存在安全性問題的原因，進(jìn)一步完善密碼方案。

2 采用其他編碼改進(jìn)的McEliece體制

2.1 基于漢明度量編碼的密碼方案

2.1.1 基于LDPC/MDPC碼的密碼方案

采用LDPC碼或MDPC碼代替原來的Goppa碼，LDPC碼或MDPC碼具有有效的迭代譯碼算法，可以明顯降低譯碼錯(cuò)誤率，并且采用其循環(huán)結(jié)構(gòu)可以有效減小公鑰尺寸。MDPC碼奇偶校驗(yàn)矩陣的行列密度比LDPC碼高。

Monico等[20]提出用LDPC碼代替原來的Goppa碼。Baldi等[10]提出基于QC-LDPC碼的McEliece體制，該體制可以減小密鑰大小，具有一定的安全性，采用比特迭代譯碼算法可以快速解碼。但其對偶碼存在低維數(shù)的漏洞，易被攻破。Baldi等[21]提出改進(jìn)的QC-LDPC變型，其中可逆矩陣和置換矩陣都采用稀疏矩陣，提高了安全性，可以抵抗結(jié)構(gòu)化攻擊。Shooshtari等[22]指出，Baldi改進(jìn)后的方案容易受到信息集譯碼攻擊(Information Set Decoding, ISD)，原因是改進(jìn)后的QC-LDPC方案中，會(huì)出現(xiàn)循環(huán)矩陣的循環(huán)塊為偶數(shù)的情況。

Misoczki等[23]提出基于QC-MDPC碼的McEliece體制來抵御已知的對LDPC碼的攻擊，同時(shí)減小了密鑰量。Guo等[24]通過研究譯碼錯(cuò)誤率與密鑰距離譜之間的聯(lián)系，對文獻(xiàn)[23]提出的QC-MDPC方案進(jìn)行了密鑰恢復(fù)攻擊。Fab?i?等[25]同樣通過大量實(shí)驗(yàn)尋找置換矩陣Q與譯碼錯(cuò)誤率之間的關(guān)聯(lián)性，對密鑰進(jìn)行恢復(fù)攻擊。

Moufek等[26]提出一種新的思路，將兩種奇偶校驗(yàn)碼結(jié)合使用。該方案通過QC-LDPC碼和QC-MDPC碼的級聯(lián)使用，可以減少密鑰長度，采用偽隨機(jī)生成矩陣具有一定的安全性。Dragoi等[27]對文獻(xiàn)[26]改進(jìn)的方案進(jìn)行安全性分析，發(fā)現(xiàn)文獻(xiàn)[26]改進(jìn)的方案存在極大的漏洞。

目前，這一方案的研究目標(biāo)和發(fā)展方向主要有以下兩類：

1)研究QC-LDPC碼和QC-MDPC碼的性質(zhì)，進(jìn)一步改進(jìn)方案的譯碼算法，減小譯碼錯(cuò)誤率，提高譯碼效率；

2)分析采用QC-LDPC碼和QC-MDPC碼密碼方案的結(jié)構(gòu)，研究低重量搜索攻擊對其密碼方案的影響，并對其安全性做進(jìn)一步分析。

2.1.2 基于Polar碼的密碼方案

Polar碼是目前可以在理論上證明趨于Shannon限的編碼。Arikan提出Polar碼[28]，并深入研究Polar碼的性質(zhì)，后來眾多學(xué)者進(jìn)一步研究了Polar碼的結(jié)構(gòu)及性能。

首先，Polar碼比Goppa碼等其他編碼糾錯(cuò)能力更強(qiáng)；其次，極化碼的連續(xù)消除譯碼算法比Goppa碼的譯碼效率更高，降低了解密過程中的計(jì)算復(fù)雜度。通過研究極性碼的性質(zhì)，Mahdlavifar等嘗試把極化碼應(yīng)用到密碼學(xué)中，并取得了一定的進(jìn)展[29]。Hooshmand 等[30]利用極化碼的性質(zhì)構(gòu)造對稱密碼體制。Hooshmand 等[31]為了避免主動(dòng)攻擊和被動(dòng)攻擊，通過分析有限長度極化碼的性質(zhì)，提出了基于物理層加密(Physical Layer Encryption, PLE)方案[32]，在合法的通信雙方建立安全可靠的保密通信。

Shrestha等[33]將Polar碼應(yīng)用到編碼密碼中，提出了基于Polar碼的McEliece密碼方案。Hooshmand等[34]在原有方案的基礎(chǔ)上，優(yōu)化了基于Polar碼的McEliece密碼方案，減少了密鑰存儲空間。但是，Bardet等[35]分析了文獻(xiàn)[34]中提出的基于Polar碼的McEliece密碼方案的結(jié)構(gòu)，提出了密鑰恢復(fù)攻擊的方法。這種攻擊方法可以獲得文獻(xiàn)[33]方案解密密文所需要的任何信息。楊超等[36]利用Polar碼譯碼算法的低復(fù)雜性構(gòu)造Niederreiter 公鑰密碼體制，并進(jìn)行了仿真分析。Drǎgoi等[37]證明任何基于弱遞減單項(xiàng)式碼的密碼方案都有可能受到密鑰恢復(fù)攻擊，基于Polar碼的密碼方案也不例外。

目前，這一方案的研究目標(biāo)和發(fā)展方向主要有四類：

1)進(jìn)一步研究Polar碼，研究其極化現(xiàn)象的原因，提高中等長度碼字的編碼效率；

2)進(jìn)一步研究其譯碼算法，分析連續(xù)消除算法，列表連續(xù)刪除譯碼算法，加入循環(huán)冗余檢驗(yàn)位的列表連續(xù)刪除算法的性能，在提高譯碼正確率的同時(shí)提高譯碼效率；

3)把Polar碼的極化性質(zhì)應(yīng)用到簽名領(lǐng)域，把極化性質(zhì)與簽名有效結(jié)合，提高簽名的效率；

4)通過把Polar碼與其他性能好的碼字相級聯(lián)，克服了Polar碼在中等長度時(shí)性能差的缺點(diǎn)，總體上使密碼方案的效率與安全性達(dá)到最佳。

2.1.3 基于RS碼/GRS碼的密碼方案

該體制采用RS碼或GRS碼代替McEliece原始方案中的Goppa碼。GRS碼存在有效譯碼算法，可以有效減少公鑰長度。

基于GRS碼的Niederreiter體制變型被Silelnikov等完全攻破，當(dāng)公鑰Hpub的列元素可以表示為支撐元素的多項(xiàng)式，利用各列元素的關(guān)系可求出支撐向量和常數(shù)向量[38]。Wieschebrink[39]提出用GRS碼與隨機(jī)碼并列的級聯(lián)碼避免了文獻(xiàn)[38]中提到的攻擊。Couvreur等[40]針對三種GRS變型，采用GRS碼的平方碼構(gòu)造與隨機(jī)碼相區(qū)分的區(qū)分器，進(jìn)而采用密鑰恢復(fù)攻擊，能夠在多項(xiàng)式時(shí)間內(nèi)攻破文獻(xiàn)[39]所采用的級聯(lián)碼方案。

Márquez-Corbella等[41]提出用兩個(gè)GRS碼構(gòu)造“u/u+v”的變型。目前，這一方案的研究目標(biāo)和發(fā)展方向主要有兩類。

1)進(jìn)一步研究文獻(xiàn)[38]針對基于GRS碼的密碼體制提出的攻擊方法，分析這種攻擊是否會(huì)對McEliece體制原始方案的安全性造成影響；

2)進(jìn)一步研究采用GRS碼的Niederreiter體制，利用Niederreiter體制可以抵抗反應(yīng)攻擊和延展性攻擊的優(yōu)點(diǎn)，深究其本質(zhì)，設(shè)計(jì)可以達(dá)到原始方案的新型密碼體制。

2.2 基于秩度量編碼

基于漢明度量的McEliece密碼，使用Goppa碼或MDPC碼，其缺點(diǎn)是有相對較大的密鑰。原始基于編碼的密碼方案是基于具有漢明度量的Goppa碼，實(shí)際上可以考慮基于秩度量的編碼。秩度量的特別之處在于譯碼問題的實(shí)際難度隨著參數(shù)的增大而迅速增大。在同樣安全級別下，基于秩度量的密碼方案比基于漢明度量的密碼方案更安全。與基于漢明度量的編碼相比，秩度量中已知的具有高效譯碼算法的碼族很少?？梢杂糜贛cEliece方案的兩大類秩度量編碼，即Gabidulin碼和LRPC碼?；贚RPC碼的密碼方案，因其低代數(shù)結(jié)構(gòu)，逐漸成為研究的熱點(diǎn)。

Kshevetskiy等對基于Gabidulin碼的原始方案進(jìn)一步優(yōu)化參數(shù)，在保證安全性的同時(shí)進(jìn)一步減少密鑰尺寸[42]。Overbeck[43]針對基于秩度量編碼的原始方案及其變型進(jìn)行分析，提出一種有效的攻擊方法。該攻擊主要是對基于秩度量碼的密碼方案進(jìn)行分析，發(fā)現(xiàn)Gabidulin碼包含一個(gè)巨大的向量空間不變作用下的弗羅貝尼烏斯自同構(gòu)。后來，許多學(xué)者試圖用其他擾亂矩陣來避免存在的已知其他攻擊，但是Gabidulin代碼自身存在的問題仍沒有消失[44]。換句話說，對編碼進(jìn)行擾亂的生成器的一些核心部分仍然存在向量空間不變的問題，這就增加了系統(tǒng)的弱點(diǎn)。

為了抵御文獻(xiàn)[43]提及的攻擊，Loidreau[45]對維度等參數(shù)進(jìn)行優(yōu)化，提出一種基于新型秩度量的編碼體制。Coggia等[46]對文獻(xiàn)[45]提出的密碼方案進(jìn)行安全性分析，指出當(dāng)λ=2時(shí)，攻擊者有超過50%的可能性用區(qū)分器把公共代碼和隨機(jī)碼區(qū)分開，利用這個(gè)區(qū)分器可以在多項(xiàng)式時(shí)間內(nèi)實(shí)現(xiàn)密鑰恢復(fù)攻擊。Aragon等[47]提出一種新的譯碼算法，該方法可以降低以往方案的譯碼錯(cuò)誤概率。Aragon等[48]利用LRPC碼在選擇明文攻擊下的不可區(qū)分性(INDistinguishability-Chosen ciPhertext Attacks, IND-CPA)情況解密失敗條件下，采用一種代數(shù)方法對解密失敗發(fā)生的情況進(jìn)行建模，然后根據(jù)攻擊者可以利用IND-CPA方案中發(fā)送給解密oracle的錯(cuò)誤這一事實(shí)，對比文獻(xiàn)[24]中提出的對QC-MDPC碼密鑰恢復(fù)攻擊，Aragon等嘗試把這種攻擊應(yīng)用到基于秩度量的密碼方案。

與漢明度量相比，秩度量的優(yōu)勢比較明顯，在一定的參數(shù)選擇范圍下，通過搜索低重量攻擊的復(fù)雜度會(huì)明顯提升。

目前，這一方案的研究目標(biāo)和發(fā)展方向主要有以下兩類：

1)分析研究LRPC碼的結(jié)構(gòu)，改進(jìn)譯碼算法以減小LRPC碼的譯碼錯(cuò)誤率；

2)尋找隱藏Gabidulin碼結(jié)構(gòu)的方法，使其能夠抵抗文獻(xiàn)[43]提及的攻擊。

3 McEliece加密方案結(jié)構(gòu)的變型

3.1 McNie方案

Kim等[17]提出將McEliece方案和Niederreiter方案結(jié)合的McNie加密方案，該方案采用4-循環(huán)低秩奇偶校驗(yàn)碼，能夠抵抗目前已知的結(jié)構(gòu)化攻擊，減小了密鑰的大小。Lau等[49]針對McNie方案提出了一種密鑰恢復(fù)攻擊，能夠恢復(fù)McNie方案所有參數(shù)下的密鑰，進(jìn)而提出了一種新的基于Gabidulin碼的McNie方案，該新方案不存在譯碼失敗率。Aragon等[48]對McNie方案采用消息恢復(fù)攻擊和改進(jìn)的信息集譯碼攻擊，使McNie方案的安全級別減半。Kim等[50]在文獻(xiàn)[49]改進(jìn)的基礎(chǔ)上，進(jìn)一步提出了McNie2-Gabidulin方案，該方案具有IND-CPA安全性，密鑰尺寸小于其他沒有譯碼失敗概率的密碼方案。

1)密鑰生成過程如下：

①對于給定的參數(shù)n和r，產(chǎn)生下列矩陣:

G′：域Fqm上的信息數(shù)為k、最小距離l>n-k碼C的k×n階生成矩陣。

S：(n-k)×(n-k)階可逆矩陣。

H：一個(gè)能夠糾正r個(gè)錯(cuò)誤的碼C的(n-k)×n階校驗(yàn)矩陣。

P：n×n階隨機(jī)置換矩陣。

②計(jì)算矩陣F=G′P-1HTS。

公鑰：(G′,F)。

私鑰：(S,H,P)。

c1=mG′+e

(1)

c2=mF

(2)

3)解密過程如下：

S′=c1P-1HT-c2S-1=eP-1HT

(3)

接收者利用譯碼算法

φH(S′)=eP-1

(4)

c1-e=mG′

(5)

得到m。

把McNie體制和McEliece類比，則

G′=SGPF=G′P-1HTS=(SGP)P-1HTS

(6)

因?yàn)镚HT=0，所以F=0，推出c2=0，c1=mG′+e，這就是McEliece體制的原始方案。

目前，這一方案的研究目標(biāo)和發(fā)展方向主要有以下兩類：

1)分析研究McNie方案，找到McNie方案沒有入圍第二輪抗量子候選方案的原因；

2)尋找隱藏Gabidulin碼結(jié)構(gòu)的方法，使其能夠抵抗文獻(xiàn)[43]提及的攻擊。

3.2 改進(jìn)版Niederreiter密碼方案

劉相信等[18]對錯(cuò)誤向量e的重量進(jìn)行了隱藏，提出的Niederreiter密碼方案改進(jìn)版可以抵抗ISD攻擊。

1)密鑰生成過程如下：

①選擇二元(n,k,t)Goppa碼，糾錯(cuò)能力為t，校驗(yàn)矩陣為(n-k)×n，快速譯碼算法為βHt。

②將H隨機(jī)拆分成兩個(gè)矩陣H1、H2(H=H1+H2)，隨機(jī)選取三個(gè)階數(shù)為(n-k)×(n-k)可逆矩陣S1、S2、S3，選取一個(gè)n×n階的可逆置換矩陣P，分別計(jì)算H′=S1H1P，H″=S2H2P，H?=S3HP。

③公鑰：(H′,H″,H?,t)。

④私鑰：(S1,S2,S3,T,βHt)。

2)加密過程如下：

將明文m編碼成漢明重量t的向量e，并將e拆分為兩個(gè)向量e1、e2,且e=e1+e2，wt(e1)=t1，wt(e2)=t2(t≠t1≠t2)。計(jì)算

(7)

將(c1,c2,c3)發(fā)送給接收方。

3)解密過程：收到(c1,c2,c3)后，計(jì)算

(8)

(9)

(10)

因?yàn)镠=H1+H2，e=e1+e2。所以

(11)

利用譯碼算法βHt進(jìn)行譯碼可得ePT，再利用私鑰P，即可得到密文e=ePT(PT)-1。

目前，這一方案的研究目標(biāo)和發(fā)展方向主要有兩類：

1)研究本方案的安全性，隱藏后的錯(cuò)誤向量是否可以保證密碼方案的安全；

2)選擇其他編碼進(jìn)一步減少密鑰長度，例如LRPC碼。

3.3 改進(jìn)錯(cuò)誤向量的密碼方案

Mostafa[19]在其博士論文中提出Mostafa Esmaeili方案，該方案在McEliece加密的基礎(chǔ)上，改變了McEliece的結(jié)構(gòu)，不再利用可逆矩陣和置換矩陣對生成的矩陣進(jìn)行擾亂，主要利用漢明重量大于編碼最小距離的錯(cuò)誤向量，構(gòu)造了新型的密碼方案。該密碼方案與McEliece方案構(gòu)造過程類似，包括密鑰生成(公鑰、私鑰)、加密過程、解密過程三部分。

1)密鑰生成過程如下：

①G：域F上的維度為k、最小距離d≥2t+1的碼C的k×n階生成矩陣。

②H：域F上的(n-k)×n階的校驗(yàn)矩陣。

③S：(n-k)×(n-k)隨機(jī)非奇異可逆矩陣。

④公鑰：(G，S(H-1)T)。

⑤私鑰：HTS-1。

2)加密過程如下：

發(fā)送者選擇長度為l1的消息m，隨機(jī)選擇長度為l2的隨機(jī)比特串r(其中l(wèi)=l1+l2)，將隨機(jī)比特串r與明文m并聯(lián)，得到[r|m]。隨機(jī)選擇n-k位的向量s，計(jì)算sS(H-1)T，假如wt(sS(H-1)T)

發(fā)送者使用接收者的公鑰對并聯(lián)后的消息進(jìn)行加密，得到

c=[r|m]G+sS(H-1)T

(12)

3)解密過程如下：

接收者收到密文c后，使用自己的私鑰對密文進(jìn)行解密。

cHTS-1=([r|m]G+sS(H-1)T)HTS-1=s

(13)

接收者通過自己的私鑰對密文進(jìn)行解密得到s，然后用向量s乘以公鑰S(H-1)T，得到sS(H-1)T，然后計(jì)算

[r|m]G=c+sS(H-1)T

(14)

利用譯碼算法對[r|m]G進(jìn)行解密，得到[r|m]，把長度為l2的隨機(jī)比特串r丟棄，最后得到明文m。

目前，這一方案的研究目標(biāo)和發(fā)展方向主要有三類：

1)研究編碼的性質(zhì)，尋找適合構(gòu)造本方案的編碼；

2)研究本密碼方案是否可以抵御其他類型的攻擊；

3)利用本方案中漢明重量大于編碼最小距離的錯(cuò)誤向量這種新的思想，嘗試把這種新的思想應(yīng)用于簽名、密鑰交換、密鑰封裝等密碼學(xué)原語中。

4 安全性分析

對基于編碼密碼體制的攻擊，主要有密鑰恢復(fù)攻擊[51]和信息集譯碼攻擊[52]等。

1)密鑰恢復(fù)攻擊。原始McEliece體制采用的是Goppa碼，具有一些隨機(jī)碼的特征。Gpub=SGP，攻擊者只有找到擾亂矩陣S、置換矩陣P，才有可能恢復(fù)出生成矩陣G，最后才能通過Goppa碼的快速譯碼算法解碼密文。假如攻擊者找不到擾亂矩陣S、置換矩陣P，無法恢復(fù)出生成矩陣G，也就無法達(dá)到破譯密文的目的。事實(shí)上，可逆矩陣S、置換矩陣P的碼族非常大，通過找到可逆矩陣S、置換矩陣P這種方法來恢復(fù)生成矩陣G在理論上是不可行的。

3)區(qū)分器攻擊。當(dāng)區(qū)分器攻擊密碼方案時(shí)，區(qū)分器利用公鑰矩陣不具有隨機(jī)性，則將公鑰矩陣和隨機(jī)二進(jìn)制矩陣進(jìn)行區(qū)分。Faugère 等[54]發(fā)現(xiàn)采用的編碼和密碼方案的秩具有一定的相關(guān)性。當(dāng)采用的Goppa碼的碼率接近于1，攻擊者構(gòu)造了一個(gè)Goppa碼區(qū)分器，很容易將隨機(jī)碼和Goppa碼區(qū)分。區(qū)分器攻擊的基本思想就是利用公共碼和隨機(jī)碼的可區(qū)分性，區(qū)分密碼方案所采用的代碼是否為隨機(jī)碼，從而達(dá)到攻擊的目的。

4)側(cè)信道攻擊。側(cè)信道攻擊通過檢測密碼方案實(shí)現(xiàn)過程中的一些物理現(xiàn)象，例如軟件的運(yùn)行時(shí)間或硬件的功耗來分析密碼方案，以達(dá)到攻擊的目的。Strenzke等[55]提出對McEliece公鑰體制的側(cè)信道攻擊，Strenzke指出在解密過程中采用Patterson譯碼算法，時(shí)間功耗攻擊是非常有效的，在密鑰生成時(shí)能量攻擊可以對校驗(yàn)矩陣的構(gòu)造造成極大的破壞。如果編碼的支撐向量已知，則在密鑰生成過程中的奇偶校驗(yàn)矩陣構(gòu)造中，通過分析不可約Goppa多項(xiàng)式的求值所帶來的功耗，可以得到不可約Goppa多項(xiàng)式。對Patterson譯碼算法的定時(shí)攻擊使用了錯(cuò)誤定位多項(xiàng)式的次數(shù)恰好等于接收到單詞中的錯(cuò)誤數(shù)量這一事實(shí)。因此，為了得到明文，可以嘗試請求對偽密碼文本進(jìn)行解密。Shoufan等[56]在文獻(xiàn)[55]分析的基礎(chǔ)上，對原始攻擊做了進(jìn)一步分析。Heyse等[57]分析了解密過程中可逆矩陣和置換矩陣的功耗攻擊。Molter等[58]用所測量的功耗軌跡圖峰值信息取代時(shí)序信息，對時(shí)序分析和錯(cuò)誤注入相結(jié)合的攻擊方法進(jìn)行了研究。Chen等[59]提出一種分析基于編碼的差分攻擊功率的新型方法，該攻擊采用的方法是計(jì)算硬件實(shí)現(xiàn)上選定的基于QC-MDPC碼單密文的特征值。Chen等[60]采用與校驗(yàn)矩陣大小相同的Boolean的方法隱藏信息,進(jìn)一步對密鑰和特征值進(jìn)行優(yōu)化。Santini等[61]研究了基于稀疏對偶校驗(yàn)碼的密碼方案,在采用循環(huán)校驗(yàn)碼的情況下，通過新的側(cè)信道攻擊方法恢復(fù)出比目前已知的其他攻擊更多的信息。

5)其他攻擊。由于McEliece公鑰密碼體制存在延展性[62]，攻擊者可以通過觀察兩個(gè)密文之間的關(guān)聯(lián)性來確定錯(cuò)誤向量。另外一種反應(yīng)攻擊[63]則是對密文加以修改，合法接收方收到修改密文，攻擊者觀察其反應(yīng)。消息在信道傳遞的過程中，攻擊者非法截取密文，然后對截取的密文添加更多的錯(cuò)誤位，如果接收方譯碼失敗，表明修改的錯(cuò)誤位在原來的錯(cuò)誤向量e上。攻擊者利用這種方法，最多重復(fù)k次就能恢復(fù)一個(gè)沒有錯(cuò)誤的信息。

5 展望

目前，基于編碼的體制主要采用兩類具有快速譯碼算法的碼：秩度量碼和漢明度量碼。其存在的共同問題是密鑰尺寸太大，為了減小密鑰尺寸，推動(dòng)基于編碼加密體制的實(shí)用化進(jìn)程，可以從以下幾方面完善密碼體制。

1)密碼體制中編碼理論方面還值得繼續(xù)研究，例如研究碼的結(jié)構(gòu)特征，尋找新的性能更優(yōu)、安全性更強(qiáng)的碼，將編碼理論中的碼應(yīng)用到密碼學(xué)中；改進(jìn)譯碼算法，降低譯碼復(fù)雜度，提高譯碼效率；研究如何構(gòu)造隨機(jī)性更強(qiáng)的公鑰矩陣，使攻擊者不能在公鑰中得到生成矩陣或校驗(yàn)矩陣。

2)嘗試在原有方案的基礎(chǔ)上對結(jié)構(gòu)進(jìn)行改變，減少密鑰長度，提高密碼方案的實(shí)用化。

3)研究基于編碼加密方案的軟硬件實(shí)現(xiàn)，優(yōu)化算法的能耗，提高實(shí)現(xiàn)效率，做好抗量子密碼的實(shí)用化準(zhǔn)備。

4)研究分析目前存在的攻擊的共性，預(yù)測還可能存在的攻擊，針對這些攻擊，設(shè)計(jì)更加完善的密碼方案。

6 結(jié)論

目前，后量子密碼標(biāo)準(zhǔn)化進(jìn)程正穩(wěn)步推進(jìn)，后量子密碼方案已完成第二輪評選，我國也有序推進(jìn)后量子算法標(biāo)準(zhǔn)化進(jìn)程，基于編碼的后量子密碼方案已成為研究的熱點(diǎn)。McEliece密碼方案是很早的基于編碼的方案，具有抗量子計(jì)算的優(yōu)點(diǎn)，在量子計(jì)算機(jī)大規(guī)模投入使用之前，亟待研究基于編碼的密碼方案。后量子密碼評選方案中包括公鑰加密、密鑰封裝、數(shù)字簽名和密鑰交換。本文綜述了基于漢明度量編碼和基于秩度量編碼加密方案的發(fā)展歷程及研究現(xiàn)狀，介紹了基于McEliece方案進(jìn)行結(jié)構(gòu)改變的方案，分析了目前對基于編碼加密方案主流的攻擊類型。由于編碼種類的多樣性，本文僅對典型的編碼進(jìn)行了介紹，還有許多其他類型的編碼沒有進(jìn)行詳細(xì)概述。