基于Polar碼改進的RLCE公鑰加密方案

李喆，韓益亮,2，李魚

（1.武警工程大學密碼工程學院，陜西 西安 710086；2.武警部隊密碼與信息安全保密重點實驗室，陜西 西安 710086）

1 引言

量子計算機技術的飛速發展，將深刻影響當前和未來的社會。銀行交易、無人駕駛、保密通信等與人們息息相關的各方面的安全性依賴于密碼學。Shor[1]提出的量子算法，極大影響了基于大整數分解困難問題的RSA等[2]公鑰密碼方案；Grover[3]提出的量子算法，極大影響了AES等[4]對稱密碼方案。Shor算法和Grover算法的提出給經典密碼方案的安全性帶來嚴峻的挑戰。

為了應對量子計算機對基于經典數學困難問題的密碼方案的威脅，各國紛紛尋求能夠抵抗量子計算機攻擊的新型密碼方案，即后量子密碼或抗量子密碼（PQC，post-quantum cryptography）。美國NIST（National Institute of Standards and Technology）在2012年啟動后量子算法的標準化項目，2016年面向全球征集后量子密碼算法，2019年征集算法完成第二輪遴選[5]。歐洲電信標準化協會（ETSI，European Telecommunications Standards Institute）開展量子安全會議以此推動后量子密碼算法的征集工作，逐步推進全球后量子密碼算法項目PQCRYPTO和后量子密碼算法應用項目SAFCRYPT[6]。在以上各國或地區制定后量子密碼算法標準的同時，我國也同步推進后量子密碼算法設計競賽活動，制定后量子算法標準，截至2019年，后量子密碼標準化已進入第二輪評選。后量子密碼方案主要包括5種[7]，5種密碼方案各有其獨特的應用范圍。目前，基于編碼的方案和基于格的方案成為研究的熱點。基于編碼的密碼方案相較于其他類型的后量子密碼方案，更適合構造加密方案，在后量子密碼加密方案中，基于編碼的加密方案具有良好的研究前景。

基于編碼的密碼方案最早可追溯到1978年的McEliece方案[8]，該方案最初使用Goppa碼作為底層編碼，該方案在適當的參數選擇下仍然是安全的，并進入PQC第二輪征集算法。基于Goppa碼的McEliece方案的安全性是基于一般線性碼的譯碼困難問題，可以規約到NPC（nondeterministic polynomial complete）問題，具有抵抗量子計算機攻擊的特點，眾多密碼學者開始研究此方案。1986年，Niederreiter[9]利用McEliece方案的對偶形式構造了一種加密方案，即Niederreiter方案。McEliece方案和Niederreiter方案均存在密鑰尺寸過大的缺點，在實際場景中難以應用。針對McEliece方案實用化差的特點，密碼學者通過利用其他結構更加緊湊的編碼作為底層編碼以減小密鑰尺寸，然而構造的變形方案存在安全性問題，易受到結構化攻擊[10]。如何在保證密碼方案安全性的基礎上，同時構造較小密鑰尺寸的密碼方案成為基于編碼的密碼方案亟待解決的問題。

2016年，Wang[11]通過在生成矩陣的每一列中插入隨機列構造了線性隨機碼公鑰加密（RLCE，random linear code encryption）方案，該方案進入PQC第一輪征集算法評選。不同于其他利用結構緊湊的編碼的密碼方案，該方案不依賴于任何底層編碼的結構。RLCE方案通過插入隨機列使方案達到隨機性，同時方案的安全性依賴于線性隨機碼譯碼的NPC問題，避免了因底層編碼結構引入的結構化攻擊。2017年，Wang[12]針對RLCE方案存在的潛在攻擊，進一步研究RLCE方案的填充方法，改進后的RLCE方案減小了密鑰尺寸，提高了加解密性能，達到了IND-CCA2安全性。Matthews[13]在2019年CBC（Code-Based Cryptography）會議上提出用Hermitian（埃爾米特）碼作為RLCE方案的底層編碼，在128 bit安全級別和256 bit安全級別的情況下，相較于GRSRLCE加密方案、HermitianRLCE加密方案的公鑰尺寸分別減少了80%、72%。Liu等[14]在2019年A2C（Algebra,Codes and Cryptology）會議上提出利用Polar碼作為RLCE方案的底層編碼，通過利用Polar碼的極化性質，降低了加解密復雜度，在正確參數選擇下，可以達到預期的安全級別，同時密鑰尺寸保持在合理的范圍內。然而，Liu在文獻[14]提出的方案沒有考慮語義安全，易受到自適應選擇密文攻擊。

