基于Polar碼的ElGamal型公鑰密碼體制

劉冰 吳旭聃 聶艇

摘 要：在量子計算技術飛速發(fā)展的時代背景下，為了滿足密碼應用的安全需求，提出了一種基于Polar碼的ElGamal型公鑰密碼體制。采用Polar碼為基于糾錯碼ElGamal型公鑰密碼體制中的公開碼，利用SC譯碼算法進行譯碼，并對方案的譯碼失敗概率和安全性進行了分析。結果表明算法具有較高的傳信率，選取的參數滿足信息集譯碼復雜度和譯碼失敗概率的要求，且算法滿足IND-CPA安全性。

關鍵詞：公鑰密碼；ElGamal型體制；Polar碼；SC譯碼算法

中圖分類號：TP393.04?? 文獻標志碼：A?? 文章編號：1001-3695（2024）01-040-0254-06

doi：10.19734/j.issn.1001-3695.2023.05.0202

ELGamal public key cryptosystem based on Polar codes

Abstract：In the context of the rapid development of quantum computing technology，in order to meet the security requirements of cryptographic applications，this paper proposed an ElGamal public key cryptosystem based on Polar codes.The paper adopted Polar codes as the public code in the ElGamal public key cryptosystem based on error-correcting codes，used SC decoding algorithm to decode，and analyzed the decoding failure probability and security of the scheme.The results show that the algorithm has a high transmission rate，the selected parameters meet the requirements of information set decoding complexity and decoding failure probability，and the algorithm meets IND-CPA security.

Key words：public key cryptography；ELGamal type cryptosystem；Polar codes；SC decoding algorithm

公鑰密碼技術是互聯網電子商務認證和電子支付的關鍵技術之一。眾所周知，RSA［1］算法和橢圓曲線密碼［2］等廣泛使用的經典公鑰密碼系統(tǒng)［3］能被在量子計算機［4］上運行的Shor［5］算法破解。幸運的是，能夠進行具有實際參數長度的量子計算的量子計算機尚未出現，仍然可以使用這些經典的公鑰密碼系統(tǒng)。不過，在不久的將來有望研制出實用的量子計算機。因此，需要準備并深入研究這些算法的替代方案，這些替代方案所引出的研究方向被稱為“后量子密碼學（PQC）［6］”。

目前，一種安全性較高的 PQC 算法是基于糾錯碼（編碼）的公鑰密碼算法。NIST最近幾年開始征集后量子密碼算法，其中大致分為基于糾錯碼的、基于格的、基于哈希函數的以及基于同源的四類?；诩m錯碼的方案自1978年被提出以來，就一直以可靠的安全性被人們所青睞。經過篩選，進入到第四輪的后量子算法中，密鑰封裝算法一共有四個，其中基于糾錯碼的方案占了三個，它們的安全性都能得到保障。這幾種密鑰封裝算法都是在公鑰算法基礎上進行構造的，這也證明了基于糾錯碼的公鑰密碼方案在后量子領域具有一定的可行性。后續(xù)引用NIST算法時特指其基于的公鑰密碼算法。其中一種方案就是基于糾錯碼的ElGamal密碼體制，這種類型的方案最早由Aguilar-Melchor等人［7］于2017年提出，它是一個安全性依賴于隨機準循環(huán)碼［8］譯碼的高效密碼系統(tǒng)，它本質上與Mc-Eliece型［9］、Niederreiter型［10］不同，因為McEliece型、Niederrei-ter型是直接通過隱藏碼的結構來保證方案的安全性，但是隱藏的碼結構一旦被揭開，這些方案就會被攻破。ElGamal型加密方式采用了兩個獨立的碼，其中隨機準循環(huán)碼不需要解密，保證了方案的安全性；而公開碼C保證了算法的正確性，對效率有很大影響。它讓使用難以隱藏但譯碼效率很高的公開碼成為可能。與之相比，McEliece型和Niederreiter型方案的編譯碼方法是固定的。同時ElGamal型采用的公私鑰是臨時密鑰，每次密鑰交換時都會生成一個新的密鑰對，這意味著ElGamal型方式在信息傳輸時的密鑰是不斷更新的，這樣可有效抵御GJS攻擊。在這之后，又出現了ElGamal型的HQC［11］和RQC［12］算法，HQC就是第四輪方案中的一個。Barreto等人［13］提出了ElGamal型的CAKE算法，Deneuville等人［14］提出了ElGamal型的Ouroboros算法，Aragon等人［15］提出了BIKE算法，其中NIST第二輪中的BIKE 3是以Ouroboros算法為基礎進行改進的ElGamal型算法。2019年，王麗萍等人提出了秩距離下的ElGamal型Piglet-1算法。

