基于Polar碼改進(jìn)的RLCE公鑰加密方案

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

（1.武警工程大學(xué)密碼工程學(xué)院，陜西 西安 710086；2.武警部隊(duì)密碼與信息安全保密重點(diǎn)實(shí)驗(yàn)室，陜西 西安 710086）

1 引言

量子計(jì)算機(jī)技術(shù)的飛速發(fā)展，將深刻影響當(dāng)前和未來(lái)的社會(huì)。銀行交易、無(wú)人駕駛、保密通信等與人們息息相關(guān)的各方面的安全性依賴于密碼學(xué)。Shor[1]提出的量子算法，極大影響了基于大整數(shù)分解困難問(wèn)題的RSA等[2]公鑰密碼方案；Grover[3]提出的量子算法，極大影響了AES等[4]對(duì)稱密碼方案。Shor算法和Grover算法的提出給經(jīng)典密碼方案的安全性帶來(lái)嚴(yán)峻的挑戰(zhàn)。

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

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

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

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

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

2.1 Polar碼編碼理論

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

Polar碼相較于Goppa碼具有更好的糾錯(cuò)能力，較低的加解密復(fù)雜度，較多的等價(jià)類碼族。擁有以上優(yōu)點(diǎn)的Polar碼應(yīng)用到編碼密碼方案中，將具有合理的密鑰尺寸，更加適合構(gòu)造基于Polar碼的加密方案，基于Polar碼的加密方案具有良好的應(yīng)用前景。Shrestha等[18]將Polar碼應(yīng)用到密碼方案中。隨著Polar碼理論的進(jìn)一步發(fā)展，Hooshmand等[19]進(jìn)一步研究Polar碼在密碼方案中的應(yīng)用，完善基于Polar碼的密碼方案。

定義1對(duì)稱信道

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

關(guān)于B-DMC的性能，可以通過(guò)兩個(gè)參數(shù)進(jìn)行評(píng)價(jià)：對(duì)稱容量I(W)和巴氏參數(shù)Z(W)。下面對(duì)兩個(gè)參數(shù)相關(guān)定義進(jìn)行闡述。

（1）對(duì)稱容量（symmetric capacity）

（2）巴氏參數(shù)（Bhattacharyya parameter）

I(W)∈[0,1]用于評(píng)估信道速率，Z(W)∈[0,1]用于評(píng)估信道可靠性。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è)階段：信道融合階段（channel combining）和信道分化（channel splitting）階段。

（1）信道融合階段描述

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

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

（2）信道分化階段描述

步驟1將信道融合構(gòu)成的復(fù)合信道WN分裂為N個(gè)二進(jìn)制輸入的坐標(biāo)信道。如下所示。

步驟2。

定義3極化碼編碼

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

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

（2）比特混合

可靠性較高的K個(gè)分裂子信道傳輸信息比特序列，而可靠性較低的分裂子信道傳輸凍結(jié)比特。通過(guò)比特混合后，輸出的比特為編碼的最初比特。對(duì)于BEC來(lái)說(shuō)，選擇巴氏參數(shù)最小的K個(gè)子信道傳輸信息比特。

（3）構(gòu)造生成矩陣

首先定義Kronecker 矩陣乘法為

定義矩陣F為，則生成矩陣，其中表示對(duì)矩陣F的n次克羅內(nèi)克積，。BN是比特反轉(zhuǎn)排序矩陣，用來(lái)對(duì)比特重排操作。BN的遞歸式定義為

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

2.2 RLCE加密方案

（1）RLCE密鑰生成過(guò)程如算法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)選擇長(zhǎng)度為n，維度為k的k×n生成矩陣G。

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

3)為了混合選擇的列，選擇w個(gè)2×2隨機(jī)非奇異矩陣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加密過(guò)程如算法2所示。

算法2RLCE加密

輸入公鑰Gpub，明文，隨機(jī)錯(cuò)誤向量。

輸出密文。

（3）RLCE解密過(guò)程如算法3所示。

算法3RLCE解密

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

輸出明文，譯碼錯(cuò)誤標(biāo)識(shí)⊥。

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

3)c′=。

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

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

2.3 信息編碼

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

（1）基本編碼（basic encoding）

（2）普通編碼（medium encoding）

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

（3）高級(jí)編碼（advanced encoding）

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

接下來(lái)概述常見(jiàn)的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是隨機(jī)諭言機(jī)模型（也可以是偽隨機(jī)位生成器或者哈希函數(shù)）輸出固定長(zhǎng)度的偽隨機(jī)比特串；1r、2r是隨機(jī)選擇的適當(dāng)長(zhǎng)度的比特串。

3 本文的加密方案

