列表译码在密码中的应用综述

张卓然; 张煌; 张方国

doi:10.11999/JEIT190851

列表译码在密码中的应用综述

doi: 10.11999/JEIT190851

1.
中山大学数据科学与计算机学院广州 510006
2.
广东省信息安全技术重点实验室广州 510006

基金项目: 国家自然科学基金(61672550, 61972429)，国家重点研发计划(2017YFB0802503)

详细信息

作者简介:
张卓然：女，1995年生，博士生，研究方向为基于纠错码的密码学

张煌：男，1988年生，博士生，研究方向为格密码和零知识

张方国：男，1972年生，教授，研究方向为密码学理论及其应用，特别是椭圆曲线密码体制、安全多方计算、可证明安全性等

通讯作者:
张方国　isszhfg@mail.sysu.edu.cn

中图分类号: TP393
计量
- 文章访问数: 3617
- HTML全文浏览量: 1264
- PDF下载量: 190
- 被引次数: 7
出版历程
- 收稿日期: 2019-11-01
- 修回日期: 2020-02-25
- 网络出版日期: 2020-03-19
- 刊出日期: 2020-06-04

Survey on Applications of List Decoding to Cryptography

1.
School of Data and Computer Science, Sun Yat-sen University, Guangzhou 510006, China
2.
Guangdong Key Laboratory of Information Security, Guangzhou 510006, China

Funds: The National Natural Science Foundation of China (61672550, 61972429), The National Key R & D Program of China (2017YFB0802503)

摘要

摘要: 列表译码自上世纪50年代提出以来，不仅在通信与编码等方面得到了广泛应用，也在计算复杂性理论和密码学领域有着广泛的应用。近年来，随着量子计算的发展，基于整数分解等传统困难问题设计的密码方案受到了巨大的威胁。由于编码理论中一些计算问题的NP困难性被广泛认为是量子概率多项式时间不可攻克的，建立在其上的基于纠错码的密码体制得到了越来越多的重视，列表译码也越来越引起人们的关注。该文系统梳理了列表译码在密码学中的应用，包括早期在证明任何单向函数都存在硬核谓词、设计叛徒追踪方案、以多项式重建作为密码原语设计公钥方案、改进传统基于纠错码的密码方案和求解离散对数问题(DLP)等方面的应用，以及近期，列表译码在设计安全通信协议、求解椭圆曲线离散对数问题、设计新的基于纠错码的密码方案等方面的应用。该文对列表译码的算法改进及其在密码协议设计和密码分析中的应用、新应用场景探索等方面的发展趋势进行了探讨。
- 公钥密码 /
- 列表译码 /
- 离散对数 /
- 后量子密码
Abstract: Since the conception of list decoding is proposed in the 1950s, list decoding not only is applied to communication and coding theory, but also plays a significant role in computational complexity and cryptography. In recent years, with the rapid development of quantum computing, the traditional cryptographic schemes based on factorization and other difficult problems are greatly threatened. The code-based cryptosystems, whose security relies on the NP-hard problems in coding theory, are attracting more and more attention as a candidate of the post-quantum cryptography, and so does the list decoding algorithm. This paper systematically reviews the applications of list decoding to cryptography, including early applications in proving that any one-way function has hard-core bits, designing traitor tracing schemes, designing public key schemes using polynomial reconstruction as cryptographic primitives, improving the traditional code-based cryptosystems and solving Discrete Logarithm Problems (DLP), and recent applications to designing secure communication interactive protocols, solving the elliptic curve discrete logarithm problem, and designs new cryptographic schemes based on error correction codes. Finally, the new research issues of the algorithm improvement of list decoding, its application to the design of cryptographic protocol and cryptoanalysis, and the exploration of new application scenarios are discussed.
- Public key cryptography /
- List decoding /
- Discrete logarithm /
- Post-quantum cryptography

HTML全文

1. 引言

2019年9月，芬兰奥卢大学6G旗舰研究计划组发布了全球首个6G白皮书，该白皮书认为6G的大多数性能指标相比5G将提升10～100倍。其中通信时延可低至0.1 ms，将是5G的1/10，并且具有超高可靠性^[1]。这些需求对移动通信中的信道编解码的延迟特性和译码性能提出了更高的要求。极化码是第1种被证明在二进制离散无记忆信道下能够达到信道容量的纠错码^[2]，具有较高的可靠度和实用价值，已经成为5G控制信道的编码方案，并有望成为6G通信中主要的信道编码方案。在极化码的译码算法方面，串行抵消(Successive Cancellation, SC)算法^[3,4]和串行抵消列表(Successive Cancellation List, SCL)^[5]作为极化码的低复杂度译码方案，具有较高的可靠性，但在译码时均需遍历译码二叉树的每个节点，导致译码延迟较高。与SC, SCL算法不同，置信度传播算法(Belief Propagation, BP)是一种并行迭代的译码算法，可获得较低的译码延迟。然而，大量的迭代次数仍造成BP较高的计算复杂度。由于大部分BP译码器在到达最大迭代次数之前已经收敛于原始码字，因此需要引入迭代早期迭代停止准则提前判断。为了减少迭代冗余，Yuan等人^[6]提出了G矩阵(G-matrix)和最小对数似然比 (minimum Log Likelihood Ratio, minLLR)两个准则。其中，G-Matrix包含 $N\log N$ 次二进制操作，而minLLR需要进行大量的比较运算。Yan等人^[7]提出一种基于局部固定比特的早期停止准则，将固定位作为提前停止的准则。为降低资源消耗，文献[8]提出一种有效节省资源消耗的提前迭代终止准则，与基于阈值的算法相比，该准则可降低资源消耗且不会造成译码性能损失。Ren等人^[9]提出了LLR辅助(LLR-Magnitude Aided, LMA)和循环冗余校验辅助(CRC Aided, CA)两种早期停止准则，当信噪比为4 dB、最大迭代次数为30时，LMA和CA分别能减少72.6%和84.5%的迭代次数。此外，Simsek等人^[10]提出一种基于最坏信息位(Worst of Information Bits, WIB)的早期停止准则，它只需检测一部分LLR的符号位，可使译码复杂度有所降低，但译码性能低于G-Matrix。Simsek等人^[11]通过去除冗余加法器阵列对WIB进行了优化。另外，Albayrak等人^[12]提出了一种基于Luby变换的提前停止准则，通过观察译码器中LLR信息的符号位变化，确定译码输出是否收敛到原始序列。文献[13]于2017年提出了一种检测冻结位误码率(Frozen Bit Error Rates, FBER)的早期停止准则，该准则只检测在最可靠的冻结子信道中传输的冻结位。受到早期停止准则的启发，Giard等人^[14]提出了基于极化码BP译码算法的盲检测法。上述准则都取决于 $\hat u$ 或与 $\hat u$ 对应的对数似然比(Log Likelihood Ratio, LLR)。