本文提出的ElGamal 密碼系統(tǒng)在公開碼的選擇上為極化（Polar）碼，極化碼由Arikan［16］提出并證明漸近地達到香農極限［17］。該碼通過引入“信道極化”現象，并在信道條件下使用，區(qū)別于以往的糾錯碼。在信道極化中，通過線性處理，可以將N個等效信道漸近地分為沒有錯誤的好信道和不能用來傳輸任何信息的壞信道兩種類型，壞信道用來傳輸預先指定的比特（凍結比特），只使用好的信道來傳輸信息比特。通過使用SC譯碼算法［16］，可以解碼在好信道中所傳輸的信息。

本文提出了一種基于Polar碼的ElGamal型公鑰密碼體制，通過使用Polar碼對公開碼C進行替換，提高了信息傳輸的效率，并對其譯碼失敗概率等問題進行了分析。

1 Polar碼簡介

1.1 概述

Polar碼是Arikan于2009年提出的一種理論上能夠達到香農極限的信道編碼方式，它根據信道極化現象進行構造。信道極化指的是在完成信道組合和信道分裂后，所有信道會呈現兩極分化的現象，即一部分信道的信道容量趨于1，另一部分趨于0，且碼長N越大，這種現象就越明顯。編碼時，在信道容量趨于1的信道上傳輸信息，在信道容量趨于0的信道傳輸固定比特。

1.2 預備知識

二進制離散無記憶信道簡稱B-DMC信道，可以用W表示：X→Y。X為輸入，Y是輸出，則轉移概率為W（y|x），x∈X，y∈Y。信道是二進制輸入，輸入X∈（0，1}，輸出和轉移概率是任意的。為了傳輸信息比特，需要選擇最可靠的K個子信道作為信息位。A是K個信道的集合，Ac是其補集，包含最不可靠信道的索引。Polar碼由三個參數定義：N=2n，R=K/N和基數為K的信息集A∈N，即碼長、碼率和信息集。

給定一個B-DMC 信道，它有信道容量I（W）和巴氏參數Z（W）兩個重要的信道參數。它們表示如下：

其中：I（W）和Z（W）分別用作速率和可靠性的度量。它們取值都是［0，1］，并且Z（W）≈0時，I（W）≈1；Z（W）≈1時，I（W）≈0。Z（W）越小，表明信道越可靠，適合傳輸信息。

1.3 信道極化

信道極化包括信道組合和信道分裂兩個步驟［16］，其可以從給定N個B-DMC信道W的獨立副本中制造出另一組N個信道（W（i）N：1≤i≤N}，這些通道在某種意義上顯示出極化效應，即隨著N變大，極化后的N個信道的對稱容量{I（W（i）N）}項趨向于0或1。

1.3.1 信道組合

信道組合是將N個相同且相互獨立的B-DWC信道通過遞歸的形式生成新的信道WN，可以表示為WN：XN→YN，N=2n，n≥0。圖1展示了信道W2的組合過程，u21=（u1，u2）表示輸入序列，x21=u21G2，WN可以通過類似的過程遞歸得到，xN1=uN1GN，xNN表示乘以生成矩陣后的輸入，G2可以根據圖推得到，也稱為二元核矩陣，生成矩陣GN由G2通過克羅內克積［16］運算得到，yN1=（y1，y2，…，yN）表示輸出。