本文在RLCE方案和PolarRLCE方案的基礎上，利用Polar碼的極化性質，通過RLCEspad消息填充，提出一種具有IND-CCA2安全的基于Polar碼改進的RLCE公鑰加密方案。改進的方案利用Arikan[15]提出的Polar碼作為底層編碼，在信息比特列中插入隨機列，選擇隨機非奇異矩陣對隨機列進行混合，選擇等價類較多的置換矩陣對生成矩陣進行擾亂，利用消息填充的方法，使用普通編碼對密文進行編碼。改進后的方案沒有改變RLCE方案的結構，仍然具有隨機性，可以抵抗McEliece方案存在的結構化攻擊。此外，本文采用系統矩陣的形式，對部分私鑰進行預計算，減少了密鑰存儲空間。

2 基礎知識

2.1 Polar碼編碼理論

根據Shannon闡述的信道容量概念，Polar碼是至今唯一可以在理論上證明達到這一容量的編碼。Polar碼具有良好的性能，加解密復雜度低，計算復雜度為O(nlogn)。Polar碼由于其獨特的極化性質、較低的加解密復雜度，成為眾多通信領域學者和密碼領域學者研究的焦點。目前，利用Polar碼在物理層的極化性質，許多學者在信息安全保密領域取得突破[16]。華為利用Polar碼信道容量大、傳輸速率高、安全性強的優點，將Polar碼作為5G時代無線通信的編碼[17]。

Polar碼相較于Goppa碼具有更好的糾錯能力，較低的加解密復雜度，較多的等價類碼族。擁有以上優點的Polar碼應用到編碼密碼方案中，將具有合理的密鑰尺寸，更加適合構造基于Polar碼的加密方案，基于Polar碼的加密方案具有良好的應用前景。Shrestha等[18]將Polar碼應用到密碼方案中。隨著Polar碼理論的進一步發展，Hooshmand等[19]進一步研究Polar碼在密碼方案中的應用，完善基于Polar碼的密碼方案。

定義1對稱信道

Polar碼可以實現任何二進制輸入的離散無記憶性信道的（B-DMC，binary input discrete memoryless channel）容量，如二進制擦除信道（BEC）和二進制對稱信道（BSC）。下面闡述二進制對稱信道相關定義。定義X是輸入符號集，Y是輸出符號集，轉移概率為W(y|x)，x∈X，y∈Y。信道W經過N次極化后，信道可以表示為WN，則信道WN：XN→YN的轉移概率為

關于B-DMC的性能，可以通過兩個參數進行評價：對稱容量I(W)和巴氏參數Z(W)。下面對兩個參數相關定義進行闡述。

（1）對稱容量（symmetric capacity）

（2）巴氏參數（Bhattacharyya parameter）

I(W)∈[0,1]用于評估信道速率，Z(W)∈[0,1]用于評估信道可靠性。I(W)與Z(W)具有如下的關系：當且僅當Z(W)≈0時，I(W)≈1；當且僅當Z(W)≈1時，I(W)≈0。

定義2信道極化

信道極化分為兩個階段：信道融合階段（channel combining）和信道分化（channel splitting）階段。

（1）信道融合階段描述

步驟1WN:XN→YN，N為2的n次冪N=2n，n≥0。其中，X表示輸入符號集合，Y表示輸出符號集合，WN表示信道W的N次使用后的信道。

步驟2YN，u1N∈XN,GN為N維生成矩陣,N=2n。其中，為原始比特輸入序列；為通過生成矩陣編碼后的比特序列。

（2）信道分化階段描述

步驟1將信道融合構成的復合信道WN分裂為N個二進制輸入的坐標信道。如下所示。

步驟2。

定義3極化碼編碼

