基于Polar碼改進的抗量子密碼方案

李 喆, 韓益亮, 李 魚

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

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

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

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

1 基礎知識

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

1.1 相關定義

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

(1)

對于一個B-DMC，有兩個重要的信道容量參數。

(1)對稱容量

(2)

(2)巴氏參數

(3)

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

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

定義2信道極化。

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

信道WN和WN的轉移概率有如下關系：

(4)

(5)

定義3信道極化定理。

定義4極化碼編碼原理。

極化編碼步驟如下。

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

(6)

(7)

BN=RN(I2?BN/2)

(8)

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

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

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

(9)

1.2 Mostafa Esmaeili方案

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

1.2.1 密鑰生成

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

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

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

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

1.2.2 加密過程

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

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

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

(10)

1.2.3 解密過程

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

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

(11)

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

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

(12)

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

1.3 SC(successive cancellation)譯碼算法

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

(13)

因此,進行SC譯碼時，對于凍結比特可以直接對其進行判決:

(14)

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

(15)

i為奇數時:

(16)

i為偶數時:

(17)

SC譯碼算法步驟如下。

(18)

(19)

(3)進行判決:

(20)

(21)

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

2 基于Polar碼改進的抗量子密碼方案

本文方案在Mostafa Esmaeili方案的基礎上，并不改變原方案的形式，主要利用Polar碼的極化性質，經過信道極化后，Polar碼極化為有用的信息比特和無用的凍結比特，把信息比特作為明文，把凍結比特作為隨機比特串，在譯碼過程中，直接將凍結比特丟棄，并對SC譯碼算法進行改進。本文方案主要包括密鑰生成(公鑰、私鑰)，加密過程，解密過程三個部分。

2.1 密鑰生成

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

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

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

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

2.2 加密過程

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

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

(22)

2.3 解密過程

接收者收到密文c后，使用自己的私鑰對密文進行解密:

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

(23)

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

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

(24)

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

改進的譯碼算法步驟如下。

3 安全性分析

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

3.1 密鑰恢復攻擊

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

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

(25)

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

3.2 譯碼攻擊

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

3.3 信息集譯碼攻擊

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

(26)

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

4 性能分析

4.1 復雜度分析

計算復雜度主要包括兩個部分：加密復雜度CEnc和解密復雜度CDec。

4.1.1 加密過程

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

加密的復雜性主要取決于矩陣乘法和錯誤向量。

所以加密復雜度:

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 解密過程

(1)所采用的延遲譯碼算法，對于每個節(jié)點都采取延時判決，采用后一節(jié)點的判決結果來代替當前節(jié)點的判決，提高當前節(jié)點正確判決的概率。

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

(3)改進后的延時譯碼算法復雜度雖然比原來的SC譯碼算法略有提高，但是相較于原來的譯碼算法，譯碼正確率大大提高。

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)

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

所以解密復雜度

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方案進行對比：

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

(42)

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

(43)

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

(44)

本文方案與McEliece方案進行對比如下。

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

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

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

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

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

表1 基于Polar碼的本文方案與McEliece方案對比

表2 基于Polar碼的本文方案與McEliece方案在不同參數的對比

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

5 結論

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

Mostafa Esmaeili的方案目前只是對消息進行加密，在將來的工作中，可以嘗試在數字簽名，密 鑰交換，密鑰封裝等方面進一步研究，將方案的新思想應用于其他密碼學原語。

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