1.3.2 信道分裂

信道分裂是將組合后的信道WN拆分為N個信道 W（i）N，每個信道可表示為 W（i）N：X→YN×Xi-1。分裂后的N個信道之間存在依賴關系。分裂后的信道轉移概率為

其中：N是碼長。

計算得到了在完成信道分裂后的巴氏參數與碼長N的關系，如圖2所示?？梢钥闯?，N的值越大，巴氏參數兩極分化的現象就越明顯，即信道容量兩極分化的現象就越明顯。

1.3.3 信道極化定理

對于任意B-DMC信道W，δ∈（0，1） ，當N以2的冪趨于無窮時，極化后的信道W（i）N的信道容量為I（W（i）N），I（W（i）N）∈（1-δ，1］的信道數量占全部信道數趨于I（W），I（W（i）N）∈［0，δ）的信道數占全部信道數趨于1-I（W）。

1.4 Polar碼編碼

根據極化現象可以進行編碼。極化后的一部分信道的信道容量無限趨近于1，選取信道容量接近于1（巴氏參數趨近于0）的信道傳輸信息。

編碼步驟：a）信息位的選?。籦）構造生成矩陣；c）根據編碼公式xN1=uN1GN進行編碼。

a）確定極化碼碼長N和極化碼的編碼速率R。根據巴氏參數法［16］計算極化后信道：

并對其進行排序，Z（W（i）N）越小，信道就越可靠，由于K=RN，最后選出前K個可靠性較大的信道傳輸信息，其余NK個信道則傳輸凍結比特，這就完成了信息位的選取。Arikan［16］指出，在碼長N足夠大時，信息位數量K會無限接近于NI（W），這就表示，編碼速率R會無限接近香農極限I（W）。將信息位的序號集合記為A，發(fā)送凍結位的序號集合記為Ac。這里的待編碼序列可表示為uN1=（uA，uAc），uN1∈{0，1}N。uA是信息比特序列，uAc是凍結比特序列。

c）運用xN1=uN1GN進行編碼。為了方便表示，也可以采用另一種形式：

1.5 Polar碼譯碼

輸入序列uN1在經過編碼后得到編碼后序列xN1，xN1經過信道傳輸后在輸出端得到序列yN1，Polar碼譯碼的工作就是從yN1中得到uN1的估計值N1。

譯碼算法可以分為以SC為基礎的串行譯碼和以BP［19］為基礎的并行譯碼兩種類型。本文采用SC譯碼算法。SC譯碼算法在進行判決時只保留一條路徑，所以若有一個環(huán)節(jié)出錯，則后邊也會跟著出錯且無法對其進行糾正，所以存在譯碼失敗概率。對于給定的（N，K，A，uAc）Polar碼，通過計算

由于uAc是固定比特，其估計值是已知的，不會發(fā)生譯碼錯誤，所以Pe也可由式（8）表示。

對于任意的B-DMC信道W和任意選擇的參數組合（N，K，A），SC譯碼下誤塊率的關鍵界限為

所以，當式中有uAC時

對于任意給定的B-DMC信道W和確定的碼率R

SC譯碼是漸進最優(yōu)的，復雜度低，但在有限長度上仍然不足。最高效的譯碼器都基于SC譯碼而發(fā)展的，允許探索多條路徑。存在三種主要的路徑探索策略，應用于列表、順序和反轉算法，每種策略都在性能和復雜性之間進行權衡。

2 基于Polar碼的ElGamal型方案

2.1 方案基礎

