改进的Type-1型广义Feistel结构的量子攻击及其在分组密码CAST-256上的应用

倪博煜; 董晓阳

doi:10.11999/JEIT190633

改进的Type-1型广义Feistel结构的量子攻击及其在分组密码CAST-256上的应用

doi: 10.11999/JEIT190633

倪博煜^{1, 2},
董晓阳^3, ,

1.
山东大学密码技术与信息安全教育部重点实验室济南 250100
2.
山东大学网络空间安全学院青岛 266237
3.
清华大学高等研究院北京 100084

基金项目: 国家重点研发计划(2017YFA0303903)，国家自然科学基金(61902207)，国家密码发展基金(MMJJ20180101, MMJJ20170121)

详细信息

作者简介:
董晓阳：男，1988年生，助理研究员。研究方向为对称密码算法的安全性分析与设计

通讯作者:
董晓阳　xiaoyangdong@tsinghua.edu.cn

中图分类号: TN918; TP309
计量
- 文章访问数: 3481
- HTML全文浏览量: 1068
- PDF下载量: 149
- 被引次数: 10
出版历程
- 收稿日期: 2019-08-26
- 修回日期: 2019-11-26
- 网络出版日期: 2019-11-29
- 刊出日期: 2020-02-19

Improved Quantum Attack on Type-1 Generalized Feistel Schemes and Its Application to CAST-256

Boyu NI^{1, 2},
Xiaoyang DONG^{3
, ,}

1.
Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan 250100, China
2.
School of Cyber Science and Technology, Shandong University, Qingdao 266237, China
3.
Institute for Advanced Study, Tsinghua University, Beijing 100084, China

Funds: The National Key Research and Development Program of China (2017YFA0303903), The National Natural Science Foundation of China (61902207), The National Cryptography Development Fund (MMJJ20180101, MMJJ20170121)

摘要

摘要: 广义Feistel结构(GFS)是设计对称密码算法的重要基础结构之一，其在经典计算环境中受到了广泛的研究。但是，量子计算环境下对GFS的安全性评估还相当稀少。该文在量子选择明文攻击(qCPA)条件下和量子选择密文攻击(qCCA)条件下，分别对Type-1 GFS进行研究，给出了改进的多项式时间量子区分器。在qCPA条件下，给出了3d – 3轮的多项式时间量子区分攻击，其中 $d(d \ge 3)$ 是Type-1 GFS的分支数，攻击轮数较之前最优结果增加 $d - 2$ 轮。得到更好的量子密钥恢复攻击，即相同轮数下攻击的时间复杂度降低了 ${2^{(d - 2)n/2}}$ 。在qCCA条件下，对于Type-1 GFS给出了 $3d - 2$ 轮的多项式时间量子区分攻击，比之前最优结果增加了 $d - 1$ 轮。该文将上述区分攻击应用到CAST-256分组密码中，得到了12轮qCPA多项式时间量子区分器，以及13轮qCCA多项式时间量子区分器，该文给出19轮CAST-256的量子密钥恢复攻击。
- 分组密码 /
- 广义Feistel结构 /
- 量子攻击 /
- CAST-256加密算法
Abstract: Generalized Feistel Schemes (GFS) are important components of symmetric ciphers, which have been extensively researched in classical setting. However, the security evaluations of GFS in quantum setting are rather scanty. In this paper, more improved polynomial-time quantum distinguishers are presented on Type-1 GFS in quantum Chosen-Plaintext Attack (qCPA) setting and quantum Chosen-Ciphertext Attack (qCCA) setting. In qCPA setting, new quantum polynomial-time distinguishers are proposed on $3d - 3$ round Type-1 GFS with branches $d \ge 3$ , which gain $d - 2$ more rounds than the previous distinguishers. Hence, key- recovery attacks can be obtained, whose time complexities gain a factor of ${2^{\frac{{\left( {d - 2} \right)n}}{2}}}$ . In qCCA setting, $3d - 3$ round quantum distinguishers can be obtained on Type-1 GFS, which gain $d-1$ more rounds than the previous distinguishers. In addition, given some quantum attacks on CAST-256 block cipher. 12-round and 13-round polynomial-time quantum distinguishers are obtained in qCPA and qCCA settings, respectively. Hence, the quantum key-recovery attack on 19-round CAST-256 is derived.
- Block cipher /
- Generalized Feistel Scheme (GFS) /
- Quantum attack /
- CAST-256 cipher algorithm

HTML全文

1. 引言

极化码是目前唯一一种通过理论证明能够达到香农极限的信道编码方案^[1]。由于极化码具有低复杂度的编译码结构和优良的纠错性能，其已成为5G增强移动宽带场景(Enhance Mobile Broad Band, EMBB)中控制信道的编码方案。当极化码的码长趋近于无穷大时，串行抵消译码算法(Successive Cancellation, SC)被证明是一种可使极化码的纠错性能达到信道容量的译码算法。但SC译码算法在有限码长情况下的译码性能并不理想，并且具有较高的译码时延。

为此，研究者提出了串行抵消翻转(Successive Cancellation Flip, SC-Flip)译码算法^[2]。该算法在首次SC译码失败后，继续尝试多次SC译码，选择易错的候选比特(Candidate Bit, CB)进行翻转。Chandesris等人^[3]提出了一种动态SC-Flip(Dynamic-SC-Flip, D-SC-Flip)译码算法。该算法通过一种新的度量准则来权衡候选比特的译码顺序和决策对数似然比(Log-Likelihood Ratio, LLR)对候选比特可靠性的影响，动态构建及更新候选翻转比特集合，同时翻转多位错误比特。文献[4]通过比较LLR计算得到的错误概率与高斯近似(Gaussian Approximation , GA)计算得到的错误概率，以此来缩小D-SC-Flip译码算法的候选翻转比特集合。文献[5]通过优化候选翻转集合的构造，减少D-SC-Flip译码算法的搜索复杂度。文献[6]提出了基于门限的候选翻转集合构造算法，进一步提升了译码性能。文献[7]提出了一种新型的SC-Flip译码算法，同时利用奇偶校验(Parity Check, PC)和循环冗余校验(Cyclic Redundancy Check, CRC)的校验作用，相比于CRC辅助的SC-Flip译码算法，获得了更好的性能和复杂度的折中。

为了降低SC算法的译码时延，文献[8]提出了简化的SC(Simplified SC, SSC)译码算法。SSC译码算法能够在Rate0节点以及Rate1节点直接进行硬判决译码，有效地降低了译码时延。随后，Sarkis等人^[9]进一步提出了单奇偶校验(Single Parity Check, SPC)以及重复(REPetition, REP)节点，并提供了这两种特殊节点的直接译码方法，使得改进后的快速简化串行抵消(Fast-Simplified Successive Cancellation, Fast-SSC)译码算法相较于SC译码算法在不损失纠错性能的前提下极大地降低译码时延。进一步地，文献[10]对Fast-SSC译码算法中的各种特殊节点做了归纳总结，提出了更具一般性的Type-I, Type-II, Type-III, Type-IV以及Type-V节点，通过对这5种节点直接译码，从而极大地改善SC译码算法的译码时延。