本文研究了信息序列估值( $\hat u$ )与码字估值( $\hat x$ )之间的关系，当 $\hat u$ 和 $\hat x$ 满足编码算法施加的约束时，可获得有效的码字估值。当 $\hat x$ 收敛到有效估值时， $\hat u$ 亦收敛到有效估值。基于这一思想，本文提出了一种新的早期停止准则，该方案只监测 $\hat x$ 的收敛性。同时，借助高斯近似(Gaussian Approximation, GA)^[15]分析了 $\hat x$ 中每位比特的出错概率，发现一些出错概率较低的 $\hat x$ 需要较少的迭代次数。因此，该准则构造了一个由 $\hat x$ 中出错概率较低的部分构成的比较空间。由于只检测 $\hat x$ 中一部分比特的收敛性，所提出的准则进一步节省了硬件资源消耗。另外，由于译码器的最终输出是 $\hat u$ ，如果早期停止准则取决于 $\hat u$ ，那么它只能在获得 $\hat u$ 后开始执行，将导致额外的计算复杂性和延迟。所提出的方案只取决于 $\hat x$ ，可避免这种情况。仿真结果表明，所提算法在不损失译码性能的情况下，可有效降低计算复杂度并减少译码的平均迭代次数。

2. 基本理论

2.1 极化码

极化码可定义为{N, K, A, A^C}，其中N=2ⁿ, K, A, A^C分别表示码长、信息位个数、信息位集合和冻结位集合。信息 ${{u}}$ 由K个信息位和(N-K)个冻结位组成，与生成矩阵G相乘获得码字 ${{x}}$ 。其中 ${{G}} = {{B}} \cdot {{{F}}^{ \otimes n}}$ , $B$ 是位置换矩阵， ${{{F}} ^{ \otimes n}}$ 表示 ${{F}} = \left[ {\begin{array}{*{20}{c}} 1&0 \\ 1&1 \end{array}} \right]$ 的n次克罗内克积。

2.2 BP译码算法

一个 (N, K)极化码可用一个 $n$ 阶因子图来表示，它在每阶都有N/2个处理单元(Processing Element, PE)，整个因子图包含 (n+1)N个节点。图1为(8, 4)极化码的因子图。BP算法的每次迭代过程由一个右向信息更新和一个左向信息更新组成。令 $L_{i,j}^t$ 和 $R_{i,j}^t$ 分别表示节点(i, j)在第t次迭代中自右向左和自左向右传播的信息，其中i是位索引，j是阶数索引。BP译码器中的节点更新如式(1)所示

图 1 (8, 4)极化码的因子图

下载: 全尺寸图片幻灯片

$\left. \begin{aligned} & L_{i,j}^t = \left\{ {{{f}} \left( {R_{i + N/2,j}^t + L_{2i,j + 1}^t,L_{2i - 1,j + 1}^t} \right)} \right\} \\ & L_{i + N/2,j}^t = \left\{ {{{f}} \left( {R_{i + N/2,j}^t + L_{2i,j + 1}^t} \right) + L_{2i,j + 1}^t} \right\} \\ & R_{2i - 1,j + 1}^t = \left\{ {{{f}} \left( {L_{2i,j + 1}^{t - 1} + R_{i + N/2,j}^t,R_{i,j}^t} \right)} \right\} \\ & R_{2i,j + 1}^t = \left\{ {{{f}} \left( {L_{2i - 1,j + 1}^{t - 1},R_{i,j}^t} \right) + R_{i + N/2,j}^t} \right\} \end{aligned} \right\}$

(1)

其中

${{f}} ({{x}},{{y}}) \approx \alpha *{\rm{sign}} ({{x}}){\rm{sign}} ({{y}})\min {\kern 1pt} (|{{x}}|,|{{y}}|)$

(2)

式(2)中α是伸缩因子。在右向更新信息期间，按照 $j = 2,3, ··· ,n + 1$ , $R_{i,j}^t$ 进行串行更新。在 $n + 1$ 列的 $R_{i,j + 1}^t$ 更新之后进行左向更新， $L_{i,j}^t$ 按照 $j = n,n - 1, ··· ,1$ 进行串行更新。当BP译码器达到最大迭代次数 ${I_{\max }}$ 时，第 $i$ 个信息位的估值可通过式(3)得到

${\hat u_i} = {\rm{sign}} (L_{i,1}^{{I_{\max }}}),i \in A$

(3)

3. 提出的早期迭代停止准则

3.1 X-tolerance早期迭代停止准则