Polar碼自從被提出以來，就成為編碼領域研究的熱點，它是唯一能在理論上被證明達到香農容量的編碼方式，擁有快速譯碼算法，具有較高的加解密速率，很多學者將Polar碼應用到公鑰密碼體制當中，達到了理想的效果?；诰幋a的公鑰密碼體制大致有McEliece型、Niederreiter型和ElGamal型三種類型。目前，基于Polar碼的McEliece型和Niederreiter型方案都已有學者提出，這些方案的思路都是將安全性寄托在Polar碼上，而本文方案與它們不同，因為ElGamal型公鑰密碼方案使用到碼保證方案的正確性和碼保證方案的安全性兩種碼，本文利用Polar碼能達到香農容量和擁有快速譯碼算法的特點來提升傳信率，同時安全性類似HQC等寄托于隨機準循環(huán)碼。

2.2 方案簡介

在本文方案中，Z表示整數環(huán)，F2表示二進制有限域。此外，用ω（·）表示一個向量的漢明重量，即它的非零坐標的數量。對于某些正的n∈Z，V表示F2上維度為n的向量空間。V的元素可以視為R=F2［X］/（Xn-1）中的行向量或多項式。如果多項式Xn-1/（X-1）在R中不可約，則稱素數n為原始整數。對于u，v∈V，定義它們的乘積類似于在R中，即uv=w∈V且

為了阻止結構攻擊，需要使用原始整數長度為n的Polar碼，以保證Xn-1只有兩個不可約因子。

方案包括密鑰生成、加密、解密三個部分。與HQC的ElGamal型方案相比，主要改進之處是將具有快速譯碼算法的公開碼C替換成Polar碼。方案存在兩種類型的碼：a）可譯碼的［n，k］線性碼C，由G∈Fk×n2生成，并且可以通過譯碼算法C.Decode（·）糾正至少δ個錯誤；b）隨機雙循環(huán)［2n，n］碼，具有奇偶校驗矩陣（1，h）。

下邊將具體描述方案。首先，生成并輸出全局參數param=（n，k，δ，w，wr，we）。F2［X］/（Xn-1）是多項式剩余類環(huán)。

基于Polar碼的ElGamal型公鑰密碼體制如下：

c）解密。令DG是Polar碼C能糾δ個錯誤的SC譯碼算法，解密如下m←DG（v-u·y）=DG（mG+xr2-r1y+e），返回DG（v-u·y）。

2.3 方案分析

如果固定A和uAC，將uA保留為自由變量，則得到從源塊uA到碼字塊xN1的映射。這個映射是陪集碼［16］，它是線性分組碼與生成矩陣GN（A）的陪集，陪集由固定向量uACGN（AC）決定，將這類碼統(tǒng)稱為GN陪集碼。單個GN陪集碼將由參數向量（N，K，A，uAC）標識，其中K是碼的維度并指定A的大小，K/N為碼率，A為信息集，uAC∈XN-K為凍結比特，由于GN（AC）傳輸的是凍結比特，實際上的生成矩陣是GN（A）。

本文提出的是一種使用極化碼來提高信息傳輸效率的方法，不影響其原本的安全性。安全性還是由隨機雙循環(huán)碼來保證。創(chuàng)建極化碼生成矩陣后，僅選擇給定信道條件下與良好信道對應的行，而丟棄其他行。因此，從這個選擇中，可以得到大小為K×N的生成矩陣GN（A）。

為了保證譯碼的可靠性和足夠的安全級別，n選取大于λ2的最小原始素數，以避免代數攻擊，其中λ是安全參數。密碼系統(tǒng)基于兩個碼：a）［n，k］碼C，其高效譯碼算法C.Decode（·）是已知的。碼C及其生成矩陣G是眾所周知的；b）系統(tǒng)形式的［2n，n］隨機雙循環(huán)碼，具有奇偶校驗矩陣（1，h）。該系統(tǒng)的總體思想是使用雙循環(huán)碼產生一些噪聲，這些噪聲可以由碼C處理和譯碼。

