李 喆, 韓益亮, 李 魚(yú)

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

密碼學(xué)在社會(huì)生活中的網(wǎng)上金融交易、國(guó)家民主選舉、軍隊(duì)通信指揮等領(lǐng)域發(fā)揮著重要的作用。1994年，Shor[1]提出在多項(xiàng)式時(shí)間內(nèi)解決基于大整數(shù)分解問(wèn)題、基于離散對(duì)數(shù)問(wèn)題的量子算法，RSA[2]、ECC[3]等密碼受到潛在的危險(xiǎn)。因此，許多學(xué)者尋找可以抵御量子計(jì)算機(jī)的新型密碼體制，即抗量子計(jì)算密碼體制(post-quantum cryptography)[4]。美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院(National Institute of Standards and Technology，NIST)面向世界征求抗量子密碼方案，在候選的密碼體制中，大約3/8的密碼體制都是基于編碼的密碼體制[5]。26種候選的密碼方案進(jìn)入第二輪評(píng)選，進(jìn)入第二輪評(píng)選的密碼方案大多都是基于編碼和基于格的[6]，由此可見(jiàn)，基于編碼的密碼體制將是未來(lái)抗量子密碼方案的研究重點(diǎn)。

McEliece等[7]首次提出基于編碼的密碼方案,該方案使用Goppa碼作為原始編碼，到目前仍然是安全的，但密鑰尺寸較大。Niederreiter[8]提出基于GRS碼的Niederreiter密碼體制，該體制相較于McEliece體制，密鑰尺寸有所減小，但距離實(shí)用化還有較大的差距。因此，許多密碼學(xué)者尋求其他結(jié)構(gòu)更為緊湊的編碼以改進(jìn)McEliece體制，通過(guò)換碼改進(jìn)的方案減小了密鑰長(zhǎng)度，但存在安全漏洞，容易受到信息集譯碼等攻擊[9]。于是，又有學(xué)者對(duì)McEliece體制進(jìn)行變形，如Kim等[10]構(gòu)造了McEliece和Niederreiter相結(jié)合的McNie密碼方案，劉相信等[11]構(gòu)造了隱藏明文的漢明重量的密碼方案。Esmaeili[12]采用漢明重量大于編碼最小距離的錯(cuò)誤向量，構(gòu)造了一種滿足IND-CPA安全性的密碼方案。

Mostafa Esmaeili方案[12]沒(méi)有采用置換矩陣和可逆矩陣對(duì)生成矩陣進(jìn)行擾亂，且采用漢明重量大于編碼最小距離的錯(cuò)誤向量，可以抵御目前已知的信息集譯碼攻擊，這種方法與McEliece有著完全不同的區(qū)別，為設(shè)計(jì)基于編碼的抗量子方案提供了一種新的方向。該方案給出了理論框架，并未說(shuō)明采用何種編碼構(gòu)造密碼方案。在Mostafa Esmaeili方案[12]的基礎(chǔ)上，根據(jù)Polar碼在信道中的極化性質(zhì)，采用Polar碼作為改進(jìn)方案選用的編碼，把信息比特作為原方案中的明文，把凍結(jié)比特作為原方案中的隨機(jī)比特串，密鑰尺寸相較于McEliece方案減少70%。在譯碼過(guò)程中直接將凍結(jié)比特丟棄，并且改進(jìn)Polar碼的譯碼算法，提高了譯碼正確率。經(jīng)過(guò)分析，該方案沒(méi)有改變Mostafa Esmaeili方案的結(jié)構(gòu)，仍然采用漢明重量大于編碼最小距離的錯(cuò)誤向量，可以抵御信息集譯碼等攻擊。

1 基礎(chǔ)知識(shí)

Polar碼是目前為止唯一可以在理論上證明無(wú)限接近于香農(nóng)限的編碼。土耳其Arikan[13]提出Polar碼后，近年來(lái)成為研究的熱點(diǎn)，越來(lái)越多的學(xué)者開(kāi)始研究Polar碼的結(jié)構(gòu)及性能[14-15]。Polar碼信道極化現(xiàn)象主要包括信道聯(lián)合和信道分裂兩部分。通過(guò)信道聯(lián)合和信道分裂后，各個(gè)子信道的對(duì)稱容量將呈現(xiàn)兩極分化的趨勢(shì)：隨著碼長(zhǎng)N的增加，出現(xiàn)信道容量趨近于1的無(wú)噪信道和信道容量趨近于0的全噪信道，信道容量趨近于1的無(wú)噪信道用來(lái)傳輸信息比特，信道容量趨近于0的全噪信道用來(lái)傳輸固定比特(凍結(jié)比特)。