圖1 極化編碼步驟Figure 1 Polar coding steps

（1）極化信道可靠性估計

（2）比特混合

可靠性較高的K個分裂子信道傳輸信息比特序列，而可靠性較低的分裂子信道傳輸凍結比特。通過比特混合后，輸出的比特為編碼的最初比特。對于BEC來說，選擇巴氏參數最小的K個子信道傳輸信息比特。

（3）構造生成矩陣

首先定義Kronecker 矩陣乘法為

定義矩陣F為，則生成矩陣，其中表示對矩陣F的n次克羅內克積，。BN是比特反轉排序矩陣，用來對比特重排操作。BN的遞歸式定義為

其中，I2為2維單位矩陣，B2=I2；RN為置換矩陣，用來分離輸入序列中的奇偶元素。

2.2 RLCE加密方案

（1）RLCE密鑰生成過程如算法1所示。

算法1RLCE密鑰生成

輸入(n,k,d,t,w),n,k,d,t>0，w∈{1,2,…,n},k+1≥d≥2t+1。

輸出公鑰Gpub，私鑰(S,G1,P,A)。

1)選擇長度為n，維度為k的k×n生成矩陣G。

2)隨機選擇w個k×1的列向量r1,r2,…,rw，將w個列向量隨機插入生成矩陣G中，得到k×(n+w)的生成矩陣G1，G1=(g1,…,gn-w,gn-w+1,r1,…gn,rw)。

3)為了混合選擇的列，選擇w個2×2隨機非奇異矩陣A1,A2,…,AW。

4)定義A=[1,…1,A1,A2,…,AW]是(n+w)×(n+w)的非奇異矩陣。

5)S為k×k的非奇異矩陣，P為(n+)w×(n+w)的置換矩陣。

6)輸出k×(n+w)的公鑰，私鑰(S,G1,A,P)。

（2）RLCE加密過程如算法2所示。

算法2RLCE加密

輸入公鑰Gpub，明文，隨機錯誤向量。

輸出密文。

（3）RLCE解密過程如算法3所示。

算法3RLCE解密

輸入密文，私鑰(S,G1,A,P)。

輸出明文，譯碼錯誤標識⊥。

2)從長度為n+w的向量中刪除w個列向量，得到長度為n的c′=(c1′,c2′,…,cn′-w+1,cn′-w+3,cn′-w+5,…,cn′+w-1)。

3)c′=。

4)利用譯碼算法，計算m′=mS，m=m′S-1。

5)計算漢明重量w=wt(c-mG1)，假如w≤t，輸出明文m；否則，輸出⊥。

2.3 信息編碼

為了抵抗編碼密碼方案存在的已知攻擊，可以通過消息編碼（消息填充）的方法保證密碼方案的安全性。通常，在密文中有3種方法可以對消息進行編碼[12]。

（1）基本編碼（basic encoding）

（2）普通編碼（medium encoding）

除了基本編碼之外，更多的消息被編碼在e的非零項中。在這種情況下，可以在每個密文中編碼長度為mLen=m(k+t)位信息。嚴格地說，因為，編碼信息小于m(k+t)位。

（3）高級編碼（advanced encoding）

除了普通編碼，更多的消息被編碼在e的非零項中。非零e共有種可能，在這種情況下，可以在每個密文中編碼長度為mLen=的信息。

接下來概述常見的5種消息填充類型。

1)Pointcheval padding[20]

2)Fujisak-Okamato padding[21]

3)Kobara-Imai′sα-padding[22]

4)Kobara-Imai′sβ-padding

5)Kobara-Imai’sγ-padding

其中，H1、H2是隨機諭言機模型（也可以是偽隨機位生成器或者哈希函數）輸出固定長度的偽隨機比特串；1r、2r是隨機選擇的適當長度的比特串。

3 本文的加密方案

3.1 改進的RLCE公鑰加密方案