密碼系統(tǒng)的私鑰是一個短向量sk=（x，y）。為了加密屬于某個明文空間的消息m，它首先通過生成矩陣G進行編碼，然后使用校驗子s和一個附加的短向量e以防止信息泄露。換句話說，加密一條消息只是簡單地為它提供一個特定形式的噪聲編碼。合法接收者可以使用私鑰sk=（x，y）獲得明文的噪聲版本v-u·y，然后使用高效譯碼算法C.Decode恢復明文。為了保證正確性，所有基于McEliece方法的先前構造都依賴于這樣一個事實，即添加到消息編碼中的錯誤項小于或等于所使用碼的譯碼能力。在新的構造中，不再需要這個假設，并且密碼系統(tǒng)的正確性能夠得到保證，因為合法接收者可以使用私鑰sk從消息的噪聲編碼v中刪除足夠多的錯誤。

公鑰為pk=（h，s=x+h·y）。由于公鑰是“公開”信息，所以不僅僅是發(fā)送者“Alice”，每個人都知道pk，但對pk的因子x和y并不知道。因此，盡管其他人知道公鑰，但他們無法正確解密密文。極化碼的生成矩陣有不同的結構，可以使用文獻［16］描述的矩陣F以遞歸的方式推導生成矩陣。

方案加密：K比特的明文m被編碼如下：u=r1+h·r2，v=mG+s·r2+e，其中最后一項e是由于信道變換而主要出現在壞信道中的誤差向量。

方案的解密：這里討論了由真實接收者進行的解密。首先，使用密文部分的u乘上私鑰中的向量y得到u·y。再用密文v減去u·y，可以獲得如下數據：v-u·y。下面可以使用SC譯碼來依次譯碼v-u·y的比特。通過遞歸地計算似然比的值，如果已知前（i-1）位，可以獲得第i位的似然比。利用基于似然比的比特決策規(guī)則，得到第i位比特的估計值，然后再計算出i+1位的比特值，直到整個塊長度完成這個過程。在譯碼過程中，只需要對信息集作出判決。在凍結集中，插入了預先固定的位。在這里，預先固定的位被設置為全0向量。譯碼后，只選擇位于信息集索引中的那些位。從連續(xù)消除譯碼獲取的信息被給出為mG+xr2-r1y+e，再通過對xr2-r1y+e分析，即可解出明文m。

上面的討論引出了對譯碼失敗概率問題的研究，具體內容將在第3章中詳細闡述。

2.4 與McEliece方案的比較

在McEliece加密框架中，采用的思想是直接隱藏碼的結構，這導致了兩個結果。首先，安全性取決于隱藏碼的結構，其次，解密算法是無法更改的，只能對所隱藏的碼譯碼。根據隱藏碼的選擇，這會產生不同的實例化，從而會導致許多攻擊，而且無法被修改。

在本文框架中沒有唯一的隱藏碼，而是兩個獨立的碼，隨機雙循環(huán)結構保證方案的安全性，公開碼C保證正確解密。它使得考慮難以隱藏但譯碼非常高效的公共編碼族成為可能，但是需要在譯碼效率和實際譯碼復雜性之間找到平衡。這與解密編碼固定的McEliece方案不同，它是可以根據程序進行修改的。

3 譯碼失敗概率分析

ElGamal型方案需要一個公開的糾錯碼C來消除解密過程中固有的噪聲，碼C編碼速度快且有著精確的譯碼失敗概率（DFR）分析。DFR的分析包括兩個步驟：首先，要研究錯誤向量e′的重量分布，然后分析所選碼對給定重量的錯誤的譯碼效果。無論使用哪個公共碼對其進行譯碼，都可以進行DFR分析，本文使用的是Polar碼。由于該碼是公開的，其結構與安全性無關，可選擇任意碼族，僅影響解密失敗率和參數大小。

3.1 漢明距離的誤差向量分布

分析方案的譯碼失敗概率，首先要知道錯誤向量e′=x·r2-r1·y+e=（e′0，…，e′n-1）的每個固定坐標e′k的概率分布。e′k服從伯努利分布，可以假設e′k為自變量，因此可以使用參數p*的二項分布來表示e′的重量分布。換句話說，需要將錯誤向量建模為具有參數為p*的二進制對稱信道。參考HQC方案［11］，可以得到