Giard等人^[11]将Fast-SSC译码算法与SC-Flip译码算法相结合，提出了Fast-SSC-Flip译码算法。Fast-SSC-Flip译码算法允许在初始Fast-SSC译码失败之后，继续尝试执行最多 ${T_{{\rm{max}}}}$ 次Fast-SSC译码算法，且每次执行Fast-SSC译码时选择候选翻转比特集合中的某个比特进行翻转。然而传统Fast-SSC-Flip译码算法在对SPC节点进行翻转译码时会有轻微的性能损失，为此研究者提出了一种新的Fast-SSC-Flip^[12](New-Fast-SSC-Flip, N-Fast-SSC-Flip)译码算法，能取得优异的译码性能。同一作者在文献[13]中提出了一种适用于衡量Fast-SSC译码过程中候选比特可靠性的度量准则，该度量准则能够更精确地定位到首位译码错误比特。文献[14] 提出了基于易错比特列表和分段CRC校验的Fast-SSC-Flip译码算法，进一步提升译码性能。文献[15,16]提出了两种增强型的多比特翻转Fast-SSC译码算法来纠正Fast-SSC译码过程中的多位译码错误比特。

候选翻转比特集合是影响Fast-SSC-Flip算法译码复杂度以及译码性能的关键因素之一，集合大小影响候选比特的搜索效率以及复杂度。当前Fast-SSC-Flip译码算法搜索候选翻转比特的范围与全部信息比特构成的集合的维度一致。因此，本文在CS的基础上提出了关键翻转集合(Critical Flip Set, CFS)，将Fast-SSC-Flip译码中候选比特搜索范围定位到CFS中，并提出了基于CFS的Fast-SSC-Flip译码算法，从而降低传统Fast-SSC-Flip译码算法的候选翻转比特集合大小，减小搜索复杂度。

2. Fast-SSC-Flip译码算法

2.1 Fast-SSC译码算法

一个 $(N,K) = (8,4)$ 的极化码SC译码算法可以用如所示的二进制译码树表示，其中 $N$ 表示极化码的码长， $K$ 表示信息序列的长度，中白色叶节点表示冻结比特，黑色叶节点表示信息比特。每一个节点 $v$ 都会收到来自父节点提供的LLR向量值 ${{\boldsymbol{\alpha}} _v}{\text{ = }}\left\{ {\left. {\alpha _v^1,\alpha _v^2,\cdots,\alpha _v^{{2^S}}} \right\}} \right.$ ，其中 $S$ 表示节点 $v$ 所在的高度。每一层的非叶节点都会计算左子节点的LLR值 ${{\boldsymbol{\alpha}} _l} = {\text{ }}\left\{ {\left. {\alpha _l^1,\alpha _l^2,\cdots,\alpha _l^{{2^{S - 1}}}} \right\}} \right.$ 及右子节点的LLR值 ${{\boldsymbol{\alpha}} _r}{\text{ = }}\left\{ {\left. {\alpha _r^1,\alpha _r^2,\cdots,\alpha _r^{{2^{S - 1}}}} \right\}} \right.$ ，两组值分别传入左右子节点中并保存。

图 1

$(N,K) = (8,4)$ 的极化码SC译码树

下载: 全尺寸图片幻灯片

图1所示的极化码SC译码树利用Rate0，Rate1，REP以及SPC节点进行剪枝之后，可以得到如图2所示的Fast-SSC译码树。Fast-SSC译码树相较于最初的SC译码树而言，其高度已经大大降低，因此深度优先遍历的效率可以得到提升，相应的译码时延也会降低。

图 2

$(N,K) = (8,4)$ 的极化码Fast-SSC译码树

下载: 全尺寸图片幻灯片

Rate0节点表示该节点有连续 ${2^S}$ 个比特为冻结比特，因此将该节点的所有码字比特硬判决为全0比特；Rate1节点表示该节点有连续 ${2^S}$ 个比特为信息比特，在该节点直接利用硬判决方法进行译码。REP节点仅仅只有最右侧的叶节点是信息比特，而其余的叶节点全是冻结比特。Fast-SSC译码算法在REP节点直接利用最大似然译码算法进行译码。SPC节点是指在以该节点为根节点的译码子树中，只有最左侧的叶节点是冻结比特，其余的叶节点全是信息比特。同理，Fast-SSC可以直接在SPC节点进行硬判决(Hard Decision, HD)，译码输出结果为