本文提出的基于Polar碼改進的RLCE公鑰加密方案是在Wang提出的RLCE方案和Liu提出的基于Polar碼的RLCE方案的基礎上，針對Liu提出的PolarRLCE方案密鑰尺寸較大且不具有IND-CCA2安全的缺點，提出的一種改進方案。本文利用Polar碼的極化性質和譯碼復雜度低的優點，將Polar碼作為RLCE方案的底層編碼，改進后的方案采用Wang的RLCE方案的結構，沒有改變RLCE方案的具體形式。將Wang的RLCE方案的IND-CCA2形式化安全證明應用到Liu的基于Polar碼的編碼方案中，對PolarRLCE方案進行消息填充，對每個密文進行語義安全普通編碼，并將公鑰矩陣轉化為系統矩陣，對部分私鑰采用預計算[23]，以減少密鑰存儲空間。本文方案和RLCE方案類似，包括密鑰生成（polarRLCE.KeySetup）、加密（polarRLCE.Enc）、解密（polarRLCE.Dec）。

（1）密鑰生成

密鑰生成過程如下。

1)參數選擇：(n,k,d,t,w),n,k,d,t>0，w∈{1,2…,n},k+1≥d≥2t+1。

2)G：長度為n，維度為k的Polar碼的k×n生成矩陣，譯碼算法可以糾出至少t個錯誤。

3)G1：長度為n+w，維度為k的Polar碼的k×(n+w)的生成矩陣，可以將隨機選擇的w個k×1的列向量r1,r2,…,rw隨機插入生成矩陣G得到G1=(g1,…,gn-w,gn-w+1,r1,…gn,rw)。

4)A：(n+w)×(n+w)的非奇異矩陣

5)S：k×k階的非奇異矩陣。

6)P：(n+w)×(n+w)階的置換矩陣。

7)Gpub：k×(n+w)的公鑰Gpub=SG1AP。

公鑰Gpub=SG1AP，私鑰 (S,G1,A,P)。

（2）加密

發送方對明文進行加密過程如下。

2)發送方利用接收方的公鑰pubG對明文m進行加密，得到密文。

（3）解密

接收方對密文進行解密過程如下。

1)接收方收到密文c，利用自己的私鑰，對密文c右乘P-1A-1，得到

2)接收方從長度為n+w的向量(c1′,c2′,…)中刪除w個凍結比特列，得到長度為n的向量，c′=（其中，e′=eP-1A-1），此時的wH(e′)≤t。

3)接收方利用Polar碼的SC譯碼算法，對c′進行譯碼，得到明文m。

4)接收方計算漢明重量wt=wt(c-mG1)，假如wt≤t，輸出明文m；否則，輸出⊥。

3.2 將公鑰矩陣轉換為系統矩陣

令mSG1=(d1,…dn)，=(d1,d2,…,⊥,…,dn,)P是長度為n+w的向量。

對于每個i＜k，當j＜n-w，di′=dj，令mi=dj，當m=(m1,…mk)。

IR={i:mi}（mi譯碼成功）；={1,…,k}IR（im譯碼失敗）。

P為置換矩陣，恢復出在mP中前k-u個mi(i∈IR)信息。通過式(15)計算得到

其中，mIR是在IR帶有索引的消息列表。

可以預計算W-1。

通過將公鑰矩陣轉換為系統矩陣，可以把V,W-1作為私鑰存儲，不再存儲私鑰S，以降低密鑰存儲空間。

3.3 消息填充

Liu提出的PolarRLCE方案不具有IND-CCA2安全，本文采用Wang提出的適合加密較短信息的RLCEspad消息填充的方法，使改進的方案達到IND-CCA2安全。對信息進行填充后，信息轉化為RLCE方案中的信息位或其他信息，采用普通編碼，填充的信息可以被編碼在e的非零項中。

首先明確相關變量定義RLCEspad (mLen,k1,k2,k3,t,m,r)

（2）H1,H2,H3是隨機諭言機模型，可以分別將任意長度的二進制比特串轉化為長度為k2，k1+k2，k3字節的輸出比特串。

（3）m∈{0,1}8k1是需要填充的信息，當r1∈是隨機選擇的二進制比特串。

RLCE填充過程如算法4所示。

算法4 RLCEspad

輸入mLen,t,m,r,H1,H2,H3。

輸出(y1,e1),c。

1)計算v=8(k1+k2+k3)-mLen。