3.2 Polar碼譯碼失敗概率分析

本節(jié)將分析Polar碼的DFR，它也對應整個加密方案的譯碼失敗概率。

Polar碼是陪集碼，有具體的公式，為了方便計算，在此公式下可以推出其上界，下面提供了這種情況下上界和下界。

給定參數為（N，K，A，uAc）的陪集碼，誤塊率（BLER）定義如下：

命題1 對于任意B-DMC信道W與任意選擇的參數組合（N，K，A），SC譯碼的誤塊率上界

命題2 對于任意B-DMC信道W與任意選擇的參數組合（N，K，A），SC譯碼的誤塊率下界

因為Polar碼的構造是針對具體信道的，為此先建立一個二元對稱信道（BSC）如圖3所示，它是一個典型的離散無記憶信道。p*在3.1節(jié)中已給出明確的公式，給出的估計值約等于0.3，即為在二進制信道模型下的p值。而實際方案中產生錯誤向量的模擬信道并非BSC信道，而是一種有記憶的信道，可以利用比特間的相關性來進行糾錯。這里采用BSC信道則是從最壞的情況進行估計，從而給出誤塊率的上界。

算法1 信道基于巴氏參數的精確構造算法

c）將巴氏參數{Z（W（i）2n）}按照從小到大排序，得到最終的可靠性結果

通過數值分析給出了不同p值下的碼長N與其對應的所有Z（W（i）N）的值的關系，這里N=37 258，結果如圖4～6所示。

的比較密集，也就表明可以在碼長較小時基本完成極化現象。還可以進行縱向對比：可以看出p在確定的情況下，隨著碼長的增加，極化現象就越明顯，這也驗證了Polar碼的最基本的原理——極化現象。為了防止結果的隨機性，本文又選取了碼長N=65 536的情況進行驗證，可以確定這個結論具有普遍性。在完成算法后，只取前K個巴氏參數求和，其中K值由程序所求。對于巴氏參數的求和算法，給出了程序上的實現，驗證了表1中的三種安全級別下的譯碼失敗概率的上界，均滿足譯碼失敗概率的要求。實際應用中碼長一般不是2n，因此需要用到打孔法來實現碼長的匹配。以安全參數為128的安全級別為例，選取的實際碼長為M=16 411，其中滿足2n-1

當實際碼長一定的情況下，譯碼失敗概率會隨著K的增加而增加，如果大于K的最大值的則不滿足譯碼失敗概率的要求，如圖7所示。

在滿足復雜度要求下適當改變碼長，K的最大值幾乎沒有變化。圖8和9是在128安全參數下，實際碼長為16 411和16 633的測試結果。

4 安全性分析

4.1 安全性證明

題——s-DQCSD（n，k，w），是問能否以不可忽略的優(yōu)勢判定（H，yT） 服從s-QCSD（n，k，w）分布或是 F（sn-k）×sn2×Fsn-k2上的均勻分布。

基于編碼的ElGamal型公鑰密碼方案滿足IND-CPA安全性。類似HQC［11］和Ouroboros［14］方案簡要給出如下證明過程：

定義敵手A執(zhí)行IND-CPA實驗 G1的優(yōu)勢：

在G1中替換s為隨機向量，構造實驗G2，可在G2基礎上構造區(qū)分2-DQCSD問題實驗，滿足

|Pr［b=b′in G1］-Pr［b=b′ in G2］|≤Adv2-DQCSD（B）（19）

在G2基礎上替換密文（u，v）為隨機向量，構造實驗G3，可在G3基礎上構造區(qū)分3-DQCSD問題實驗，滿足

|Pr［b=b′ in G2］-Pr［b=b′ in G3］|≤Adv3-DQCSD（C）（20）

AdvCPA（A）≤Adv2-DQCSD（B）+Adv3-DQCSD（C）（21）

可得，在2-DQCSD和3-DQCSD困難性假設下，算法具有IND-CPA安全性。