1.1 相關(guān)定義

定義1一個(gè)二進(jìn)制輸入離散無(wú)記憶信道(binary input discrete memoryless channel,B-DMC)可以表示為W:X→Y，X是輸入符號(hào)集合，Y是輸出符號(hào)集合，，轉(zhuǎn)移概率為W(y|x)，x∈X，y∈Y。對(duì)信道W的N次極化后的信道可以表示為WN，則信道WN:XN→YN的轉(zhuǎn)移概率為

(1)

對(duì)于一個(gè)B-DMC，有兩個(gè)重要的信道容量參數(shù)。

(1)對(duì)稱容量

(2)

(2)巴氏參數(shù)

(3)

式中：I(W)是對(duì)信道速率的度量；Z(W)是對(duì)信道可靠性的度量。信道W在等概率輸入情況下，可靠傳輸時(shí)的最大速率為I(W)；而信道W在只傳輸0或1的情況下，最大似然判決錯(cuò)誤概率的上限為Z(W)。

I(W)與Z(W)的取值范圍均為[0,1]。由于對(duì)數(shù)以2為底，因此碼率和信道容量的單位為bit。I(W)與Z(W)滿足這樣的關(guān)系：當(dāng)且僅當(dāng)Z(W)≈0時(shí)，I(W)≈1；當(dāng)且僅當(dāng)Z(W)≈1時(shí)，I(W)≈0。

定義2信道極化。

信道極化分為兩個(gè)階段：信道聯(lián)合階段和信道分裂階段。

信道WN和WN的轉(zhuǎn)移概率有如下關(guān)系：

(4)

(5)

定義3信道極化定理。

定義4極化碼編碼原理。

極化編碼步驟如下。

(1)極化信道可靠性估計(jì)：

(6)

(7)

BN=RN(I2?BN/2)

(8)

式(8)中：I2為2維單位矩陣，B2=I2；RN為置換矩陣，用來(lái)分離輸入序列中的奇序元素和偶序元素，即先對(duì)奇序元素排列，再對(duì)偶序元素排列，例如：

(u1,u2,u3,u4，…，uN)RN=

(u1,u3,u5,uN-1,u2,u4,u6,uN)

(9)

1.2 Mostafa Esmaeili方案

Mostafa Esmaeili方案是Mostafa Esmaeili2019年在其博士論文中提出的，該方案的主要?jiǎng)?chuàng)新點(diǎn)是在McEliece加密方案的基礎(chǔ)上，對(duì)McEliece方案的結(jié)構(gòu)進(jìn)行變形，利用漢明重量大于編碼最小距離的錯(cuò)誤向量的思想構(gòu)造的密碼方案[12]。該密碼方案與McEliece方案構(gòu)造過(guò)程類似，但是沒(méi)有利用可逆矩陣和置換矩陣對(duì)生成矩陣進(jìn)行擾亂，主要包括密鑰生成(公鑰、私鑰)，加密過(guò)程，解密過(guò)程三個(gè)部分。

1.2.1 密鑰生成

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

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

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

公鑰：[G，S(H-1)T]，私鑰：HTS-1。

1.2.2 加密過(guò)程

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

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

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

(10)

1.2.3 解密過(guò)程

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

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

(11)

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

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

(12)

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

1.3 SC(successive cancellation)譯碼算法

首先定義對(duì)數(shù)似然比(log-likelihood ratio，LLR):

(13)

因此,進(jìn)行SC譯碼時(shí)，對(duì)于凍結(jié)比特可以直接對(duì)其進(jìn)行判決:

(14)

即當(dāng)i∈AC時(shí)，表明該比特為凍結(jié)比特，即收發(fā)方事先約定好的比特，直接對(duì)凍結(jié)比特估計(jì)值賦值i∈AC。而當(dāng)i∈A，表明該比特是信息比特，判決函數(shù)為

(15)

i為奇數(shù)時(shí):