4)將y轉化為(y1,e1)∈，輸出(y1,e1)，得到密文c=y1G+e。

4 安全性分析

（1）窮舉攻擊

窮舉攻擊是通過一一窮舉可能存在的正確私鑰，從而恢復明文，達到攻擊密碼方案的目的。通過采取系統矩陣的形式，改進后的私鑰為(V,W-1,G1,A,P)。本文采用Polar碼作為方案的底層編碼，其置換矩陣P等價類碼族較多，攻擊者通過窮舉攻擊難以在多項式時間內找到正確的P，對密文難以進行操作，，無法恢復出正確的明文。此外，根據Liu方案選擇的參數，攻擊者通過窮舉的方法找到其他4類密鑰也是不可行的。所以，窮舉攻擊不會對本文方案的安全性造成影響。

（2）密鑰恢復攻擊

密鑰恢復攻擊的基本思想是：從公鑰Gpub恢復出正確的私鑰。密鑰恢復攻擊是一種結構攻擊，通常是針對特定的編碼，如QC-LDPC碼、GRS碼等。本文提出的方案插入了隨機列，同時采用2×2隨機非奇異矩陣A對插入的隨機列進行混合，私鑰的結構被打亂。混合之后又隨機從長度為n+w密文中刪除w列凍結比特列，由于攻擊者無法知道Polar碼的極化性質，進一步增加了私鑰結構的復雜度，攻擊者在多項式時間內通過公鑰難以恢復出正確的私鑰結構。Bardet等[24]針對Polar碼提出一種確定最小權重的攻擊，解決了極化碼相對于遞減單項式碼的等價問題。本文方案插入的隨機列擾亂了生成矩陣的原有編碼結構，所以文獻[24]不會影響本文方案的安全性。因為Polar碼的結構與漢明循環碼、GRS碼和RM碼結構不同，針對底層編碼為循環碼、GRS碼和RM碼的結構化攻擊，不會威脅本文方案的安全性。

（3）信息集譯碼攻擊

信息集譯碼攻擊是對McEliece編碼方案最有效的攻擊，在所有已知的攻擊中，基于信息集譯碼的攻擊擁有最低的計算復雜度。Stern[25]首先提出對McEliece方案的信息集譯碼攻擊，此后，攻擊者為了提高對編碼方案攻擊的有效性，提出許多改進的高效率的信息集譯碼攻擊[26]。信息集譯碼攻擊不是利用編碼的底層結構對密碼方案進行攻擊的，而是利用搜索信息集的方法達到攻擊的目的。此外，信息集譯碼攻擊的工作因子隨錯誤向量的增加而增加。對于RLCE方案，信息集譯碼攻擊尋找的是公鑰Gpub的列數，而不是私鑰G1的列數。從含有t個錯誤的n+w位密文中隨機選擇k位，構成xk，從錯誤向量e中選擇對應位置的k位構成ek，從Gpub選取對應的列構成k×k矩陣。如果選取的ek不含有錯誤的比特，即ek=0，攻擊者很容易恢復出明文m。

對于從RLCE方案公鑰中隨機選擇的k列，密文在這些位置上不包含錯誤的概率為

本文通過插入w個隨機列，增加了尋找選取的錯誤向量ek無差錯位置的困難性。給定適當的參數，攻擊者通過信息集譯碼攻擊獲取明文m是極其困難的，所以，本文通過插入隨機列保證了密碼方案不受信息集譯碼攻擊的影響。

（4）反應攻擊

反應攻擊是攻擊者通過修改少量的密文c，將修改后的密文發送給接收方，觀察接收方是否可以正確譯碼。對于給定的密文c，攻擊者隨機選擇位置i，在位置i添加錯誤，將添加錯誤的密文c發送給接收方，觀測接收方是否可以正確譯碼。如果接收方可以正確譯碼，說明攻擊者在位置i添加了錯誤；假如接收方譯碼失敗，說明攻擊者在位置i沒有添加錯誤。重復進行上述操作，直到攻擊者獲得k個無差錯位。本文通過插入w個隨機列，消息填充，可以抵抗反應攻擊。Liu提出的基于Polar碼的RLCE方案沒有考慮到反應攻擊，本文對可能存在的反應攻擊加以分析發現，不同于底層編碼為漢明循環碼的密碼方案，通過消息填充的方法，本文方案可以抵抗可能存在的反應攻擊。