4.2 信息集譯碼復雜度分析

漢明度量的SD問題的實際復雜性已被研究了50多年。最有效的攻擊基于信息集譯碼（ISD），該技術首先由Prange［21］于1962年引入，后來由Stern［22］和Dumer［23］進行了改進。最近，有學者［24］關于某些常數c提出了2cw（1+negl（1））階的復雜度。一項專注于w=negl（n）的特定工作證實了這個公式，c與所用碼的編碼速率k/n之間存在密切相關性［25］。

當碼長n增長時，長度為n和維度為k的二進制線性碼中的w個錯誤的復雜度為2cw（1+o（1）），其中c是常數，具體取決于碼率k/n和錯誤率w/n。很多ISD變體在出現時都改進了常數c。當錯誤數量w是次線性時，w=o（n），所有ISD變體的復雜度仍然具有2cw（1+o（1））的形式。常數c僅取決于碼率k/n，并且對于上述所有已知的ISD變體都是相同的，包括五十年前的Prange算法。

參數集的選取涵蓋安全類別128（第1類）、192（第3類）和256（第5類）位經典（即前量子）的安全性，通過將安全位除以二（取復雜性的平方根），獲得量子安全的安全性。它們與譯碼失敗概率DFR密切相關。

對于參數為［n，k］的隨機準循環(huán)碼，r=n-k，n=2k，它是保證方案安全性的碼，需要考慮其時間復雜度，以滿足信息集譯碼復雜度的要求。估算的公式如下：

方案中向量x、y、r1、r2、e在重量為w、wr和we的向量中均勻隨機且獨立選擇。表2給出了三種安全級別下的具體參數，k的選取需要為素數，這是為了避免代數攻擊。w是N維向量x、y的重量，wr是r1和r2的重量，類似地，we=ω（e），這些向量的重量取值與w相近。

所選取的參數滿足信息集譯碼復雜度的要求，這樣就可以抵抗各種信息集譯碼算法的攻擊，保證了安全性。

最后將本文方案與進入NIST第四輪的三個基于編碼的方案進行對比，如表3所示，其中公鑰規(guī)模是在256安全級別下的值。需要注意的是，在HQC中利用種子擴展的方法來生成部分公鑰以進一步壓縮公鑰尺寸。而表3為在相同條件下進行對比，各算法公鑰均采用直接給出的方式。

5 結束語

本文結合編碼領域的新成果Polar碼和基于編碼的ElGamal型公鑰密碼體制，提出了基于Polar碼的El-Gamal型公鑰密碼體制，具有較高的編譯碼效率，著重對其譯碼失敗概率方面進行了分析。其安全性是基于隨機準循環(huán)碼的困難問題，能夠抵御多種攻擊類型，并給出了驗證結果。當然，本文所用到的譯碼算法的效率還有待進一步提高，以后可以對方案的參數做進一步優(yōu)化。

參考文獻：

［1］Rivest R L，Shamir A，Adleman L.A method for obtaining digital signatures and public-key cryptosystems［J］.Communications of the ACM，1978，21（2）：120-126.

［2］王輩，胡紅鋼.基于橢圓曲線中配對的密碼學研究綜述［J］.密碼學報，2022，9（2）：189-209.（Wang Bei，Hu Honggang.Overview of cryptography based on pairing in elliptic curves［J］.Journal of Cryptography，2022，9（2）：189-209.）

［3］Imam R，Areeb Q M，Alturki A，et al.Systematic and critical review of RSA based public key cryptographic schemes：Past and present status［J］.IEEE Access，2021，9：155949-155976.

［4］賽迪研究院.2021量子計算技術創(chuàng)新與趨勢展望［EB/OL］.（2021-06-04）.https：//www.ccidgroup.com/info/1096/33151.html.（China Center for Information Industry Development.2021 quantum computing technology innovation and trend outlook［EB/OL］.（2021-06-04）.https：//www.ccidgroup.com/info/1096/33151.html.）