BP算法的迭代过程可用极化码的因子图来表示。因子图中的每一个节点都与编码过程中的节点相对应，由于因子图节点中包含相应节点的LLR，则对因子图节点中的LLR进行硬判决即可得到相应的编码过程的中间估计值。对最左侧列节点中的LLR进行硬判决可得 ${u_i}$ 的估值 ${\hat u_i}$ ，类似地对最右侧即因子图中第n+1列节点中的LLR进行判决可得到 ${x_i}$ 的估值 ${\hat x_i}$ 。设 $R_{i,n + 1}^t = \ln ({P} ({\hat x_i} = 0)/{P} ({\hat x_i} = 1)$ , ${\hat x_i}$ 代表码字估值中的第i位。因此， ${\hat x_i}$ 定义为

${\hat x_i} = {s_{i,n + 1}} = {\rm{sign}} (R_{i,n + 1}^t)$

(4)

$\hat x = \left\{ {{{\hat x}_1},{{\hat x}_2},···,{{\hat x}_N}} \right\} = ({s_{1,n + 1}},{s_{2,n + 1}}, ··· ,{s_{N,n + 1}})\!\!\!\!\!$

(5)

对于任何极化码， ${{x}} = {{u}} \cdot {{G}}$ ，如果 $\hat x$ 和 $\hat u$ 是有效的估值，则必须满足式(6)

$\hat {{x}} = \hat {{u}} \cdot {{G}}$

(6)

基于该推论， ${{ \hat x}} = {{\hat u }}\cdot {{G}}$ 可被用于在迭代过程中检测 ${{\hat x}}$ 与 ${{\hat u}}$ 是否为有效的估值。G-Matrix早期停止准则根据极化码编码中信息序列 $u$ 和码字 $x$ 之间的关系，在译码迭代中通过判断是否满足式(6)来决定是否提前停止译码迭代，因此每一次判断都相当于进行一次极化码编码。本文对G-Matrix做了进一步分析，依据式(6)，发现译码中信息序列估值 ${{\hat u}}$ 和码字估值 ${{\hat x}}$ 存在下列3种类型：类型1， ${{\hat x}}$ 和 ${{\hat u}}$ 满足式(6), ${{\hat x}}$ 和 ${{\hat u}}$ 均为有效估值；类型2， ${{\hat x}}$ 和 ${{\hat u}}$ 满足式(6), ${{\hat x}}$ 和 ${{\hat u}}$ 均为有效估值，但 ${{\hat u}}$ 并不是发送端所传输的信息序列；类型3：迭代次数达到最大迭代次数时依旧不满足式(6)。

对于类型2, ${{\hat x}}$ 和 ${{\hat u}}$ 在迭代过程中满足这种约束，即 ${{\hat x}}$ 的确是 ${{\hat u}}$ 经过极化编码后的码字，但 $\hat u_1^N \ne u_1^N$ ，即该信息序列并不是发送端所发送的信息。该类型情况在译码过程中极少发生，可忽略。类型3属于提前终止准则无法处理的情况，该类型会在迭代次数到达预设的最大迭代次数后停止。由以上分析可知，有效处理类型1是本文研究的重点。

对于类型1，为了满足式(6), ${{\hat x}}$ 和 ${{\hat u}}$ 需要同时为有效的估值。令 ${T_u}$ 表示 ${{\hat u}}$ 收敛所需的最小迭代次数， ${T_x}$ 表示 ${{\hat x}}$ 收敛所需的最小迭代次数，则类型1中迭代终止所需迭代次数由 ${T_u}$ 和 ${T_x}$ 中的较大值决定。

令 ${T_d}$ 表示译码成功所需的最小迭代次数。通过仿真得到 ${T_d}$ , ${T_u}$ 和 ${T_x}$ 之间的大小关系。图2展示了 ${T_u} - {T_d} > 0$ 和 ${T_x} - {T_u} > 0$ 的比例，灰色部分为 ${T_u} - {T_d} = 0$ 的比例。从图2中可看到 ${T_x}$ 是 ${T_u}$ 和 ${T_x}$ 之间较大的那个。因此，对于类型1，迭代终止准则可简化为判断 $\hat x$ 是否收敛。如图3所示，当E_b/N₀= $2.5\;{\rm{dB}}$ 时，随着迭代次数的增加， ${{\hat x}}$ 中的符号改变个数和 ${{\hat u}}$ 中的错误估值位数均迅速下降。当 ${{\hat u}}$ 中的错误估值位数下降到0，得到一个有效估值。

图 2

${T_d}$ ,

${T_u}$ 和

${T_x}$ 的大小关系

下载: 全尺寸图片幻灯片

图 3

$\hat x$ 中符号变化和

$\hat u$ 中错误位数

下载: 全尺寸图片幻灯片

在BP译码过程中，如果 ${{\hat x}}$ 连续几次迭代保持不变，则认定 ${{\hat x}}$ 已经收敛。因此，本文提出了一种新的停止准则，称之为X-tolerance。当 ${{\hat x}}$ 在连续X次迭代中保持不变时停止迭代。X-tolerance检测规则如式(7)所示。该准则不同于G-Matrix，它只依赖码字估计值 ${{\hat x}}$ ，无须每次迭代均对 ${{\hat u}}$ 进行重新编码，因此减少了计算复杂度

$\sum\limits_{t - X + 1}^t {\sum\limits_{i = 1}^N {\hat x_i^t} } \oplus \hat x_i^{t - 1} = 0$

(7)

3.2 比较空间的构造

在式(7)中，X-tolerance在一次迭代中需要N个异或(XOR)操作，为了进一步减小计算复杂度，本文定义了一个集合 $S \subseteq \left\{ {1,2, ··· ,N} \right\}$ ，称为比较空间，是由 $\hat x$ 中部分比特的索引构成的集合。设 $P({\hat x_i} \ne {x_i})$ 是当 $t = {I_{\max }}$ 时的 ${\hat x_i}$ 的出错概率。对于BP译码器，具有较低 $P({\hat x_i} \ne {x_i})$ 的 $\hat x_1^N$ 需要较少的译码迭代。利用这一思想，根据 $P({\hat x_i} \ne {x_i})$ 构造了比较空间。

对于n=3，极化码的Tanner图如图4所示。圆圈表示变量节点，方块表示校验节点。变量节点中的信息用LLR表示。设 ${a_{i,j}}$ 表示节点 $v(i,j)$ 的LLR的概率密度函数(Probability Density Function, PDF)。假设传输全零码字，基于密度进化理论^[11]，采用式(8)和式(9)递归地计算 ${a_{i,j}}$

图 4 (8, 4)极化码的Tanner图

下载: 全尺寸图片幻灯片

$\begin{split} \qquad\quad\ & {a_{2i - 1,j}} = {a_{i,j + 1}} \odot {a_{i + {2^{j + 1}},j + 1}},\\ & {a_{2i,j}} = {a_{i,j + 1}} \otimes {a_{i + {2^{j + 1}},j + 1}} \end{split}$

(8)

$\quad {a_{i,n + 1}} = {a_w}$

(9)

其中， $\odot$ 和 $\otimes$ 分别是变量节点和校验节点的卷积操作。 ${a_w}$ 是信道W接收到的LLR的概率密度函数。对于BP译码，设 $r_{i,j}^t$ 和 $l_{i,j}^t$ 表示 $v(i,j)$ 中 $R_{i,j}^t$ 和 $L_{i,j}^t$ 的概率密度函数。根据式(1)和密度进化理论， $r_{i,j}^t$ 和 $l_{i,j}^t$ 可通过式(10)计算

$\left. \begin{aligned} & r_{i,{{j}} + 1}^t = \left\{ {r_{2i - 1,{{j}}}^t \odot (r_{2i,{{j}}}^t \otimes l_{i + {2^{j + 1}},{{j}} + 1}^{t - 1})} \right\} \\ & r_{i + {2^{j + 1}},{{j}} + 1}^t = \left\{ {(r_{2i - 1,{{j}}}^t \otimes l_{i,{{j}} + 1}^{t - 1}) \odot r_{2i,{{j}}}^t} \right\} \\ & l_{2i - 1,{{j}}}^t = \left\{ {l_{i,{{j}} + 1}^t \odot (l_{i + {2^{j + 1}},{{j}} + 1}^t \otimes r_{2i,{{j}}}^t)} \right\} \\ & l_{2i,{{j}}}^t = \left\{ {(l_{i,{{j}} + 1}^t \otimes r_{2i - 1,{{j}}}^t) \odot l_{i + {2^{j + 1}},{{j}} + 1}^t} \right\} \end{aligned}\right\}$

(10)

根据BP算法的初始化可得， $r_{i,1}^t$ 满足