5 IND-CCA2安全性

本文方案采用系統矩陣對明文m進行加密，使用這種方法加密明文，可能會導致方案IND-CCA2的安全性降低。Liu提出的基于Polar碼的RLCE方案不具有語義安全，并舉例說明了一種相關性攻擊的情況：對同一明文m進行兩次加密得到兩個不同的密文，可以將兩個不同的密文進行對比分析來找出原始的消息。根據上述闡述的消息填充方法，本文采用RLCEspad填充方法，對每個密文進行普通編碼，使部分消息被編碼在錯誤向量e非零項中。發送方在發送明文m之前，通過3個隨機諭言機模型H1,H2,H3將信息打亂，將部分消息編碼在錯誤向量e非零項中，然后將編碼后的消息發送給發送方。攻擊者為了獲取明文m，攻擊填充后的密碼方案，困難性等價于基于Goppa碼的McEliece原始方案。假設解碼RLCE密文是不可區分的，可以使用與文獻[12]中類似的證明來保證RLCE-RLCEspad方案可抵御IND-CCA2攻擊。所以，本文采用RLCEspad方法進行消息填充后的方案具有語義安全，可以達到IND-CCA2安全。

6 性能分析

下面從公鑰尺寸與私鑰尺寸兩個方面分析本文方案。

（1）公鑰尺寸

Gpub的尺寸為k×(n+w)，通過采用系統矩陣，改進后的Gpub的尺寸為k×(n+w-k)。

（2）私鑰尺寸

私鑰(V,W-1,G1,A,P)，V的尺寸為(k-u)u，W-1的尺寸為u×u，G1的尺寸為k×(n+w)，A的尺寸為(n+w)×(n+w)，P的尺寸為(n+w)×(n+w)。通過預計算W-1的值，改進后的方案不再存儲k×k階的矩陣S，減少了私鑰存儲空間。

通過表1，分析得到：

1)在相同的比特安全級別，本文方案的公鑰尺寸和Liu方案一樣，但本文方案具有IND-CCA2安全性，且本文對部分私鑰采用預計算的方法，可以明顯減少私鑰存儲空間；

2)在相同的比特安全級別，本文基于Polar碼的加密方案公鑰尺寸最小，在128 bit安全級別，本文方案相較于HermitianRLCE方案、GRSRLCE方案和GoppaMcEliece方案公鑰尺寸分別減少了4%、46.5%、47.9%。

表1 基于編碼的RLCE加密方案公鑰尺寸的對比Table 1 Comparison of public key Size of RLCE schemes based on encoding

7 結束語

利用Polar碼的等價類碼族較多、加解密復雜度低的優點，本文在RLCE方案和PolarRLCE加密方案的基礎上，利用Polar碼作為RLCE加密方案的底層編碼，通過采用RLCEspad消息填充的方法，將發送的消息擾亂，提出一種具有IND-CCA2安全的基于Polar碼改進的RLCE方案。本文將公鑰矩陣轉換為系統矩陣，減少了公鑰尺寸，對部分私鑰進行預計算，采用存儲預計算的值代替存儲私鑰S的值，減小了私鑰存儲空間。改進后的方案依然采用RLCE方案的結構，經過安全分析，可以抵抗目前已知存在的信息集譯碼等攻擊。將Polar碼作為底層編碼，相較于基于漢明循環碼的方案，本文方案可以抵抗已知存在的結構化等攻擊。

Polar碼因其獨特的極化性質和較低的譯碼復雜度等優點，日益成為研究的熱點。將Polar碼應用到基于編碼的密碼方案中，具有良好的研究前景。在接下來的工作中，可以進一步研究Polar碼的加密方案，構造更加適合5G通信環境下的輕量級加密方案。此外，研究RLCE方案的安全性和構造具有IND-CCA2安全的RLCE密鑰封裝機制，也是未來研究的重點。利用RLCE方案是否可以構造安全高效的簽名方案，這個問題值得以后深入研究。