(16)

i為偶數(shù)時(shí):

(17)

SC譯碼算法步驟如下。

(18)

(19)

(3)進(jìn)行判決:

(20)

(21)

返回(2)進(jìn)行下一比特的譯碼，直到該碼字全部譯碼完畢。

2 基于Polar碼改進(jìn)的抗量子密碼方案

本文方案在Mostafa Esmaeili方案的基礎(chǔ)上，并不改變?cè)桨傅男问剑饕肞olar碼的極化性質(zhì)，經(jīng)過(guò)信道極化后，Polar碼極化為有用的信息比特和無(wú)用的凍結(jié)比特，把信息比特作為明文，把凍結(jié)比特作為隨機(jī)比特串，在譯碼過(guò)程中，直接將凍結(jié)比特丟棄，并對(duì)SC譯碼算法進(jìn)行改進(jìn)。本文方案主要包括密鑰生成(公鑰、私鑰)，加密過(guò)程，解密過(guò)程三個(gè)部分。

2.1 密鑰生成

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

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

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

公鑰pk=[G，S(H-1)T]，私鑰sk=HTS-1。

2.2 加密過(guò)程

根據(jù)Polar碼的極化性質(zhì)，發(fā)送者將極化后的信息比特uA作為明文m，凍結(jié)比特uAC作為隨機(jī)比特串r，將凍結(jié)比特uAC與信息比特uA并列，得到[uAC|uA]。隨機(jī)選擇n-k位的向量s，計(jì)算sS(H-1)T，假如漢明重量的值wt[sS(H-1)T]

c=[uAC|uA]G+sS(H-1)T

(22)

2.3 解密過(guò)程

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

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

(23)

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

[uAC|uA]G=c+sS(H-1)T

(24)

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

改進(jìn)的譯碼算法步驟如下。

3 安全性分析

基于編碼的密碼方案的攻擊，主要有密鑰恢復(fù)攻擊[17]和信息集譯碼攻擊[18]兩種類型的攻擊。密鑰恢復(fù)攻擊的思想是通過(guò)公鑰直接恢復(fù)私鑰。信息集譯碼攻擊通過(guò)密文恢復(fù)明文。

3.1 密鑰恢復(fù)攻擊

密鑰恢復(fù)攻擊是通過(guò)公鑰恢復(fù)出私鑰，即從S(H-1)T恢復(fù)出私鑰HTS-1。

S(H-1)THTS-1=In-k

(25)

攻擊者找到私鑰的概率為2k(n-k)。參數(shù)n和k在合理的選擇范圍下，本文方案可以抵御密鑰恢復(fù)攻擊。2018年，Drǎgoi等[19]針對(duì)基于Polar碼的McEliece方案采用平方碼技術(shù)進(jìn)行密鑰恢復(fù)攻擊，本文方案中生成矩陣G是公開(kāi)的，并沒(méi)有像McEliece密碼方案中采用可逆矩陣S和置換矩陣P對(duì)生成矩陣G進(jìn)行隱藏，并不存在文獻(xiàn)[19]攻擊的情況，所以Drǎgoi等[19]提出的針對(duì)基于Polar碼的密鑰恢復(fù)攻擊對(duì)本方案是無(wú)效的。

3.2 譯碼攻擊

譯碼攻擊通過(guò)尋找加密明文時(shí)的錯(cuò)誤向量從而對(duì)密碼方案進(jìn)行攻擊。譯碼攻擊需要的工作因子小于密鑰恢復(fù)攻擊，所以通常情況下，攻擊者采用譯碼攻擊比采用密鑰恢復(fù)攻擊更有效。當(dāng)錯(cuò)誤向量的漢明重量小于編碼的最小距離，攻擊者采取譯碼攻擊才有效，通過(guò)隨機(jī)向量s乘以公鑰S(H-1)T作為錯(cuò)誤向量，假如錯(cuò)誤向量sS(H-1)T的漢明重量小于編碼的最小距離，則重新選擇隨機(jī)向量s，這樣保證了采用的錯(cuò)誤向量sS(H-1)T的漢明重量大于編碼的最小距離，目前已知的譯碼攻擊都是基于錯(cuò)誤向量的漢明重量小于編碼最小距離的情況，所以本文選擇的錯(cuò)誤向量，譯碼攻擊是無(wú)效的。