${{\boldsymbol{\beta}} }_{v}[i]=\left\{\begin{aligned} &\text{HD}[i]\oplus p, \text{ }i={i}_{\epsilon } \\ &\text{HD}[i],\qquad 其他 \end{aligned}\right.$

(1)

其中， ${\rm{HD}}\left[ i \right]$ 表示根据SPC节点内的第 $i$ 个比特的LLR值进行硬判决，判决方式如式(2)所示； $p$ 表示SPC节点内所有比特的译码估计值的总和，计算方式如式(3)所示； ${i_\varepsilon }$ 表示SPC节点内最不可靠的一位信息位的索引位置，选择方法如式(4)所示

$\qquad \text{HD}[i]=\left\{\begin{array}{ll}0, & {\alpha }_{v}[i]\ge 0 \\ 1, & 其他 \end{array}\right.$

(2)

$\qquad p = \sum\limits_i {{\text{HD}}[i]}$

(3)

$\qquad {i_\varepsilon } = \mathop {\arg }\limits_{} \mathop {\min }\limits_i \left| {{{\boldsymbol{\alpha}} _v}[i]} \right|$

(4)

2.2 Fast-SSC-Flip译码算法

Fast-SSC-Flip算法通过找到Fast-SSC译码中不可靠的比特加入到候选翻转比特集合中，并在额外译码中尝试逐次翻转不可靠的比特，直至译码输出正确结果或者达到设置的最大额外尝试译码次数 ${T_{{\rm{max}}}}$ 。

在衡量Fast-SSC译码过程中候选比特可靠性时，需要根据不同节点类型分别计算各个节点内候选比特的可靠性。由于Rate0节点内包含的所有比特全是冻结比特，这些冻结比特在接收端和发送端也被假设是已知的。因此本文在构建候选翻转比特集合时，仅考虑Rate1，REP以及SPC 3种节点内的信息比特。

Rate1节点内的任意第 $i$ 个CB的可靠性度量计算方式为

${\lambda _i} = \left. {\left| {{{\boldsymbol{\alpha}} _v}[i]} \right.} \right|{\text{ }}$

(5)

当需要翻转的比特位于该节点内时，相应位置的比特进行翻转。

REP节点内仅含有一个信息比特，即在该节点内有且仅有1个CB，且该CB位于末尾位置。该CB的可靠性度量计算方式为

${\lambda _i} = \left| {\left. {\sum\limits_{i = 0}^{{N_v} - 1} {{{\boldsymbol{\alpha}} _v}[i]} } \right|} \right.$

(6)

其中， ${N_v}$ 表示该节点的长度，即包含冻结比特以及信息比特的总数量。当需要翻转的比特位于REP节点内时，该节点内的末尾比特进行翻转。

SPC节点内CB的可靠性度量计算及其无损翻转译码方法为

${\lambda }_{i}=|{{\boldsymbol{\alpha}} }_{v}[i]|+(1-p)\cdot \varepsilon ,\text{ }\forall 0\le i < {N}_{v}-1\text{ and }i\ne {i}_{\epsilon }$

(7)

其中， $p$ 以及 ${i_\varepsilon }$ 计算方式参见式(3)和式(4)， $\varepsilon$ 表示节点内最不可靠的比特的决策LLR值，可用式(8)计算

$\varepsilon = \min (|{{\boldsymbol{\alpha}} _v}|)$

(8)

当需要翻转的比特位于SPC节点时，节点内相应位置的比特以及 ${i_\varepsilon }$ 处的比特(固定翻转位)同时进行翻转。根据上述SPC节点的无损翻转译码方法，若SPC节点需要执行翻转译码，则 ${i_\varepsilon }$ 处的候选比特必然会被执行翻转译码。因此本文仅考虑SPC节点内除 ${i_\varepsilon }$ 处的比特外的所有比特作为候选比特。

在Fast-SSC-Flip译码算法中，无论是计算候选比特的度量值，还是选择不可靠的候选比特执行翻转译码，都与候选翻转比特集合的大小相关。然而大部分现存文献中的Fast-SSC-Flip算法的候选翻转比特集合的大小都等于信息比特集合的大小，因此若能有效缩小候选翻转比特集合的大小，则可以有效减少度量值计算以及排序复杂度，并且可以提升候选比特的搜索效率。为此，本文利用极化码的生成矩阵得到与CS中信息比特相应的码字比特，并用这些码字比特构建关键翻转集合CFS作为候选翻转比特集合。从而降低Fast-SSC-Flip译码算法的候选翻转比特集合大小，减小搜索复杂度。

3. Fast-SSC译码算法中CS构造及其有效性

为了降低Fast-SSC-Flip译码算法搜索候选翻转比特的复杂度，一种直接的思想是缩小译码过程中首位错误比特的搜索范围，文献[16]提出的关键集合CS能够将SC译码算法中首位错误比特定位到CS中，CS在SC译码算法中有极大概率包含首位错误比特。然而由于Fast-SSC并不是在SC译码树的叶节点得到译码信息比特值，而是在Fast-SSC译码树的各种特殊节点得到相应的码字比特序列。故本节首先研究了CS在Fast-SSC译码算法中的有效性。

3.1 CS构造方法

构建CS的方法简述为：首先将SC译码树裁剪为SSC译码树，裁剪后的译码树中编码速率为1的叶节点(等效于Rate1节点)被称为极化子块，每个子块都是一个仅包含信息比特序列的极化码。将所有子块中的首位比特依次放入到初始化为空集的CS中完成CS的构建。CS详细的构建方法如算法1所示。

算法1　关键集合CS构建
输入：信息比特索引集合 ${\boldsymbol{I}}$
输出：关键集合CS
(1) 根据集合 ${\boldsymbol{I}}$ 构建裁剪后的SSC译码树，并初始化CS为空集
(2) 将每个子块的首位比特放入到CS中

下载: 导出CSV

| 显示表格

3.2 CS有效性

本节主要验证CS集合在Fast-SSC译码算法下是否能够有效地包含Fast-SSC译码算法的首位错误比特。本节的仿真参数如下：极化码编码方式为非系统编码，接收端采用Fast-SSC译码算法。设置极化码码长 $N = 1\;024$ ，信息比特长度 $K = 512$ ，码率 $R = 0.5$ ，蒙特卡罗仿真次数为 ${T_{{\rm{sim}}}} = {10^6}$ 。

仿真结果见表1，“译码错误帧数”表示采用Fast-SSC译码得到的错误译码总帧数；“首错在CS中”表示Fast-SSC译码中的首位错误信息比特在由算法1构造的CS中的总帧数；“准确性”由两者的比值得到；“CS的维度”表示CS集合的大小。

表 1

${\boldsymbol{N}} = {\boldsymbol{1\;024}}$ ,

${\boldsymbol{K}} = {\boldsymbol{512}}$ ,

${\boldsymbol{{T_{{\rm{sim}}}} = {10^6}}}$ 时CS的有效性验证

	SNR (dB)
	0.5	1.0	1.5	2.0	2.5	3.0
译码错误帧数	947 225	708 607	320 935	81 666	12 462	1 057
首错在CS中	942 203	707 058	320 717	81 652	12 462	1 057
准确性	0.994 7	0.997 8	0.999 3	0.999 8	1.0	1.0
CS的维度	107	110	111	116	124	129

下载: 导出CSV

| 显示表格

仿真结果验证了CS在Fast-SSC译码过程中仍然有效，即CS有接近100%的概率能够包含Fast-SSC译码过程中的首位译码错误比特，且CS的维度小于信息比特集合的大小。

4. 关键翻转集合CFS的构造

4.1 基础理论及结论证明

给出了SC译码树转换成Fast-SSC译码树的过程。 $\{ {u_1},{u_2},{u_3},{u_5}\}$ 表示冻结序列， $\{ {u_4},{u_6},{u_7},{u_8}\}$ 表示信息序列。右边的译码树表示该极化码的Fast-SSC译码树。其中左边叶节点为REP节点，该节点可以描述成一个长度为4，包含 $\{ {u_1},{u_2},{u_3},{u_4}\}$ 的子极化码。同理，右边叶节点为SPC节点，可以描述为一个长度为4，包含 $\{ {u_5},{u_6},{u_7},{u_8}\}$ 的子极化码。

图 3 极化码SC译码树以及Fast-SSC译码树

下载: 全尺寸图片幻灯片

当进行Fast-SSC译码时，利用硬判决方法对REP以及SPC节点直接译码得到的结果称为码字序列。在Fast-SSC译码过程中，只有翻转首位错误码字比特才能避免错误传播对Fast-SSC译码过程的影响。然而CS是相对于信息比特序列而言的，因此对于Fast-SSC译码，需要寻找与CS中的信息比特相应的候选比特(码字比特)才能构建候选翻转比特集合。

对于一个码长为 $N = {2^n}$ 的极化码，其生成矩阵 ${{\boldsymbol{G}}_N} = \left( {{{\boldsymbol{g}}_1},{{\boldsymbol{g}}_2},\cdots,{{\boldsymbol{g}}_N}} \right) = {{\boldsymbol{F}}^{ \otimes n}}$ ，其中 ${{\boldsymbol{G}}_N}$ 的列向量 ${{\boldsymbol{g}}_i}$ 中元素1的位置构成的集合为 ${{\boldsymbol{\varOmega}} _i}$ 。若叶节点 $l$ 长度为 $L$ ，当前子极化码对应于极化码的索引为 $(\tau + 1,\tau + 2,\cdots,\tau + L)$ ， $l$ 由包含的信息比特序列 ${\boldsymbol{u}}_{\tau + 1}^{\tau + L}$ 经过极化编码构成，在节点 $l$ 处可得到码字序列为

${\boldsymbol{x}}_1^L = {\boldsymbol{u}}_{\tau + 1}^{\tau + L}{{\boldsymbol{G}}_L}$

(9)

其中， ${{\boldsymbol{G}}_{{L}}}$ 为该子极化码的生成矩阵。当译码树的叶节点 $l$ 为Rate1或者REP节点时，在2元域下，本文给出如下命题：

命题1　若Fast-SSC译码中首位错误信息比特 ${u_{\tau + i}}$ 在译码树的叶节点 $l$ 内，且是由 $l$ 译码得到的部分码字比特 ${\hat x_{\boldsymbol{\varPhi}} }$ 错误导致的，则必然有 ${\boldsymbol{\varPhi}} \subseteq {{\boldsymbol{\varOmega}} _i}$ 且有极大概率 $\left| {\boldsymbol{\varPhi}} \right|{\text{ = }}1$ ，其中 ${\boldsymbol{\varPhi}}$ 表示为候选翻转比特集合。

证明　若节点 $l$ 得到的译码码字序列为 $\hat {\boldsymbol{x}}_1^L$ ，则该节点包含的信息序列为

${\hat{{\boldsymbol{u}}}}_{\tau +1}^{\tau +L}\text={\hat{{\boldsymbol{x}}}}_{1}^{L}\cdot {{\boldsymbol{G}}}_{L}{}^{-1}={\hat{{\boldsymbol{x}}}}_{1}^{L}\cdot{{\boldsymbol{G}}}_{L}$

(10)

其中，第2步等式是根据文献[]中给出的 ${{\boldsymbol{G}}_N} = {{\boldsymbol{G}}_N}^{ - 1}$ ，故可以得到首位错误比特 ${u_{\tau + i}}$ 的估计值 ${\hat u_{\tau + i}}$ 为

${\hat{u}}_{\tau +i}={\hat{{\boldsymbol{x}}}}_{1}^{L}\cdot{{\boldsymbol{g}}}_{i}={\displaystyle \sum _{j\in {{\boldsymbol{\varOmega}} }_{i}}{\hat{x}}_{j}}$

(11)

根据式(11)可以得到 ${\hat u_{\tau + i}}$ 值的正确与否仅仅与集合 ${{\boldsymbol{\varOmega}} _i}$ 有关，必然有 ${\boldsymbol{\varPhi}} \subseteq {{\boldsymbol{\varOmega}} _i}$ ；又由文献[]可知，Fast-SSC译码中首位译码错误的特殊节点有极大概率仅包含一位错误，因此集合 ${\boldsymbol{\varPhi}}$ 的大小 $|{\boldsymbol{\varPhi}} |$ 极大概率为1。

因此对于Rate1及REP节点而言，若确定首位错误信息比特 ${u_{\tau + i}}$ ，则其相应的候选比特集合 ${\boldsymbol{\varPhi}}$ 可由命题1得到。当译码树的叶节点 $l$ 为SPC节点时，若首位错误信息比特 ${u_{\tau + i}}$ 在该节点内，则根据文献[]可知，SPC节点有极大概率仅存在两位错误比特，一位为固定翻转码字比特(由于该比特是固定翻转比特，因此并没有被包含于该文献中的节点内错误比特数量统计结果)，另一位为待确定的由信道噪声导致译码错误的某个候选码字比特 $e$ 。由于命题1是在2元域讨论下得到的结论，则两位错误比特必然不可能同时在 ${x_{{{\boldsymbol{\varOmega}} _i}}}$ 中，否则根据式(11)可知，两位错误比特将导致 ${u_{\tau + i}}$ 正确译码。将 ${u_{\tau + i}}$ 相应的固定翻转位记作 ${\mu _\varepsilon }$ ，且计算为

${\mu _\varepsilon } = \arg \mathop {\min }\limits_\mu \left| {{{\boldsymbol{\alpha}} _v}[\mu ]} \right|,\mu \in {\boldsymbol{\varOmega}} _i^C$

(12)

其中， ${\boldsymbol{\varOmega}} _i^C$ 表示列向量 ${{\boldsymbol{g}}_i}$ 中元素0的位置构成的集合，即 ${{\boldsymbol{\varOmega}} _i}$ 的补集。当对SPC节点执行翻转译码时，同时翻转 $e$ 及 ${\mu _\varepsilon }$ 处的码字比特。此外，候选码字比特 $e$ 必然属于 ${\hat x_{\boldsymbol{\varPhi}} }$ ，证明过程同上述命题1的证明。因此，对于SPC节点而言，若首位错误信息比特为 ${u_{\tau + i}}$ ，则可以根据式(12)计算其相应的固定翻转位，根据命题1得到相应的候选比特集合 ${\boldsymbol{\varPhi}}$ 。

综上所述，对于Rate1，REP以及SPC 3种特殊节点，若确定首位错误信息比特 ${u_{\tau + i}}$ ，则都能够利用命题1来构建 ${u_{\tau + i}}$ 相应的候选比特集合。

为了便于理解命题1，本文以中的SPC节点为例。该SPC节点为一个码长 $N = 4$ 的子极化码，包含信息比特序列 $({u_6},{u_7},{u_8})$ ， ${u_5}$ 为冻结比特且设置为0，该子极化码对应的子树结构如图4所示，其中蓝色节点表示SPC节点，白色叶节点表示冻结比特，黑色叶节点表示信息比特。当利用Fast-SSC算法进行译码时，在SPC节点得到的正确译码码字为

图 4 译码树SPC节点对应子树结构

下载: 全尺寸图片幻灯片

${x}_{1}^{4}={{\boldsymbol{u}}}_{5}^{8}\cdot{{\boldsymbol{G}}}_{4}$

(13)

其中， ${{\boldsymbol{G}}_4}$ 为该子极化码的生成矩阵。假设上述的极化码在Fast-SSC译码中首位错误比特为 ${u_6}$ ，则根据式(13)有

${\hat{u}}_{6}={\hat{{\boldsymbol{x}}}}_{1}^{4}\cdot {{\boldsymbol{g}}}_{2}={\hat{x}}_{2}+{\hat{x}}_{4}$

(14)

根据式(14)可知，导致 ${u_6}$ 译码错误的原因是 ${x_2}$ 或 ${x_4}$ 译码错误，即有 ${\boldsymbol{\varPhi }}= \{ 2\}$ 或 ${\boldsymbol{\varPhi}} = \{ 4\}$ ；显然 ${{\boldsymbol{\varOmega}} _2} = \{ 2,4\}$ ，故 ${\boldsymbol{\varPhi}} \subseteq {{\boldsymbol{\varOmega}} _i}$ 成立。证毕

4.2 CFS构造算法

基于上述的命题1，在Fast-SSC译码过程中，首位错误信息比特一般都是由其所在的子极化码的某位码字比特 ${x_{\boldsymbol{\varPhi}} }$ 译码错误导致的；同时根据Fast-SSC译码中首位错误信息比特有接近100%的概率在CS中的结论，本文将CS中的每个信息比特对应的 ${x_{{\varPhi}} }$ 收集起来构成一个关键翻转集合CFS。不同于CS的构建方法，CFS在CS的基础上，需要利用LLR以及生成矩阵完成，其不仅与极化码的结构有关还与译码过程有关。

CFS构建方法如所示：注意到所述算法的第1行利用的是算法1所述的CS构造函数；第3行根据Fast-SSC译码树结构确定 ${\text{CS(}}i{\text{)}}$ 相应的 ${\boldsymbol{\varOmega}}$ ，先确定 ${\text{CS(}}i{\text{)}}$ 所在的子极化码生成矩阵 ${{\boldsymbol{G}}_N}$ 以及其相对节点内的首位信息比特的位置 $i$ ，根据 ${{\boldsymbol{G}}_N}$ 以及 $i$ 确定相应的 ${\boldsymbol{\varOmega}}$ ；第4行描述的衡量码字比特可靠性的度量准则，所使用的度量准则为码字比特的决策LLR。 ${\boldsymbol{\lambda}} _1^N$ 表示码字比特序列相应的决策LLR向量。

算法2　CFS构造算法
输入：信息比特索引集合 ${\boldsymbol{I}}$ ，Fast-SSC译码树结构tree_struct，　码字决策LLR向量 ${\boldsymbol{\lambda}} _1^N$
输出：关键翻转集合CFS
(1) ${\text{CS}}$ $\leftarrow$ Construct Critical Set ( ${\boldsymbol{I}}$ )
(2) for $i = 1:\|{\rm{CS}}\|$ do
(3) 　　根据tree_struct，找到CS( $i$ )相应的 ${\boldsymbol{\varOmega}}$
(4) 　　根据 ${\boldsymbol{\lambda}} _1^N$ 选择 ${\boldsymbol{\varOmega}}$ 中最不可靠的码字比特放入到CFS集合中
(5) end for

下载: 导出CSV

| 显示表格

CFS构造算法一个直观的解释是，Fast-SSC译码过程中首位错误比特一般是由于该比特所在的子极化码某位译码错误导致的，且该比特必然属于 ${x_{\boldsymbol{\varOmega}} }$ ，因此本文选择 ${x_{{{\boldsymbol{\varOmega}}}} }$ 中最不可靠的码字比特作为CFS集合中的一员。同时，由于CS集合有极大概率包括Fast-SSC译码的首位错误比特，故为了减少复杂度，本文仅考虑在CS基础上构建相应的CFS。

5. CFS-Fast-SSC-Flip译码算法及性能

5.1 CFS-Fast-SSC-Flip译码算法

本文基于提出的CFS设计了一种单比特翻转Fast-SSC译码算法，命名为CFS-Fast-SSC-Flip译码算法。CFS-Fast-SSC-Flip译码算法详细的描述见算法3。所提算法与传统的Fast-SSC-Flip译码算法的主要区别为：所提算法选择候选比特进行翻转译码时仅从CFS中选择，相较于传统的Fast-SSC-Flip使用整个信息比特集合的搜索范围而言，减小了搜索复杂度，有效提升候选比特的搜索效率。

算法3　CFS-Fast-SSC-Flip译码算法
输入：信道接收序列 $y$ ，信息比特索引集合 ${\boldsymbol{I}}$ ，最大可翻转次数　 ${T_{\max }}$
输出：译码输出比特序列 ${\boldsymbol{u}}_1^N$
(1) $[\hat {\boldsymbol{u} }_1^N,{\boldsymbol{\lambda}} _1^N] \leftarrow$ Fast-SSC $(y,{\boldsymbol{I}})$
(2) if 译码码字 $\hat {\boldsymbol{u}}_1^N$ 未通过CRC校验，then
(3) 　　CFS $\leftarrow$ Construct CFS $(\lambda _1^N,{{{\rm{tree}}_{-}{\rm{struct}}} },{\boldsymbol{I} })$
(4) 　　根据度量准则对所有 ${x_i} \in {\text{CFS}}$ 进行升序排序
(5) 　　　　for $i = {\text{1} }:{T_{{\rm{max}}} }$ do
(6) 　　　　　　 $[\hat {\boldsymbol{u}}_1^N] \leftarrow$ Fast-SSC-Flip $(y,{\boldsymbol{I}},{\text{CFS} }(i))$
(7) 　　　　　　if 译码码字 $\hat {\boldsymbol{u}}_1^N$ 通过CRC校验，then
(8) 　　　　　　　return $\hat {\boldsymbol{u}}_1^N$
(9) 　　　　　　end if
(10) 　　　 end for
(11) end if
(12) return $\hat {\boldsymbol{u}}_1^N$

下载: 导出CSV

| 显示表格

5.2 CFS-Fast-SSC-Flip译码器性能分析

为了研究提出的CFS-Fast-SSC-Flip译码算法译码性能，本节将中第4行的度量准则设置为根据候选比特的决策LLR升序排序，并与Fast-SSC-Flip ( $s = 0.5$ ，算法补偿系数) ，N-Fast-SSC-Flip, Fast-SSC以及SSC-Oracle译码算法进行性能比较。由于本文所提的CFS-Fast-SSC-Flip译码算法的CFS是基于CS构建的，因此本文同时比较了基于CS的Fast-SSC-Flip (Fast-SSC-Flip-CS)译码算法的性能。SSC-Oracle译码算法是一种理想的Fast-SSC译码算法，该算法能够完美纠正Fast-SSC译码过程中由信道噪声导致的单个错误比特，即该算法的性能代表单比特翻转 Fast-SSC 算法的译码性能上限。

当设置极化码的参数 $N = 512$ , $R = 0.5$ 时，上述各个译码算法的BER性能曲线如所示。从可以看出所提的CFS-Fast-SSC-Flip译码算法与N-Fast-SSC-Flip译码算法的BER性能曲线几乎保持一致，相较于传统的Fast-SSC-Flip译码算法以及Fast-SSC-Flip-CS译码算法，所提的CFS-Fast-SSC-Flip译码算法并没有明显的BER性能损失。相较 SC, Fast-SSC译码算法在 ${\text{BER}} = {10^{ - 3}}$ 条件下有0.78 dB的性能增益。

图 5 CFS-Fast-SSC-Flip译码算法与各种译码算法在

$R = 0.5$ 时BER性能比较图

下载: 全尺寸图片幻灯片

类似地，表示 $N = 1\;024$ , $R = 0.5$ 时上述的各个译码算法的BER性能数值仿真图。综合图5(a)与图5(b)可得，所提的CFS-Fast-SSC-Flip译码算法与N-Fast-SSC-Flip译码算法的BER性能曲线几乎保持一致，相较于传统的Fast-SSC-Flip译码算法以及Fast-SSC-Flip-CS译码算法，所提的CFS-Fast-SSC-Flip译码算法并没有明显的BER性能损失。

当设置极化码的参数为 $N = 512$ , $R = 0.5$ 时，上述各个译码算法的FER性能曲线如所示。从中可以看出提出的CFS-Fast-SSC-Flip译码算法相较于基础的Fast-SSC译码算法在FER= ${10^{ - 2}}$ 条件下大约有0.48 dB的性能增益，相较于传统的Fast-SSC-Flip算法在FER= ${10^{ - 3}}$ 条件下大约有0.09 dB的性能增益，性能要略优于Fast-SSC-Flip-CS译码算法，且性能近似于N-Fast-SSC-Flip算法。

图 6 CFS-Fast-SSC-Flip译码算法与各种译码算法在

$R = 0.5$ 时FER性能比较图

下载: 全尺寸图片幻灯片

类似地，表示在极化码参数 $N = 1\;024$ , $R = 0.5$ 时上述的各个译码算法的FER性能数值仿真图。通过观察两图可以发现，提出的CFS-Fast-SSC-Flip算法的译码性能略优于传统的Fast-SSC-Flip译码算法以及Fast-SSC-Flip-CS译码算法，且与N-Fast-SSC-Flip译码算法的性能几乎相同。

为了研究CFS-Fast-SSC-Flip译码算法的性能开销以及译码延迟，本节利用翻转译码算法的平均迭代次数 ${I_{{\rm{ave}}}}$ 来表示每一帧需要进行译码的次数，其最小和最大的迭代次数分别为1和 ${T_{{\rm{max}}}} + 1$ 。 ${I_{{\rm{ave}}}}$ 的计算方法为

${I_{{\rm{ave}}}} = \frac{{\displaystyle\sum\limits_{i = 1}^F {{t_i}} }}{F}$

(15)

其中， ${t_i}$ 表示第 $i$ 帧中译码的总次数， $F$ 表示传输的总帧数。

为了更好地分析所提算法的译码延迟^[18]，对各种算法的时钟周期(Clock Cycles, CC)进行比较。为了便于表述每个译码阶段所消耗的CC数，其中Fast-SSC译码算法消耗的CC数、排序操作消耗的CC数、CRC校验消耗的CC数以及一轮额外迭代的CC数分别用 ${C_{{\rm{Fast}} - {\rm{SSC}}}}$ ， ${C_{{\rm{Sort}}}}$ ， ${C_{{\rm{CRC}}}}$ 以及 ${C_{{\rm{Extra}}}}$ 进行表示。假设在第1次译码过程中，首先进行Fast-SSC译码操作，然后执行排序操作，其中CRC校验和排序操作同时执行。因此在第1次译码过程中消耗的 ${C_1} = {C_{{\rm{Fast}} - {\rm{SSC}}}} + {C_{{\rm{Sort}}}}$ 。在额外的迭代译码过程中仍然先执行Fast-SSC译码操作，与第1次译码不同的是，后续的迭代译码过程不需要进行排序操作。因此，每一轮额外的迭代译码消耗的 ${C_{{\rm{Extra}}}} = {C_{{\rm{Fast}} - {\rm{SSC}}}} + {C_{{\rm{CRC}}}}$ 。综上，译码一帧所需CC数量的计算表达如式(16)所示

$\begin{split} C=&{C}_{1}+({I}_{{\rm{ave}}}-1)\cdot {C}_{{\rm{Extra}}}\\ =&{I}_{{\rm{ave}}}\cdot {C}_{{\rm{Fast}}-{\rm{SSC}}}+({I}_{{\rm{ave}}}-1)\cdot {C}_{{\rm{CRC}}}+{C}_{{\rm{Sort}}} \end{split}$

(16)

由于所对比的几种不同算法均基于Fast-SSC，在保持参数一致的情况下，译码过程中消耗的 ${C_{{\rm{Fast}} - {\rm{SSC}}}}$ ， ${C_{{\rm{CRC}}}}$ 一致。因此，译码一帧中消耗的CC数量取决于 ${C_{{\rm{Sort}}}}$ 。传统的Fast-SSC-Flip译码算法对 $K$ 个信息比特的LLR值进行排序，而CFS-Fast-SSC-Flip仅对CFS中 $\eta$ 个信息比特的LLR值进行排序。在排序过程中消耗的时钟周期 ${C_{{\rm{Sort}}}}(\eta ) < {C_{{\rm{Sort}}}}(K)$ 。由可以得到，本文所提的CFS-Fast-SSC-Flip译码算法的平均迭代次数 ${I_{{\rm{ave}}}}$ 要小于等于目前现存的Fast-SSC-Flip译码算法。综上，本文所提算法的译码延迟要优于Fast-SSC-Flip算法、且与N-Fast-SSC-Flip译码算法的译码延迟接近。

表 2 各种译码算法的平均迭代次数

	极化码参数
	N = 512, R = 0.5			N = 1 024, R = 0.5
SNR (dB)	1.0	2.0	3.0	1.0	2.0	3.0
Fast-SSC-Flip	5.256	1.597	1.018	6.153	1.428	1.004
N-Fast-SSC-Flip	5.039	1.482	1.013	5.958	1.369	1.003
Fast-SSC-Flip-CS	6.118 5	1.625 1	1.095 9	6.263 7	1.887 3	1.013 8
CFS-Fast-SSC-Flip	5.041	1.486	1.013	5.963	1.370	1.003

下载: 导出CSV

| 显示表格

本文所提的CFS-Fast-SSC-Flip译码算法相较于传统Fast-SSC-Flip以及N-Fast-SSC-Flip译码算法的一个直观优势是在候选比特的搜索效率。传统的Fast-SSC-Flip译码算法在搜索候选比特方面的复杂度为 $O(K{\log _2}K)$ ，而CFS-Fast-SSC-Flip译码算法的搜索复杂度为 $O(\eta {\log _2}\eta )$ 。其中 $K$ 表示信息比特集合大小， $\eta$ 表示CFS集合的大小。

比较了本节所提的CFS相较于传统的Fast-SSC-Flip所使用的候选翻转比特集合大小。从可以得到本文所提的CFS集合的大小在不同极化码编码参数以及信噪比的情况下都要小于传统的Fast-SSC-Flip译码算法所使用的候选翻转比特集合大小。在极化码的码长 $N = 1\;024$ ，码率 $R = 0.5$ ，本文所提的CFS-Fast-SSC-Flip译码算法相较于传统Fast-SSC-Flip(N-Fast-SSC-Flip与传统Fast-SSC-Flip两种译码算法的候选翻转比特集合大小相同)，至少能缩小77.93%的候选翻转比特集合大小。

表 3 CFS与传统Fast-SSC-Flip译码算法的候选翻转比特集合大小比较

	极化码参数
	N = 512, R = 0.5			N = 1 024, R = 0.5
SNR (dB)	1.0	2.0	3.0	1.0	2.0	3.0
CFS平均大小	52	58	62	87	96	113
传统翻转比特集合大小	256			512
缩小比例 (%)	79.69	77.34	75.78	83.01	81.25	77.93

下载: 导出CSV

| 显示表格

6. 结论

本文从缩小Fast-SSC-Flip译码算法中的候选翻转比特集合大小出发来提升Fast-SSC-Flip的候选比特搜索效率，由此提出了CFS-Fast-SSC-Flip。本文所提的CFS能够有效地包含候选翻转比特，但集合大小远小于全部信息比特集合大小，从而减小搜索复杂度。实验结果表明，本文提出的基于CFS的Fast-SSC-Flip算法在和N-Fast-SSC-Flip取得相近的译码性能和平均迭代次数的情况下，显著地缩小了候选翻转比特集合的大小，减小了搜索复杂度，提升了候选比特的搜索效率。

图 1 3轮的量子区分器

下载: 全尺寸图片幻灯片

图 2 FX结构

下载: 全尺寸图片幻灯片

图 3 Ito等人在Feistel上的4轮量子区分器

下载: 全尺寸图片幻灯片

图 4 $d$ 分支Type-1 GFS的第 $i$ 轮

下载: 全尺寸图片幻灯片

图 5 4分支Type-1 GFS的选择明文量子区分器

下载: 全尺寸图片幻灯片

图 6 4分支Type-1 GFS的16轮密钥恢复攻击

下载: 全尺寸图片幻灯片

图 7 4分支CAST256-like GFS的10轮区分器

下载: 全尺寸图片幻灯片

图 8 CAST-256的12轮区分器

下载: 全尺寸图片幻灯片

图 9 CAST-256的14轮攻击

下载: 全尺寸图片幻灯片

图 10 CAST-256的13轮区分器

下载: 全尺寸图片幻灯片

表 1 Type-1 GFS的量子区分器的轮数

来源	攻击条件	$r$	$d = 3$	$d = 4$	$d = 5$	$d = 6$	$d = 7$
文献[35]	qCPA	2d–1	5	7	9	11	13
4.1节	qCPA	3d–3	6	9	12	15	18
4.2节	qCCA	3d–2	7	10	13	16	19

下载: 导出CSV

表 2 在量子环境下对Type-1 GFS的密钥恢复攻击

来源	区分器轮数	密钥恢复轮数	复杂度(log)	穷搜复杂度(log)
文献[35]	$2d - 1$	$r \ge {d^2}$	$T + ({{r - {d^2} + d - 2)n} / 2}$	${{rn} / 2}$
4.1节	$3d - 3$	$r \ge {d^2}$	$T + ({{r - {d^2})n} / 2}$	${{rn} / 2}$

下载: 导出CSV

表 3 CAST-256的量子攻击

来源	攻击条件	区分器轮数	密钥恢复攻击轮数
来源	攻击条件	区分器轮数	$r = 14$	$r = 15$	$r = 16$	$r = 17$	$r = 18$	$r = 19$
文献[35]	qCPA	7	${2^{74}}$	${2^{92.5}}$	${2^{111}}$	$-$	$-$	$-$
5.1节	qCPA	12	${2^{37}}$	${2^{55.5}}$	${2^{74}}$	${2^{92.5}}$	${2^{111}}$	$-$
5.2节	qCCA	13	${2^{18.5}}$	${2^{37}}$	${2^{55.5}}$	${2^{74}}$	${2^{92.5}}$	${2^{111}}$

下载: 导出CSV

表 4 针对CAST-256的经典攻击和量子攻击的比较

来源	密钥长度	攻击	轮数	数据	时间
文献[39]	128	飞去来器	16	${2^{49.3}}$	$-$
5.2节	128	qCCA	16	–	${2^{55.5}}$
文献[40]	192	线性攻击	24	${2^{124.1}}$	${2^{156.52}}$
5.2节	192	qCCA	17	–	${2^{74}}$
文献[41]	256	多维零相关	28	${2^{98.8}}$	${2^{246.9}}$
5.2节	256	qCCA	19	–	${2^{111}}$

下载: 导出CSV

参考文献(41)

KNUDSEN L R. The security of Feistel ciphers with six rounds or less[J]. Journal of Cryptology, 2002, 15(3): 207–222. doi: 10.1007/s00145-002-9839-y

ISOBE T and SHIBUTANI K. Generic key recovery attack on Feistel scheme[C]. The 19th International Conference on the Theory and Application of Cryptology and Information Security, Bengaluru, India, 2013: 464–485.

GUO Jian, JEAN J, NIKOLIĆ I, et al. Meet-in-the-middle attacks on generic Feistel constructions[C]. The 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, China, 2014: 458–477.

DINUR I, DUNKELMAN O, KELLER N, et al. New attacks on Feistel structures with improved memory complexities[C]. The 35th Annual Cryptology Conference, Santa Barbara, USA, 2015: 433–454.

AOKI K, ICHIKAWA T, KANDA M, et al. Camellia: A 128-bit Block Cipher Suitable for Multiple Platforms - Design and Analysis[M]. Berlin, Heidelberg: Springer, 2001: 39–56.

National Soviet Bureau of Standards. GOST 28147-89 Information processing systems. cryptographic protection cryptographic transformation algorithm[S]. 1989.

ZHENG Yuliang, MATSUMOTO T, and IMAI H. On the construction of block ciphers provably secure and not relying on any unproved hypotheses[C]. Conference on the Theory and Application of Cryptology, Santa Barbara, USA, 1990: 461–480.

ANDERSON R and BIHAM E. Two practical and provably secure block ciphers: BEAR and LION[C]. The 3rd International Workshop on Fast Software Encryption, Cambridge, UK, 1996: 113–120.

LUCKS S. Faster luby-rackoff ciphers[C]. The 3rd International Workshop on Fast Software Encryption, Cambridge, UK, 1996: 189–203.

SCHNEIER B and KELSEY J. Unbalanced Feistel networks and block cipher design[C]. The 3rd International Workshop on Fast Software Encryption, Cambridge, UK, 1996: 121–144.

First AES Candidate Conference[EB/OL]. http://csrc.nist.gov/archive/aes/round1/conf1/aes1conf.htm.

SHIRAI T, SHIBUTANI K, AKISHITA T, et al. The 128-bit blockcipher CLEFIA (extended abstract)[C]. The 14th International Workshop on Fast Software Encryption, Luxembourg, Luxembourg, 2007: 181–195.

GUERON S and MOUHA N. Simpira v2: A family of efficient permutations using the AES round function[C]. The 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, 2016: 95–125.

LUBY M and RACKOFF C. How to construct pseudorandom permutations from pseudorandom functions[J]. SIAM Journal on Computing, 1988, 17(2): 373–386. doi: 10.1137/0217022

MORIAI S and VAUDENAY S. On the pseudorandomness of top-level schemes of block ciphers[C]. The 6th International Conference on the Theory and Application of Cryptology and Information Security, Kyoto, Japan, 2000: 289–302.

HOANG V T and ROGAWAY P. On generalized Feistel networks[C]. The 30th Annual Cryptology Conference, Santa Barbara, USA, 2010: 613–630.

JUTLA C S. Generalized birthday attacks on unbalanced Feistel networks[C]. The 18th Annual International Cryptology Conference, Santa Barbara, USA, 1998: 186–199.

GUO Jian, JEAN J, NIKOLIC I, et al. Meet-in-the-middle attacks on classes of contracting and expanding Feistel constructions[J]. IACR Transactions on Symmetric Cryptology, 2016(2): 307–337.

NACHEF V, VOLTE E, and PATARIN J. Differential attacks on generalized Feistel schemes[C]. The 12th International Conference on Cryptology and Network Security, Paraty, Brazil, 2013: 1–19.

TJUAWINATA I, HUANG Tao, and WU Hongjun. Improved differential cryptanalysis on generalized Feistel schemes[C]. The 18th International Conference on Cryptology in India, Chennai, India, 2017: 302–324.

PATARIN J, NACHEF V, and BERBAIN C. Generic attacks on unbalanced Feistel schemes with contracting functions[C]. The 12th International Conference on the Theory and Application of Cryptology and Information Security, Shanghai, China, 2006: 396–411.

PATARIN J, NACHEF V, and BERBAIN C. Generic attacks on unbalanced Feistel schemes with expanding functions[C]. The 13th International Conference on the Theory and Application of Cryptology and Information Security, Kuching, Malaysia, 2007: 325–341.

VOLTE E, NACHEF V, and PATARIN J. Improved generic attacks on unbalanced Feistel schemes with expanding functions[C]. The 16th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, 2010: 94–111.

GROVER L K. A fast quantum mechanical algorithm for database search[C]. The 28th Annual ACM Symposium on Theory of Computing, Philadelphia, USA, 1996: 212–219.

KUWAKADO H and MORII M. Quantum distinguisher between the 3-round Feistel cipher and the random permutation[C]. IEEE International Symposium on Information Theory, Austin, USA, 2010: 2682–2685.

SIMON D R. On the power of quantum computation[J]. SIAM Journal on Computing, 1997, 26(5): 1474–1483. doi: 10.1137/S0097539796298637

KUWAKADO H and MORII M. Security on the quantum-type even-mansour cipher[C]. 2012 International Symposium on Information Theory and its Applications, Honolulu, USA, 2012: 312–316.

KAPLAN M, LEURENT G, LEVERRIER A, et al. Breaking symmetric cryptosystems using quantum period finding[C]. The 36th Annual International Cryptology Conference, Santa Barbara, USA, 2016: 207–237.

BONNETAIN X. Quantum key-recovery on full AEZ[C]. The 24th International Conference on Selected Areas in Cryptography, Ottawa, Canada, 2018: 394–406.

LEANDER G and MAY A. Grover meets simon - quantumly attacking the FX-construction[C]. The 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, 2017: 161–178.

ZHANDRY M. How to construct quantum random functions[C]. The 53rd IEEE Annual Symposium on Foundations of Computer Science, New Brunswick, USA, 2012: 679–687.

ITO G, HOSOYAMADA A, MATSUMOTO R, et al. Quantum chosen-ciphertext attacks against Feistel ciphers[C]. The Cryptographers' Track at the RSA Conference, San Francisco, USA, 2019: 391–411.

HOSOYAMADA A and SASAKI Y. Quantum demiric-selçuk meet-in-the-middle attacks: Applications to 6-round generic Feistel constructions[C]. The 11th International Conference on Security and Cryptography for Networks, Amalfi, Italy, 2018: 386–403.

DONG Xiaoyang and WANG Xiaoyun. Quantum key-recovery attack on Feistel structures[J]. Science China Information Sciences, 2018, 61(10): 102501. doi: 10.1007/s11432-017-9468-y

DONG Xiaoyang, LI Zheng, and WANG Xiaoyun. Quantum cryptanalysis on some generalized Feistel schemes[J]. Science China Information Sciences, 2019, 62(2): 22501. doi: 10.1007/s11432-017-9436-7

DONG Xiaoyang, DONG Bingyou, and WANG Xiaoyun. Quantum attacks on some Feistel block ciphers[R]. Cryptology ePrint Archive, Report 2018/504, 2018.

BONNETAIN X, NAYA-PLASENCIA M, and SCHROTTENLOHER A. On quantum slide attacks[R]. Cryptology ePrint Archive, Report 2018/1067, 2018.

HOSOYAMADA A and IWATA T. Tight quantum security bound of the 4-round luby-rackoff construction[R]. Cryptology ePrint Archive, Report 2019/243, 2019.

WAGNER D. The boomerang attack[C]. The 6th International Workshop on Fast Software Encryption, Rome, Italy, 1999: 156–170.

WANG Meiqin, WANG Xiaoyun, and HU Changhui. New linear cryptanalytic results of reduced-round of CAST-128 and CAST-256[C]. The 15th International Workshop on Selected Areas in Cryptography, Sackville, Canada, 2009: 429–441.

BOGDANOV A, LEANDER G, NYBERG K, et al. Integral and multidimensional linear distinguishers with correlation zero[C]. The 18th International Conference on the Theory and Application of Cryptology and Information Security, Beijing, China, 2012: 244–261.

施引文献

期刊类型引用(5)

1.	王惠琴，罗佳，何永强，曹明华，高大庆，李佳豪. 改进YOLOv5的探地雷达常见地下管线识别. 地球物理学报. 2024(09): 3588-3604 . 百度学术
2.	胡丕杰，邱旭波，林昊宇. 基于深度学习的自动驾驶环境感知系统优化. 中国战略新兴产业. 2024(26): 104-107 . 百度学术
3.	侯斐斐，彭应昊，董健，银雪. 基于双重YOLOv8-pose模型的探地雷达双曲线关键点检测与目标定位. 电子与信息学报. 2024(11): 4305-4316 . 本站查看
4.	刘兴，闫坤，甘海铭. 基于深度学习的LGPR数据处理及定位方法. 计算机工程与设计. 2024(11): 3514-3521 . 百度学术
5.	张玉强，郭辉. 渗漏埋地供水管道雷达探测信号特征分析. 延安大学学报(自然科学版). 2023(03): 92-97 . 百度学术

其他类型引用(5)

资源附件(0)

访问统计

图(10) / 表(4)

计量

文章访问数: 3481
HTML全文浏览量: 1068
PDF下载量: 149
被引次数: 10

1. 引言
2. Fast-SSC-Flip译码算法
2.1 Fast-SSC译码算法
2.2 Fast-SSC-Flip译码算法
3. Fast-SSC译码算法中CS构造及其有效性
3.1 CS构造方法
3.2 CS有效性
4. 关键翻转集合CFS的构造
4.1 基础理论及结论证明
4.2 CFS构造算法
5. CFS-Fast-SSC-Flip译码算法及性能
5.1 CFS-Fast-SSC-Flip译码算法
5.2 CFS-Fast-SSC-Flip译码器性能分析
6. 结论

1. 引言
2. Fast-SSC-Flip译码算法
2.1 Fast-SSC译码算法
2.2 Fast-SSC-Flip译码算法
3. Fast-SSC译码算法中CS构造及其有效性
3.1 CS构造方法
3.2 CS有效性
4. 关键翻转集合CFS的构造
4.1 基础理论及结论证明
4.2 CFS构造算法
5. CFS-Fast-SSC-Flip译码算法及性能
5.1 CFS-Fast-SSC-Flip译码算法
5.2 CFS-Fast-SSC-Flip译码器性能分析
6. 结论

参考文献(41)

施引文献

资源附件(0)

访问统计

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

留言板

改进的Type-1型广义Feistel结构的量子攻击及其在分组密码CAST-256上的应用

doi: 10.11999/JEIT190633

作者简介:
董晓阳：男，1988年生，助理研究员。研究方向为对称密码算法的安全性分析与设计

通讯作者:
董晓阳　xiaoyangdong@tsinghua.edu.cn

计量

Improved Quantum Attack on Type-1 Generalized Feistel Schemes and Its Application to CAST-256

1. 引言

2. Fast-SSC-Flip译码算法

2.1 Fast-SSC译码算法

2.2 Fast-SSC-Flip译码算法

3. Fast-SSC译码算法中CS构造及其有效性

3.1 CS构造方法

3.2 CS有效性

4. 关键翻转集合CFS的构造

4.1 基础理论及结论证明

4.2 CFS构造算法

5. CFS-Fast-SSC-Flip译码算法及性能

5.1 CFS-Fast-SSC-Flip译码算法

5.2 CFS-Fast-SSC-Flip译码器性能分析

6. 结论

期刊类型引用(5)

其他类型引用(5)

计量

目录

1. 引言

2. Fast-SSC-Flip译码算法

2.1 Fast-SSC译码算法

2.2 Fast-SSC-Flip译码算法

3. Fast-SSC译码算法中CS构造及其有效性

3.1 CS构造方法

3.2 CS有效性

4. 关键翻转集合CFS的构造

4.1 基础理论及结论证明

4.2 CFS构造算法

5. CFS-Fast-SSC-Flip译码算法及性能

5.1 CFS-Fast-SSC-Flip译码算法

5.2 CFS-Fast-SSC-Flip译码器性能分析

6. 结论

留言板

改进的Type-1型广义Feistel结构的量子攻击及其在分组密码CAST-256上的应用

doi: 10.11999/JEIT190633

作者简介: 董晓阳：男，1988年生，助理研究员。研究方向为对称密码算法的安全性分析与设计

通讯作者: 董晓阳 xiaoyangdong@tsinghua.edu.cn

计量

出版历程

Improved Quantum Attack on Type-1 Generalized Feistel Schemes and Its Application to CAST-256

1. 引 言

2. Fast-SSC-Flip译码算法

2.1 Fast-SSC译码算法

2.2 Fast-SSC-Flip译码算法

3. Fast-SSC译码算法中CS构造及其有效性

3.1 CS构造方法

3.2 CS有效性

4. 关键翻转集合CFS的构造

4.1 基础理论及结论证明

4.2 CFS构造算法

5. CFS-Fast-SSC-Flip译码算法及性能

5.1 CFS-Fast-SSC-Flip译码算法

5.2 CFS-Fast-SSC-Flip译码器性能分析

6. 结论

期刊类型引用(5)

其他类型引用(5)

计量

出版历程

目录

1. 引 言

2. Fast-SSC-Flip译码算法

2.1 Fast-SSC译码算法

2.2 Fast-SSC-Flip译码算法

3. Fast-SSC译码算法中CS构造及其有效性

3.1 CS构造方法

3.2 CS有效性

4. 关键翻转集合CFS的构造

4.1 基础理论及结论证明

4.2 CFS构造算法

5. CFS-Fast-SSC-Flip译码算法及性能

5.1 CFS-Fast-SSC-Flip译码算法

5.2 CFS-Fast-SSC-Flip译码器性能分析

6. 结论

作者简介:
董晓阳：男，1988年生，助理研究员。研究方向为对称密码算法的安全性分析与设计

通讯作者:
董晓阳　xiaoyangdong@tsinghua.edu.cn

1. 引言

1. 引言