3.1 改進(jìn)的RLCE公鑰加密方案

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

（1）密鑰生成

密鑰生成過(guò)程如下。

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

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

3)G1：長(zhǎng)度為n+w，維度為k的Polar碼的k×(n+w)的生成矩陣，可以將隨機(jī)選擇的w個(gè)k×1的列向量r1,r2,…,rw隨機(jī)插入生成矩陣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）加密

發(fā)送方對(duì)明文進(jìn)行加密過(guò)程如下。

2)發(fā)送方利用接收方的公鑰pubG對(duì)明文m進(jìn)行加密，得到密文。

（3）解密

接收方對(duì)密文進(jìn)行解密過(guò)程如下。

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

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

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

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

3.2 將公鑰矩陣轉(zhuǎn)換為系統(tǒng)矩陣

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

對(duì)于每個(gè)i＜k，當(dāng)j＜n-w，di′=dj，令mi=dj，當(dāng)m=(m1,…mk)。

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

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

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

可以預(yù)計(jì)算W-1。

通過(guò)將公鑰矩陣轉(zhuǎn)換為系統(tǒng)矩陣，可以把V,W-1作為私鑰存儲(chǔ)，不再存儲(chǔ)私鑰S，以降低密鑰存儲(chǔ)空間。

3.3 消息填充

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

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

（2）H1,H2,H3是隨機(jī)諭言機(jī)模型，可以分別將任意長(zhǎng)度的二進(jìn)制比特串轉(zhuǎn)化為長(zhǎng)度為k2，k1+k2，k3字節(jié)的輸出比特串。

（3）m∈{0,1}8k1是需要填充的信息，當(dāng)r1∈是隨機(jī)選擇的二進(jìn)制比特串。

RLCE填充過(guò)程如算法4所示。

算法4 RLCEspad

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

輸出(y1,e1),c。

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

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

4 安全性分析

（1）窮舉攻擊

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

（2）密鑰恢復(fù)攻擊

密鑰恢復(fù)攻擊的基本思想是：從公鑰Gpub恢復(fù)出正確的私鑰。密鑰恢復(fù)攻擊是一種結(jié)構(gòu)攻擊，通常是針對(duì)特定的編碼，如QC-LDPC碼、GRS碼等。本文提出的方案插入了隨機(jī)列，同時(shí)采用2×2隨機(jī)非奇異矩陣A對(duì)插入的隨機(jī)列進(jìn)行混合，私鑰的結(jié)構(gòu)被打亂?；旌现笥蛛S機(jī)從長(zhǎng)度為n+w密文中刪除w列凍結(jié)比特列，由于攻擊者無(wú)法知道Polar碼的極化性質(zhì)，進(jìn)一步增加了私鑰結(jié)構(gòu)的復(fù)雜度，攻擊者在多項(xiàng)式時(shí)間內(nèi)通過(guò)公鑰難以恢復(fù)出正確的私鑰結(jié)構(gòu)。Bardet等[24]針對(duì)Polar碼提出一種確定最小權(quán)重的攻擊，解決了極化碼相對(duì)于遞減單項(xiàng)式碼的等價(jià)問(wèn)題。本文方案插入的隨機(jī)列擾亂了生成矩陣的原有編碼結(jié)構(gòu)，所以文獻(xiàn)[24]不會(huì)影響本文方案的安全性。因?yàn)镻olar碼的結(jié)構(gòu)與漢明循環(huán)碼、GRS碼和RM碼結(jié)構(gòu)不同，針對(duì)底層編碼為循環(huán)碼、GRS碼和RM碼的結(jié)構(gòu)化攻擊，不會(huì)威脅本文方案的安全性。

（3）信息集譯碼攻擊

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

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

本文通過(guò)插入w個(gè)隨機(jī)列，增加了尋找選取的錯(cuò)誤向量ek無(wú)差錯(cuò)位置的困難性。給定適當(dāng)?shù)膮?shù)，攻擊者通過(guò)信息集譯碼攻擊獲取明文m是極其困難的，所以，本文通過(guò)插入隨機(jī)列保證了密碼方案不受信息集譯碼攻擊的影響。

（4）反應(yīng)攻擊

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

5 IND-CCA2安全性

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

6 性能分析

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

（1）公鑰尺寸

Gpub的尺寸為k×(n+w)，通過(guò)采用系統(tǒng)矩陣，改進(jìn)后的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)。通過(guò)預(yù)計(jì)算W-1的值，改進(jìn)后的方案不再存儲(chǔ)k×k階的矩陣S，減少了私鑰存儲(chǔ)空間。

通過(guò)表1，分析得到：

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

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

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

7 結(jié)束語(yǔ)

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

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