3.3 信息集譯碼攻擊

信息集譯碼攻擊一般是通過(guò)在接收端給定編碼中的擴(kuò)展集搜索最小重量的編碼來(lái)尋找密文中的錯(cuò)誤向量。信息集譯碼攻擊采用MMT譯碼算法[20]，所需要的工作因子為

(26)

信息集譯碼攻擊試圖找到與明文對(duì)應(yīng)的k個(gè)無(wú)錯(cuò)誤的密文位，即隨機(jī)錯(cuò)誤向量可以用糾錯(cuò)方法消除。本文所采用的錯(cuò)誤向量的漢明重量大于編碼的最小距離，所以通過(guò)糾錯(cuò)的方法不能消除本文方案中的錯(cuò)誤向量。目前為止，信息集譯碼算法都是在錯(cuò)誤向量的漢明重量小于編碼最小距離的情況下攻擊的，還沒(méi)有已知有效的攻擊算法在錯(cuò)誤向量的漢明重量大于編碼最小距離情況下找到k個(gè)無(wú)誤差位。因此，本文方案可以抵抗信息集譯碼攻擊。

4 性能分析

4.1 復(fù)雜度分析

計(jì)算復(fù)雜度主要包括兩個(gè)部分：加密復(fù)雜度CEnc和解密復(fù)雜度CDec。

4.1.1 加密過(guò)程

c=[uAC|uA]G+sS(H-1)T

加密的復(fù)雜性主要取決于矩陣乘法和錯(cuò)誤向量。

所以加密復(fù)雜度:

CEnc=Cmul([uAC|uA]G)+Cadd[sS(H-1)T]

(27)

Cmul([uAC|uA]G)=O(k×n)

(28)

Cadd[sS(H-1)T]=O[(n-k)×n]

(29)

CEnc=Cmul([uAC|uA]G)+Cadd[sS(H-1)T]≈

O(k×n)

(30)

4.1.2 解密過(guò)程

(1)所采用的延遲譯碼算法，對(duì)于每個(gè)節(jié)點(diǎn)都采取延時(shí)判決，采用后一節(jié)點(diǎn)的判決結(jié)果來(lái)代替當(dāng)前節(jié)點(diǎn)的判決，提高當(dāng)前節(jié)點(diǎn)正確判決的概率。

(2)假設(shè)第一個(gè)信息比特之前有L1個(gè)凍結(jié)比特，后面有L2個(gè)凍結(jié)比特，即L1+L2=n-k。改進(jìn)后的延時(shí)判決譯碼算法，需要計(jì)算的節(jié)點(diǎn)數(shù)L=4k+L1+2L2-1，算法復(fù)雜度為O[2nlgn-(n-1)]。

(3)改進(jìn)后的延時(shí)譯碼算法復(fù)雜度雖然比原來(lái)的SC譯碼算法略有提高，但是相較于原來(lái)的譯碼算法，譯碼正確率大大提高。

cHTS-1=([uAC|uA]G+sS(H-1)T)HTS-1=

s[uAC|uA]G=c+sS(H-1)T[uAC|uA]=

Dc[c+sS(H-1)T]

(31)

解密的復(fù)雜性主要取決于譯碼算法和cHTS-1:

所以解密復(fù)雜度

CDec=Cmul(cHTS-1)+CSC[c+sS(H-1)T](32)

Cmul(cHTS-1)=O[n(n-k)]

(33)

CSC([uAC|uA]G)=CSC[c+sS(H-1)T]=

O[2nlgn-(n-1)]

(34)

CDec=Cmul(cHTS-1)+CSC([uAC|uA]G)≈

O[n(n-k)]

(35)

4.2 密鑰尺寸分析

本文方案的公鑰為[G，S(H-1)T]，私鑰為HTS-1。

公鑰量：

Mpk=kn+(n-k)n=n2

(36)

私鑰量：

Msk=n(n-k)

(37)

密鑰量：

M=Mpk+Msk=

kn+(n-k)n+n(n-k)=n(2n-k)

(38)

McEliece方案的公鑰為Gpub(其中Gpub=SGP)，私鑰為(S,G,P)。

公鑰量：

(39)

私鑰量：

(40)

密鑰量：

(41)