［5］Shor P W.Algorithms for quantum computation：discrete logarithms and factoring［C］//Proc of the 35th annual symposium on foundations of computer science.Piscataway，NJ：IEEE Press，1994：124-134.

［6］楊嘉宇.抗量子密碼的研究與應用［D］.西安：西安電子科技大學，2021.（Yang Jiayu.Research and application of anti-quantum cryptography［D］.Xian ：Xidian University，2021.）

［7］Aguilar-Melchor C，Blazy O，Deneuville J C，et al.Efficient encryption from random quasi-cyclic codes［J］.IEEE Trans on Information Theory，2018，64（5）：3927-3943.

［8］Danish M N，Pasha S A，Hashmi A J.Quasi-cyclic LDPC codes for short block-lengths［C］// Proc of IEEE Aerospace Conference.Pisca-taway，NJ：IEEE Press，2021：1-8.

［9］McEliece R J.A public-key cryptosystem based on algebraic［J］.Coding Thv，1978，4244：114-116.

［10］Niederreiter H.Knapsack-type cryptosystems and algebraic coding theory［J］.Problems of Control and Information Theory，1986，15（2）：157-166.

［11］Melchor C A，Aragon N，Bettaieb S，et al.Hamming quasi-cyclic（HQC）［J］.NIST PQC Round，2018，2（4）：13.

［12］Melchor C A，Aragon N，Bettaieb S，et al.Rank quasi-cyclic（RQC）［EB/OL］.（2020-04-21）.https：//pqc-rqc.org/doc/rqc-specification_2020-04-21.pdf.

［13］Barreto P S L M，Gueron S，Güneysu T，et al.CAKE：code-based algorithm for key encapsulation［C］//Proc of the 16th IMA International Conference on Cryptography and Coding.Berlin：Springer，2017：207-226.

［14］Deneuville J C，Gaborit P，Zé mor G.Ouroboros：a simple，secure and efficient key exchange protocol based on coding theory［C］//Proc of International Workshop on Post-Quantum Cryptography.Cham：Sprin-ger，2017：18-34.

［15］Aragon N，Barreto P S L M，Bettaieb S，et al.BIKE：bit flipping key encapsulation［EB/OL］.（2017-11-30）.https：//bikesuite.org/files/BIKE.2017.11.30.pdf.

［16］Arikan E.Channel polarization：a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels［J］.IEEE Trans on Information Theory，2009，55（7）：3051-3073.

［17］Shannon C E.A mathematical theory of communication［J］.The Bell System Technical Journal，2001，5（3）：3-55.

［18］Reed I S.A class of multiple-error-correcting codes and the decoding scheme［J］.Trans of the IRE Professional Group on Information Theory，2003，4（4）：38-49.

［19］Saber H，Marsland I.Design of generalized concatenated codes based on polar codes with very short outer codes［J］.IEEE Trans on Vehicular Technology，2016，66（4）：3103-3115.

［20］Niu Kai，Chen Kai，Lin Jiaru.Beyond turbo codes：rate-compatible punctured polar codes［C］//Proc of IEEE International Conference on Communications.Piscataway，NJ：IEEE Press，2013：3423-3427.

［21］Prange E.The use of information sets in decoding cyclic codes［J］.IRE Trans on Information Theory，1962，8（5）：5-9.

［22］Stern J.A method for finding codewords of small weight［J］.Coding Theory and Applications，1989，388：106-113.

［23］Dumer I.On minimum distance decoding of linear codes［C］//Proc of the 5th Joint Soviet-Swedish International Workshop Information Theory.1991：50-52.

［24］May A，Ozerov I.On computing nearest neighbors with applications to decoding of binary linear codes［C］//Proc of the 34th Annual International Conference on the Theory and Applications of Cryptographic Technique.Berlin：Springer，2015：203-228.

［25］Canto T R，Sendrier N.Analysis of information set decoding for a sub-linear error weight［C］//Proc of the 7th International Workshop.Cham：Springer，2016：144-161.