$\int\limits_{ - \infty }^0 {r_{i,1}^t} {\rm{d}}z = \left\{ \begin{aligned} & {0.5,i \in A} \\ & {0,\ \ i \notin A} \end{aligned} \right.,\;l_{i,n + 1}^t = {a_w}$

(11)

可用GA简化计算， $r_{i,j}^t$ 和 $l_{i,j}^t$ 分别表示为 ${\cal{N}}(m_{i,j}^{r,t},2m_{i,j}^{r,t})$ 和 ${\cal{N}}(m_{i,j}^{l,t},2m_{i,j}^{l,t})$ ^[13]。因此，式(10)和式(11)可近似为

$\begin{split} & m_{i,j + 1}^{r,t} = \left\{ {\varphi ^{ - 1}}(1 - [1 - \varphi (m_{2i - 1,j}^{r,t})]\right.\\ & \qquad\quad\ \ \left.\cdot [1 - \varphi (m_{2i,j}^{r,t} + m_{i + {2^{j + 1}},j + 1}^{l,t - 1})]) \right\}, \\ & m_{i + {2^{j + 1}},j + 1}^{r,t} = \left\{ {\varphi ^{ - 1}}(1 - [1 - \varphi (m_{2i - 1,j}^{r,t})]\right.\\ & \qquad\qquad\qquad \left.\cdot [1 - \varphi (m_{i,j + 1}^{l,t - 1})]) + m_{2i,j}^{r,t} \right\}, \\ & m_{2i - 1,j}^{l,t} = \left\{ {\varphi ^{ - 1}}(1 - [1 - \varphi (m_{i,j + 1}^{l,t})]\right.\\ & \qquad\quad\ \ \ \left.\cdot [1 - \varphi (m_{2i,j}^{l,t} + m_{i + {2^{j + 1}},j + 1}^{r,t})]) \right\}, \\ & m_{2i,j}^{l,t} = \left\{ {\varphi ^{ - 1}}(1 - [1 - \varphi (m_{2i - 1,j}^{l,t})] \right.\\ & \qquad\quad\ \left. \cdot [1 - \varphi (m_{i,j + 1}^{l,t})]) + m_{i + {2^{j + 1}},j + 1}^{l,t} \right\} \!\!\!\!\! \end{split}$

(12)

$m_{i,1}^{r,t} = \left\{ \begin{aligned} & {0,\quad\ i \in A} \\ & { + \infty ,i \notin A} \end{aligned} \right.$

(13)

$m_{i,n + 1}^{l,t} = 2/{\sigma ^2}$

(14)

在得到 $m_{i,n + 1}^{l,{I_{\max }}}$ 后， ${\hat x_i}$ 的错误概率通过式(15)计算

$\begin{split} P({\hat x_i} \ne {x_i}) =\,& \int\limits_{ - \infty }^0 {\frac{1}{{2\sqrt {\pi a_{i,n + 1}^t} }}} \\ & \cdot \exp \left( {\frac{{ - {{(x - m_{i,n + 1}^{l,{I_{\max }}})}^2}}}{{4m_{i,n + 1}^{l,{{{I}} _{\max }}}}}} \right){\rm{d}}x \end{split}$

(15)

式(15)可简化为^[16]

$\begin{split} & P({\hat x_i} \ne {x_i}) \\ & = \left[ {{\rm{1}} - {{\left( {1 - \exp \left( { - \left( {m_{i,n + 1}^{l,{I_{\max }}}/2} \right)/1.6058} \right)} \right)}^{1/2}}} \right]\Bigr/2 \end{split}$

(16)

对于X-tolerance，当采用比较空间缩小检测范围时，错误率会增加。然而，当增加X来弥补性能损失时，又增加了平均迭代次数。因此，为尽可能降低平均迭代次数，S由 $\{ P({\hat x_i} \ne {x_i})\left| {i = 1,2, ··· ,{{N}}} \right.\}$ 中Q个最小值的索引构成。当式(17)满足时，X-tolerance停止迭代译码，在算法1中给出了具体的BP译码过程

算法1　(N, K) X-tolerance BP译码器
(1) 输入：
(2) 信道输出： ${\rm{ LLR}}\left( { {r_i} } \right)$
(3) 冻结位集合： $A^C$
(4) 比较空间：S
(5) 初始化：
(6) 设定 ${I_{\max }}$ 和X
(7) For 每个节点的传播信息 $L_{i,j}^t$ 和 $R_{i,j}^t$
(8)　　if $(j = = 1)$ & $\left( {i \in {A^C}} \right)$ $R_{i,1}^t = \infty$ 对于t=0, 1,···, I_max
(9)　　else if $(j = = 1 + n)$ $L_{i,n + 1}^t = {\rm{LLR}}\left( { {r_i} } \right)$ 对于t=0, 1,···, 　　　　 I_{max x}
(10)　　else $L_{i,j}^0 = R_{i,j}^0 = 0$
(11) 迭代过程：
(12) While $t < {I_{\max }}$ do
(13) 根据(1)更新每个节点的 $L_{i,j}^t$ and $R_{i,j}^t$
(14) 更新 $\hat x_1^N$
(15)　　if $R_{i,n + 1}^t > 0$ then ${{\hat x}_i} = 0$
(16)　　else ${{\hat x}_i} = 1$
(17) end while
(18) 提前停止准则：
(19)　　if (17) 成立 then
(20) 迭代终止
(21)　　else $t=t+1$
(22) 输出： $\hat u_1^N = \left( {{{\hat u}_1},{{\hat u}_2}, ··· ,{{\hat u}_N}} \right)$

下载: 导出CSV

| 显示表格

$\sum\limits_{t - X + 1}^t {\sum\limits_{i \in S} {\hat x_i^t} } \oplus \hat x{}_i^{t - 1} = 0$

(17)

4. 性能分析

采用二进制相移键控(Binary Phase Shift Keying, BPSK)调制，在二进制加性高斯白噪声(Binary-Input Additive White Gaussian Noise, BI-AWGN)信道下，对(1024, 512)极化码进行BP算法仿真，其中 $\alpha = 0.9375$ ，最大迭代次数设置为40次。

4.1 译码性能分析

如图5所示，当Q=128, X=2时，所提出的准则在误帧率和误码率上与40次固定迭代(fixed 40), WIB和FBER译码性能相似。如果Q降低到64，则需将X至少增加到3，以弥补性能损失。每当X增加1时，它将至少导致平均迭代次数上升一次。同样可观察到Q值越大，译码性能越好。然而，较高的Q值增加了计算复杂度。因此，可通过仿真选择合适的(X,Q)来权衡硬件复杂度和平均迭代次数。

图 5 不同迭代终止准则的极化码译码性能比较

下载: 全尺寸图片幻灯片

4.2 对迭代次数的分析

在相同的误码率条件下，比较不同迭代终止算法的平均迭代次数。如图6所示，在BER=1.48×10^–5, E_b/N₀=3.5 dB时，与40次固定迭代(fixed 40)的算法相比，G-Matrix准则可以减少87.96%的迭代，本文所提准则在Q=128和X=2时可以减少83.03%的迭代；当 $Q = 1024, X = 1$ 时，与G-Matrix相比，平均迭代次数上升了29.98%；当 $Q = 128, X = 2$ 和 $Q = 64,X = 3$ 时分别与WIB(n_WIB=128, M=6)和FBER(N_F=64, M=6)相比平均迭代次数减少了39.44%和27.67%。当检测位数相等时，所提准则比WIB和FBER需要更少的迭代。

图 6 不同迭代终止准则的平均迭代次数比较

下载: 全尺寸图片幻灯片

4.3 硬件结构

X-tolerance的硬件结构如图7所示。通过硬判决得到 $R_{{S_i},n + 1}^t$ 的符号；异或(XOR)用于计算 $\hat x_{{S_i}}^t \oplus \hat x_{{S_i}}^{t - 1}$ 。在第t次迭代中， ${D_t}$ 是与门(OR)的结果；Comp检测 $\left\{ {{D_t},{D_{t - 1}}, ··· ,{D_{t - X + 1}}} \right\}$ 是否等于0；当 ${E_t}$ 为0时终止译码。

图 7 X-tolerance的硬件结构

下载: 全尺寸图片幻灯片

图8中给出了(8, 4)极化码的BP译码流程。虚线部分表示处理单元的阶段和停止准则之间的数据依赖关系。采用X-tolerance时，在第t次迭代的第3个时钟中，译码器输出 $R_{t,4}^t,i \in \left[ N \right]$ ，然后确定 ${\hat x^t}$ 。接下来， ${\hat x^t}$ 和 ${\hat x^{t - 1}}$ 被发送到相等检测器。第5个时钟，计算X比较器的结果。如果满足X-tolerance，译码器将计算 $L_{i,1}^t,i \in [N]$ ，终止译码，否则继续下一次迭代。对于大多数具有实际长度 $(n \le 10000)$ 的极化码，相等检测器和X比较器的关键路径延迟总是小于PE^[7]。因此，X-tolerance不会增加整个译码器的关键路径延迟。此外，G-Matrix, WIB和FBER只能在得到 ${{\hat u}}$ 后开始早期停止准则的判决，由于译码器和早期停止准则并行运行，在得到早期停止准则的结果前，译码无法终止，这会导致额外的延迟和复杂度。如图8所示，在第t次迭代的第6个时钟中译码器计算输出 $L_{i,4}^t,i \in \left[ N \right]$ ，之后的第7个时钟其他准则才会开始判断是否终止译码，相对于X-tolerance会多出部分时钟译码延迟。当 $n > 2$ 时，X-tolerance不会导致额外的延迟，因为X-tolerance的检测在获得 ${{\hat u}}$ 之前已完成。

图 8 采用X-tolerance的BP译码流程

下载: 全尺寸图片幻灯片

4.4 计算复杂度和资源消耗分析

表1列出了一次迭代停止准则的计算复杂度。对于 ${\hat x_i},i \in S$ , X-tolerance使用Q个XOR操作来计算 $\hat x_i^t \oplus \hat x{}_i^{t - 1}$ 。同时，X-tolerance需要X+Q个OR操作和1个比较操作来检测连续X次迭代是否有变化。虽然X-tolerance消耗更多或操作，但因为没有加法操作，其具有最低的计算复杂度。表2比较了多种早期迭代停止准则在Stratix V 5SGXEA7N2F45C2上的综合结果，统一采用8 bit量化LLR。与其他迭代终止准则相比，X-tolerance可有效降低硬件消耗。在ALM方面，它减少了90%以上的资源消耗。与G-Matrix, WIB和FBER相比，X-tolerance可节省37.6%～97.2%的寄存器。

表 1 早期停止准则的计算复杂度比较

停止准则	G-Matrix	WIB	FBER	X-tolerance
停止准则	G-Matrix	WIB	FBER	Q=N/8	Q=N/16
加法运算	2N	M+2N/8	M+N/16	–	–
比较运算	3N	–	–	–	1
异或(XOR)	NlogN	N/8	N/16	N/8	N/16
或(OR)		–	–	X+N/8	X+N/16

下载: 导出CSV

| 显示表格

表 2 不同早期停止准则的综合结果

停止准则	G-Matrix	WIB	FBER	X-tolerance
停止准则	G-Matrix	WIB	FBER	Q=128 X=2	Q=64 X=3
ALMs	30265	1820	1260	50	27
Registers	3073	330	210	131	68

下载: 导出CSV

| 显示表格

5. 结束语

为了降低极化码置信度传播算法的译码延迟，减少迭代次数，本文提出一种基于码字估值的早期迭代停止准则。通过构造比较空间，只需检测码字估值 ${{\hat x}}$ 中的部分位置，进一步降低计算复杂度，且不会引入额外的延迟。仿真表明，当最大迭代次数为40，信噪比为3.5 dB时，与G-Matrix相比，X-tolerance平均迭代次数上升了29.98%，与WIB, FBER相比，X-tolerance平均迭代次数分别降低39.44%和27.67%。综合结果表明，与G-Matrix, WIB和FBER相比，X-tolerance可节省90%以上的ALM资源。

表 1 Guruswami-Sudan列表译码算法 ${\rm{ListDecode}}({\cal{C}},{{r}},t)$

输入：有限域 ${\mathbb{F}_q}$ ，曲线 ${\cal{X}}$ ，除子 $G = \alpha Q$ 和 $D$ ，接受向量 ${{r} } = ({r_1},{r_2}, ··· ,{r_n})$ 以及错误重量上界 $t$ 。
初始化：
(1) 设置表单 ${\Omega _r}: = \varnothing$ ；
(2) 由 $n,k,t$ 计算译码参数 $l$ ，要求 $l > \alpha$ ；一般地，设　　 $r = 1 + \dfrac{{(2g + \alpha )n - 2gt + \sqrt {{{((2g + \alpha )n - 2gt)}^2} - 4({g^2} - 1)({{(n - t)}^2} - \alpha n)} }}{{2{{(n - t)}^2} - \alpha n}}$ , $l = r(n - t) - 1$ ；
(3) 固定 ${\cal{L}}(lQ)$ 的一组极基 $\{ {\phi _{ {j_1} } }:1 \le {j_1} \le l - g + 1\}$ ，使得Q最多为 ${\phi _{{j_1}}}$ 的 ${j_1} + g - 1$ 次极点；
(4) 对任意 ${P_i}$ , $1 \le i \le n$ ，找 ${\cal{L}}(lQ)$ 的一组零基 $\{ {\psi _{ {j_3} } }:1 \le {j_3} \le l - g + 1\}$ ，使得 ${P_i}$ 为 ${\psi _{{j_3},{P_i}}}$ 重数(至少)为 ${j_3} - 1$ 的零点；
(5) 计算集合 $\{ {a_{ {P_i},{j_1},{j_3} } } \in {\mathbb{F}_q}:1 \le i \le n,1 \le {j_1},{j_3} \le l - g + 1\}$ ，使得对任意i和 ${j_1}$ ，都有 ${\phi _{{j_1}}} = {\Sigma _{{j_3}}}{a_{{P_i},{j_1},{j_3}}}{\psi _{{j_3},{P_i}}}$ 。
插值：　　令 $s = \dfrac{{l - g}}{\alpha }$ ，找非零多项式 $H \in {\cal{L}}(lQ)[T]$ ，它具有以下形式： $H[T] = \displaystyle\sum\limits_{ {j_2} = 0}^s {\displaystyle\sum\limits_{ {j_1} = 1}^{l - g + 1 - \alpha {j_2} } { {h_{ {j_1},{j_2} } }{\phi _{ {j_1} } }{T^{ {j_2} } } } }$ ；
其中，系数 ${h_{{j_1},{j_2}}} \in {\mathbb{F}_q}$ 满足：至少有一个 ${h_{{j_1},{j_2}}}$ 是非零的，且对任意 $i \in [n]$ ，和满足 ${j_3} + {j_4} \le r$ 的 ${j_3} \ge 1,{j_4} \ge 0$ ，有　　 $h_{{j_3},{j_4}}^{(i)} = \displaystyle\sum\limits_{{j_2} = {j_4}}^s {\displaystyle\sum\limits_{{j_1} = 1}^{l - g + 1 - \alpha {j_2}} {\left( \begin{array}{l} {j_2} \\ {j_4} \\ \end{array} \right)r_i^{{j_2} - {j_4}} \cdot {h_{{j_1},{j_2}}}{\alpha _{{x_i},{j_1},{j_3}}} = 0} }$
求根：
找到 $H[T]$ 的所有根 $h \in {\cal{L}}(\alpha Q) \subseteq {\cal{L}}(lQ)$ 。对每一个 $h$ ，检查是否对至少 $n - t$ 个 $i \in \{ 1,2, ··· ,n\}$ 有 $h({P_i}) = {r_i}$ ，即 $d({{r} },{{c} }) \le t$ 。如果成　　立，将 $h$ 加入 ${\Omega _r}$ 。
输出：码字列表 ${\Omega _r}$ 。

下载: 导出CSV

参考文献(68)

BERLEKAMP E R, MCELIECE R J, and VAN TILBORG H C A. On the inherent intractability of certain coding problems (Corresp.)[J]. IEEE Transactions on Information Theory, 1978, 24(3): 384–386. doi: 10.1109/TIT.1978.1055873

MCELIECE R J. A public-key cryptosystem based on algebraic coding theory[R]. DSN Progress Report 42–44, 1978: 114–116.

ELIAS P. List decoding for noisy channels[R]. Technical Report 335, 1957: 94–104.

GOLDREICH O and LEVIN L A. A hard-core predicate for all one-way functions[C]. The 21st Annual ACM Symposium on Theory of Computing, Seattle, USA, 1989: 25–32. doi: 10.1145/73007.73010.

SUDAN M. Decoding of Reed Solomon codes beyond the error-correction bound[J]. Journal of Complexity, 1997, 13(1): 180–193. doi: 10.1006/jcom.1997.0439

GURUSWAMI V and SUDAN M. Improved decoding of Reed-Solomon and algebraic-geometry codes[J]. IEEE Transactions on Information Theory, 1999, 45(6): 1757–1767. doi: 10.1109/18.782097

GURUSWAMI V and SUDAN M. On representations of algebraic-geometric codes for list decoding[C]. The 8th Annual European Symposium, Saarbrücken, Germany, 2000: 244–255. doi: 10.1007/3-540-45253-2_23.

GOPALAN P, KLIVANS A R, and ZUCKERMAN D. List-decoding Reed-Muller codes over small fields[C]. The 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, 2008: 265–274. doi: 10.1145/1374376.1374417.

SUDAN M. List decoding: Algorithms and applications[C]. International Conference IFIP TCS 2000 Sendai, Japan, 2000: 25–41. doi: 10.1007/3-540-44929-9_3.

BLUM M and MICALI S. How to generate cryptographically strong sequences of pseudo random bits[C]. The 23rd Annual Symposium on Foundations of Computer Science, Chicago, USA, 1982: 112–117. doi: 10.1109/SFCS.1982.72.

AKAVIA A, GOLDWASSER S, and SAFRA S. Proving hard-core predicates using list decoding[C]. The 44th Annual IEEE Symposium on Foundations of Computer Science, Cambridge, USA, 2003: 146–157. doi: 10.1109/SFCS.2003.1238189.

王明强, 庄金成. 基于列表译码方法在查询访问模型下含错学习问题的分析[J]. 电子与信息学报, 2020, 42(2): 322–326. doi: 10.11999/JEIT190624

WANG Mingqiang and ZHUANG Jincheng. Analysis of learning with errors in query access model: A list decoding approach[J]. Journal of Electronics &Information Technology, 2020, 42(2): 322–326. doi: 10.11999/JEIT190624

MORILLO P and RÀFOLS C. The security of all bits using list decoding[C]. The 12th International Conference on Practice and Theory in Public Key Cryptography, Irvine, USA, 2009: 15–33.

谢小容, 吕克伟, 王鲲鹏. ax + b mod p比特安全的列表译码证明[J]. 系统科学与数学, 2012, 32(11): 1366–1376.

XIE Xiaorong, LÜ Kewei, and WANG Kunpeng. Proving the security of all bits of ax + b mod p using list decoding[J]. Journal of Systems Science and Mathematical Sciences, 2012, 32(11): 1366–1376.

DUC A and JETCHEV D. Hardness of computing individual bits for one-way functions on elliptic curves[C]. The 32nd Annual Cryptology Conference, Santa Barbara, USA, 2012: 832–849. doi: 10.1007/978-3-642-32009-5_48.

FAZIO N, GENNARO R, PERERA I M, et al. Hard-core predicates for a Diffie-Hellman problem over finite fields[C]. The 33rd Annual Cryptology Conference, Santa Barbara, USA, 2013: 148–165. doi: 10.1007/978-3-642-40084-1_9.

WANG Mingqiang, ZHAN Tao, and ZHANG Haibin. Bit security of the CDH problems over finite fields[C]. The 22nd International Conference on Selected Areas in Cryptography, Sackville, 2015: 441–461.

KAWACHI A and YAMAKAMI T. Quantum hardcore functions by complexity-theoretical quantum list decoding[C]. The 33rd International Colloquium on Automata, Languages and Programming, Venice, 2006: 216–227.

BONEH D and FRANKLIN M. An efficient public key traitor tracing scheme[C]. The 19th Annual International Cryptology Conference Santa Barbara, Santa Barbara, USA, 1999: 338–353. doi: 10.1007/3-540-48405-1_22.

FERNANDEZ M and SORIANO M. Identification of traitors in algebraic-geometric traceability codes[J]. IEEE Transactions on Signal Processing, 2004, 52(10): 3073–3077. doi: 10.1109/TSP.2004.833858

FAZIO N, NICOLOSI A, and PHAN D H. Traitor tracing with optimal transmission rate[C]. The 10th International Conference on Information Security, Valparaíso, Chile, 2007: 71–88. doi: 10.1007/978-3-540-75496-1_5.

PHAN D H. Traitor tracing for stateful pirate decoders with constant ciphertext rate[C]. The 1st International Conference on Cryptology in Vietnam, Hanoi, Vietnam, 2006: 354–365. doi: 10.1007/11958239_24.

SIRVENT T. Traitor tracing scheme with constant ciphertext rate against powerful pirates[EB/OL]. https://eprint.iacr.org/2006/383, 2019.

SILVERBERG A, STADDON J, and WALKER J L. Efficient traitor tracing algorithms using list decoding[C]. The 7th International Conference on the Theory and Application of Cryptology and Information Security Gold Coast, Gold Coast, Australia, 2001: 175–192. doi: 10.1007/3-540-45682-1_11.

SILVERBERG A, STADDON J, and WALKER J L. Applications of list decoding to tracing traitors[J]. IEEE Transactions on Information Theory, 2003, 49(5): 1312–1318. doi: 10.1109/TIT.2003.810630

BARBIER M and BARRETO P S L M. Key reduction of McEliece's cryptosystem using list decoding[C]. 2011 IEEE International Symposium on Information Theory Proceedings, St. Petersburg, Russia, 2011: 2681–2685. doi: 10.1109/ISIT.2011.6034058.

KIAYIAS A and YUNG M. Secure games with polynomial expressions[C]. The 28th International Colloquium on Automata, Languages, and Programming, Crete, Greece, 2001: 939–950. doi: 10.1007/3-540-48224-5_76.

KIAYIAS A and YUNG M. Polynomial reconstruction based cryptography[C]. The 8th Annual International Workshop on Selected Areas in Cryptography, Toronto, Canada, 2001: 129–133. doi: 10.1007/3-540-45537-X_10.

KIAYIAS A and YUNG M. Cryptanalyzing the polynomial-reconstruction based public-key system under optimal parameter choice[C]. The 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, 2004: 401–416. doi: 10.1007/978-3-540-30539-2_28.

KIAYIAS A and YUNG M. Cryptographic hardness based on the decoding of Reed-Solomon codes[J]. IEEE Transactions on Information Theory, 2008, 54(6): 2752–2769. doi: 10.1109/TIT.2008.921876

CHENG Qi and WAN Daqing. On the list and bounded distance decodibility of Reed-Solomon codes[C]. The 45th Annual IEEE Symposium on Foundations of Computer Science, Rome, Italy, 2004: 335–341. doi: 10.1109/FOCS.2004.46.

CHENG Qi. On the bounded sum-of-digits discrete logarithm problem in finite fields[C]. The 24th Annual International Cryptology Conference, Santa Barbara, USA, 1999: 201–212. doi: 10.1007/978-3-540-28628-8_12.

WANG Pengwei and SAFAVI-NAINI R. Interactive message transmission over adversarial wiretap channel Ⅱ[C]. IEEE INFOCOM 2017-IEEE Conference on Computer Communications, Atlanta, USA, 2017: 1–9. doi: 10.1109/INFOCOM.2017.8057120.

ZHANG Fangguo and LIU Shengli. Solving ECDLP via list decoding[EB/OL]. https://eprint.iacr.org/2018/795.pdf, 2019.

MÁRQUEZ-CORBELLA I and TILLICH J P. Using Reed-Solomon codes in the (U|U+V) construction and an application to cryptography[C]. 2016 IEEE International Symposium on Information Theory, Barcelona, Spain, 2016: 930–934. doi: 10.1109/ISIT.2016.7541435.

ZHANG Fangguo and ZHANG Zhuoran. ECC²: Error correcting code and elliptic curve based cryptosystem[C]. The 11th International Symposium Cyberspace Safety and Security, Guangzhou, China, 2019: 214–229.

ZHANG F, ZHANG Z, and GUAN P. ECC²: Error correcting code and elliptic curve based cryptosystem (full version)[J]. Submit to Information Science.

GOPPA V D. Codes on algebraic curves[J]. Soviet Math Dokl, 1981, 24: 170–172.

JANWA H and MORENO O. McEliece public key cryptosystems using algebraic-geometric codes[J]. Designs, Codes and Cryptography, 1996, 8(3): 293–307. doi: 10.1023/A:1027351723034

HØHOLDT T, VAN LINT J H, and PELLIKAAN R. Algebraic Geometry Codes[M]. LUISA B. Handbook of Coding Theory. Amsterdam: Elsevier Science Inc., 1998: 871–961.

SHOKROLLAHI M A and WASSERMAN H. List decoding of algebraic-geometric codes[J]. IEEE Transactions on Information Theory, 1999, 45(2): 432–437. doi: 10.1109/18.748993

WU Xinwen and SIEGEL P H. Efficient root-finding algorithm with application to list decoding of algebraic-geometric codes[J]. IEEE Transactions on Information Theory, 2001, 47(6): 2579–2587. doi: 10.1109/18.945273

TRIFONOV P. On the root finding step in list decoding of folded Reed-Solomon codes[EB/OL]. http://arxiv.org/abs/1103.1958v3, 2019.

MURALIDHARA V N and SEN S. Improvements on the Johnson bound for Reed-Solomon codes[J]. Discrete Applied Mathematics, 2009, 157(4): 812–818. doi: 10.1016/j.dam.2008.06.014

GURUSWAMI V and XING Chaoping. List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the singleton bound[C]. The 45th Annual ACM Symposium on Theory of Computing, Palo Alto, USA, 2013: 843–852. doi: 10.1145/2488608.2488715.

NAOR M and PINKAS B. Oblivious transfer and polynomial evaluation[C]. The 21st Annual ACM Symposium on Theory of Computing, Atlanta, USA, 1999: 245–254. doi: 10.1145/301250.301312.

BLEICHENBACHER D, KIAYIAS A, and YUNG M. Decoding of interleaved Reed Solomon codes over noisy data[C]. The 30th International Colloquium on Automata, Languages, and Programming, Eindhoven, The Netherlands, 2003: 97–108. doi: 10.1007/3-540-45061-0_9.

AUGOT D and FINIASZ M. A public key encryption scheme based on the polynomial reconstruction problem[C]. International Conference on the Theory and Applications of Cryptographic Techniques, Warsaw, Poland, 2003: 229–240. doi: 10.1007/3-540-39200-9_14.

CORON J S. Cryptanalysis of a public-key encryption scheme based on the polynomial reconstruction problem[C]. The 7th International Workshop on Theory and Practice in Public Key Cryptography, Singapore, 2004: 14–27. doi: 10.1007/978-3-540-24632-9_2.

JUSTESEN J and HOHOLDT T. Bounds on list decoding of MDS codes[J]. IEEE Transactions on Information Theory, 2001, 47(4): 1604–1609. doi: 10.1109/18.923744

NIEBUHR R, CAYREL P L, BULYGIN S, et al. On lower bounds for information set decoding over F_q[C]. The 2nd International Conference on Symbolic Computation and Cryptography - SCC 2010, Egham, UK, 2010: 143–157.

FAUGÈRE J C, OTMANI A, PERRET L, et al. Algebraic cryptanalysis of mcEliece variants with compact keys[C]. The 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, French Riviera, France, 2010: 279–298. doi: 10.1007/978-3-642-13190-5_14.

OZAROW L H and WYNER A D. Wire-tap channel Ⅱ[C]. EUROCRYPT 1984 A Workshop on the Theory and Application of Cryptographic Techniques, Paris, France, 1984: 33–50. doi: 10.1007/3-540-39757-4_5.

TAL I and VARDY A. List decoding of polar codes[J]. IEEE Transactions on Information Theory, 2015, 61(5): 2212–2216. doi: 10.1109/TIT.2015.2410251

王琼, 罗亚洁, 李思舫. 基于分段循环冗余校验的极化码自适应连续取消列表译码算法[J]. 电子与信息学报, 2019, 41(7): 1572–1578. doi: 10.11999/JEIT180716

WANG Qiong, LUO Yajie, and LI Sifang. Polar adaptive successive cancellation list decoding based on segmentation cyclic redundancy check[J]. Journal of Electronics &Information Technology, 2019, 41(7): 1572–1578. doi: 10.11999/JEIT180716

王美洁, 郭锐. 极化码低时延列表连续删除译码算法[J]. 通信技术, 2016, 49(3): 270–273. doi: 10.3969/j.issn.1002-0802.2016.03.004

WANG Meijie and GUO Rui. Reduced-latency successive cancellation list decoding for polar code[J]. Communications Technology, 2016, 49(3): 270–273. doi: 10.3969/j.issn.1002-0802.2016.03.004

HOOSHMAND R, SHOOSHTARI M K, EGHLIDO T, et al. Reducing the key length of McEliece cryptosystem using polar codes[C]. The 11th International ISC Conference on Information Security and Cryptology, Tehran, Iran, 2014: 104–108. doi: 10.1109/ISCISC.2014.6994031.

SHRESTHA S R and KIM Y S. New McEliece cryptosystem based on polar codes as a candidate for post-quantum cryptography[C]. The 14th International Symposium on Communications and Information Technologies, Incheon, South Korea, 2014: 368–372. doi: 10.1109/ISCIT.2014.7011934.

BARDET M, CHAULET J, DRAGOI V, et al. Cryptanalysis of the McEliece public key cryptosystem based on polar codes[C]. The 7th International Workshop, Fukuoka, Japan, 2016: 118–143. doi: 10.1007/978-3-319-29360-8_9.

DRIENCOURT Y and MICHON J F. Elliptic codes over fields of characteristics 2[J]. Journal of Pure and Applied Algebra, 1987, 45(1): 15–39. doi: 10.1016/0022-4049(87)90081-8

CHENG Qi. Hard problems of algebraic geometry codes[J]. IEEE Transactions on Information Theory, 2008, 54(1): 402–406. doi: 10.1109/TIT.2007.911213

SIDELNIKOV V M and SHESTAKOV S O. On insecurity of cryptosystems based on generalized Reed-Solomon codes[J]. Discrete Mathematics and Applications, 1992, 2(4): 439–444.

MINDER L. Cryptography based on error correcting codes[D]. [Ph.D. dissertation], EPFL, 2007.

FAURE C and MINDER L. Cryptanalysis of the McEliece cryptosystem over hyperelliptic codes[C]. The 11th international workshop on Algebraic and Combinatorial Coding Theory, Pamporovo, Bulgaria, 2008: 99–107.

COUVREUR A, MÁRQUEZ-CORBELLA I, and PELLIKAAN R. A polynomial time attack against algebraic geometry code based public key cryptosystems[C]. 2014 IEEE International Symposium on Information Theory, Honolulu, USA, 2014: 1446–1450. doi: 10.1109/ISIT.2014.6875072.

COUVREUR A, MÁRQUEZ-CORBELLA I, and PELLIKAAN R. Cryptanalysis of McEliece cryptosystem based on algebraic geometry codes and their subcodes[J]. IEEE Transactions on Information Theory, 2017, 63(8): 5404–5418. doi: 10.1109/TIT.2017.2712636

PELLIKAAN R. On decoding by error location and dependent sets of error positions[J]. Discrete Mathematics, 1992, 106-107: 369–381. doi: 10.1016/0012-365X(92)90567-Y

PELLIKAAN R. On the existence of error-correcting pairs[J]. Journal of Statistical Planning and Inference, 1996, 51(2): 229–242. doi: 10.1016/0378-3758(95)00088-7

施引文献

期刊类型引用(3)

1.	高珍，张国伟. 改进区块链的移动网络敏感数据防篡改仿真. 计算机仿真. 2023(03): 409-412+430 . 百度学术
2.	文豪，曹阳，党宇超. 无线光通信下极化码DNN-NOMS译码方法研究. 红外与激光工程. 2022(05): 262-272 . 百度学术
3.	袁建国，张瑞，张丰果，李志伟，黄胜. CRC辅助PC-polar码的新颖编码算法. 重庆邮电大学学报(自然科学版). 2022(06): 929-934 . 百度学术

其他类型引用(4)

资源附件(0)

访问统计

表(1)

计量

文章访问数: 3617
HTML全文浏览量: 1264
PDF下载量: 190
被引次数: 7

1. 引言
2. 基本理论
2.1 极化码
2.2 BP译码算法
3. 提出的早期迭代停止准则
3.1 X-tolerance早期迭代停止准则
3.2 比较空间的构造
4. 性能分析
4.1 译码性能分析
4.2 对迭代次数的分析
4.3 硬件结构
4.4 计算复杂度和资源消耗分析
5. 结束语

姓名
邮箱
手机号码
标题
留言内容
验证码

留言板

列表译码在密码中的应用综述

doi: 10.11999/JEIT190851

通讯作者:
张方国　isszhfg@mail.sysu.edu.cn

计量

Survey on Applications of List Decoding to Cryptography

1. 引言

2. 基本理论

2.1 极化码

2.2 BP译码算法

3. 提出的早期迭代停止准则

3.1 X-tolerance早期迭代停止准则

3.2 比较空间的构造

4. 性能分析

4.1 译码性能分析

4.2 对迭代次数的分析

4.3 硬件结构

4.4 计算复杂度和资源消耗分析

5. 结束语

期刊类型引用(3)

其他类型引用(4)

计量

目录

1. 引言

2. 基本理论

2.1 极化码

2.2 BP译码算法

3. 提出的早期迭代停止准则

3.1 X-tolerance早期迭代停止准则

3.2 比较空间的构造

4. 性能分析

4.1 译码性能分析

4.2 对迭代次数的分析

4.3 硬件结构

4.4 计算复杂度和资源消耗分析

5. 结束语

留言板

列表译码在密码中的应用综述

doi: 10.11999/JEIT190851

通讯作者: 张方国 isszhfg@mail.sysu.edu.cn

计量

出版历程

Survey on Applications of List Decoding to Cryptography

1. 引言

2. 基本理论

2.1 极化码

2.2 BP译码算法

3. 提出的早期迭代停止准则

3.1 X-tolerance早期迭代停止准则

3.2 比较空间的构造

4. 性能分析

4.1 译码性能分析

4.2 对迭代次数的分析

4.3 硬件结构

4.4 计算复杂度和资源消耗分析

5. 结束语

期刊类型引用(3)

其他类型引用(4)

计量

出版历程

目录

1. 引言

2. 基本理论

2.1 极化码

2.2 BP译码算法

3. 提出的早期迭代停止准则

3.1 X-tolerance早期迭代停止准则

3.2 比较空间的构造

4. 性能分析

4.1 译码性能分析

4.2 对迭代次数的分析

4.3 硬件结构

4.4 计算复杂度和资源消耗分析

5. 结束语

通讯作者:
张方国　isszhfg@mail.sysu.edu.cn