將本文方案與McEliece方案進(jìn)行對(duì)比：

(1)將本文方案的公鑰量與McEliece方案的公鑰量比值定義為

(42)

(2)將本文方案的私鑰量與McEliece方案的私鑰量比值定義為

(43)

(3)將本文方案的密鑰量與McEliece方案的密鑰量比值定義為

(44)

本文方案與McEliece方案進(jìn)行對(duì)比如下。

(1)公鑰量：根據(jù)表1，當(dāng)本文方案和McEliece方案都選用Polar碼，本文方案的公鑰尺寸比McEliece方案略大；根據(jù)表3，當(dāng)本文方案采用Polar碼，McEliece方案采用Goppa碼，本文方案的公鑰尺寸約是McEliece方案的2倍。

(2)私鑰量：根據(jù)表1，當(dāng)本文方案和McEliece方案都選用Polar碼時(shí)，本文方案的私鑰尺寸減小為McEliece方案的4%；根據(jù)表2，當(dāng)本文方案和McEliece方案選用碼率越高的Polar碼，減小私鑰尺寸效果越明顯；根據(jù)表3，當(dāng)本文方案采用Polar碼時(shí)，McEliece方案采用Goppa碼時(shí)，本文方案的私鑰尺寸減少為McEliece方案的5.7%。

(3)密鑰量：根據(jù)表1，當(dāng)本文方案和McEliece方案都選用Polar碼時(shí)，本文方案的密鑰尺寸減少為McEliece方案的30%；根據(jù)表2，當(dāng)本文方案和McEliece方案選用Polar碼時(shí)，碼率越高，減小密鑰尺寸效果越明顯，選參數(shù)為(1 024,921)時(shí)，密鑰尺寸減少約70%，當(dāng)R≈1時(shí)，理論上，可以減少約75%；根據(jù)表3，當(dāng)本文方案采用Polar碼，McEliece方案采用Goppa碼，本文方案的密鑰尺寸減少為McEliece方案的48%。

方案的公鑰量比McEliece方案的公鑰量略大，但私鑰量遠(yuǎn)遠(yuǎn)小于McEliece方案的私鑰量，重要的是，本文方案整體的密鑰量(公鑰量，私鑰量)遠(yuǎn)小于McEliece方案的密鑰量。

本文選用參數(shù)為(1 024,921)的Polar碼，密鑰量與McEliece方案相比，減少約70%。

表1 基于Polar碼的本文方案與McEliece方案對(duì)比

表2 基于Polar碼的本文方案與McEliece方案在不同參數(shù)的對(duì)比

表3 基于Polar碼的本文方案與基于Goppa碼的McEliece對(duì)比

5 結(jié)論

證明了選用碼率高的Polar碼，將有效減小密鑰存儲(chǔ)空間；方案中采用了漢明重量大于編碼最小距離的錯(cuò)誤向量，使其能抵抗信息集譯碼攻擊。下一步可以尋找威脅本方案安全性的其他類型的攻擊。

Mostafa Esmaeili的方案目前只是對(duì)消息進(jìn)行加密，在將來(lái)的工作中，可以嘗試在數(shù)字簽名，密 鑰交換，密鑰封裝等方面進(jìn)一步研究，將方案的新思想應(yīng)用于其他密碼學(xué)原語(yǔ)。

在Mostafa Esmaeili方案基礎(chǔ)上，利用Polar碼的極化性質(zhì)和Mostafa Esmaeili方案的特殊結(jié)構(gòu)，提出了基于Polar碼的抗量子密碼方案，并改進(jìn)了譯碼算法，提高了譯碼正確率。在合理的參數(shù)選擇下，該方案私鑰尺寸和整體的密鑰尺寸相較于McEliece方案大大減小，整體的密鑰尺寸減少了約70%，促進(jìn)了密碼方案的實(shí)用化。本方案沒(méi)有改變Mostafa Esmaeili方案的結(jié)構(gòu)，依然采用漢明重量大于編碼最小距離的錯(cuò)誤向量，可以抵抗目前存在的信息集譯碼等攻擊，達(dá)到IND-CPA安全。選用的Polar碼正是華為5G控制信道技術(shù)使用的編碼，利用Polar碼構(gòu)造密碼方案，將是未來(lái)5G時(shí)代研究的熱點(diǎn)。