对称密码体制的量子攻击.pdf

第42卷 第1期2024年1月应用科学学报JOURNAL OF APPLIED SCIENCESElectronics and Information EngineeringVol.42 No.1Jan.2024DOI:10.3969/j.issn.0255-8297.2024.01.004对称密码体制的量子攻击冯晓宁，吴洪宇哈尔滨工程大学 计算机科学与技术学院，黑龙江 哈尔滨 150001摘摘摘要要要：该文梳理了近年来量子攻击在对称密码体制的研究脉络，分析了主流攻击方法的研究趋势与各文献之间的关系，并将主流攻击方法分为量子周期攻击、Grover 算法相关攻击、量子差分攻击 3 类，分别介绍了具有代表性的攻击方法，呈现了各攻击方法的核心思想。立足于现有的攻击方案，展望了这一领域可能会出现的热门研究方向。关键词：密码分析；量子算法；对称密码体制；量子攻击中图分类号：TP309文章编号：0255-8297(2024)01-0039-14Quantum Attacks on Symmetric CryptosystemsFENG Xiaoning,WU HongyuCollege of Computer Science and Technology,Harbin Engineering University,Harbin 150001,Heilongjiang,ChinaAbstract:This paper undertakes an investigation of recent research trends in quantumattacks on symmetric encryption schemes,offering an analysis of the connections betweenmainstream attack methods and various literature sources.Mainstream attack methodsare systematically categorized into three types:quantum period attacks,Grover algorithm-related attacks,and quantum differential attacks.For each category,representative attackmethods are introduced,accompanied by an elucidation of the core concepts underlyingeach approach.Furthermore,we contemplate future research directions within this domain,considering potential advancements in light of existing attack schemes.Keywords:cryptanalysis,quantum algorithm,symmetric cryptosystem,quantum attack美国物理学家费曼在 1982 年提出了量子计算的概念1，该技术引起了世界各国的广泛关注。量子计算在大整数分解、离散对数计算等多个计算问题上展现出了显著优势。量子密码分析学（亦称为量子攻击）是量子计算与密码分析相交叉的新学科，具有经典密码分析不能拥有的资源及速度优势。本文主要介绍了量子密码分析学中针对于传统密码体制中对称密码体制的部分，即量子（对称）密码分析学。并把使用量子算法进行密码分析的过程称为量子环境设置，把未使用量子算法进行密码分析的过程称为经典或传统环境设置。量子计算对非对称密码分析学产生了深远影响。Shor 算法2和 Grover 算法3作为两种经典的量子计算方法，开启了量子密码分析的先河。1994 年，Shor 提出了在多项式时间内收稿日期：2023-06-29基金项目：国家自然科学基金（No.51979048）资助通信作者：冯晓宁，教授，研究方向为网络安全与密码学。E-mail:40应用科学学报第42卷分解大整数的算法2。大整数分解在传统计算机中被视为经典困难问题，很多非对称密码体制就是为了解决这种困难问题而设计的，比如 RSA 加密算法4。Shor 算法理论上对传统密码造成了巨大威胁5。时隔 20 年，当初提出的理论算法已变成现实，量子计算机已经可以分解 13 位的大整数6，表明量子计算在破解非对称密码方面已经取得了实质性的突破。在对称密码体制中，量子计算的影响是有限的。Grover 算法3应用于穷举攻击，可以产生二次加速的效果7。尽管 Grover 算法在密码分析领域产生了广泛的影响，但除 Grover 算法之外，绝大多数量子算法只能提供亚指数或多项式级别的加速，在对称密码分析方面的实际影响尚不明显。这也导致了密码学领域一个长期存在的共识：简单地将传统对称密码算法的密钥长度加倍，可确保对称密码算法在量子计算模型下的安全性。美国国家科学院关于量子计算的报告中指出：可能存在一些迄今未知但性能远超 Grover算法的量子攻击。许多密码学家正在探索比 Grover 算法更为高效的密码分析手段。例如，量子差分密码分析将经典差分密码分析的环境置为量子环境，旨在得到相比于经典情况下二次甚至指数级别的加速8。密码学家在诸多量子密码分析方面取得了长足的进步，有些甚至能够在多项式时间内破坏许多对称密码系统。1研究脉络及分类近年来，涉及量子对称密码分析学的研究成果显著增多，多数研究都在探索比传统密码分析所需资源更少的量子密码分析方法。对称密码体制的量子密码分析主流研究有两个重要特点：1）绝大多数量子攻击基于量子选择明文攻击模型（quantum chosen plaintext attack,qCPA）9。作为一个通用的攻击模型，一旦实施了攻击，则说明对称密码体制在量子设置下是不安全的。2）有两种逐步上升的研究趋势，一种是通过将经典密码分析算法转换为量子设置进行攻击，另一种是以低资源量子消耗为目标设计量子密码分析算法10。这两个研究趋势说明，在经典设置下可能无效的攻击方法，但在量子设置下可能会有效。为了更深入地理解对称密码体制量子攻击的研究历史沿革以及各文献之间的关系，图 1 展示本文重点文献关系。其中箭头表示研究的递进关系，虚线表示同类研究，红色表示高被引用文章，蓝色表示出现的2010 Kuwakado?162012 Kuwakado?172013 Rotteler?18?Simon?2019 Bonnetain?192020 Dong?20?Simon?2016 Kaplan?21(?)2022 Shinagawa?322022 Zhang332020 Ni?342018 Dong?35(?)2017 Alagic?232018 Bonnetain?24(?)2017 Leander?30(Grover meetsSimon)2019 Bonnetain?25(Offline simon)Grover?2020 Rahman?272020 Bonnetain?28(offline simon?)2022 Ulitzsch?292018 Hosoyamada?44(?Demiric&selcuk?)2022 Frixons?482020 Hosoyamada?51(?)2022 Schrottenloher?54?372017 Grassl?382018 Almazrooie?392020 Langenberg?40(?AES?)2020 Anand?432021 Liu?432015 Zhou?662015 Li612017 Xie?622019 Xie?632020 Xie?64(?)2020 Xie?642021 Zhou?362018 Li?69(?)?II?I?2022 Denisenko?682015 Kaplan?652021 Jojan?671997 Simon112022 Canale?221993 Bernstein?56(Bernstein-Vazirani?)2020 Aaronson?70(?)2019 Chen?71(?/?)?图 1 对称密码体制量子攻击的研究脉络Figure 1 Research context of quantum attack on symmetric cryptosystem第1期冯晓宁，等：对称密码体制的量子攻击41重点或有前景的攻击方法。根据上述研究脉络，本文将现有对称密码体制的量子攻击划分为量子周期攻击、Grover算法相关攻击及量子差分攻击，如图 2 所示。量子周期攻击以 Simon 算法为基础，主要关注Simon 算法中的弱化条件情况。除此之外，本文介绍了基于 Simon 算法的周期构建攻击，以及 Simon 算法的离线计算方式。在 Grover 算法相关攻击的研究中，主要介绍 Grover meetsSimon 算法、Grover 算法的穷举攻击以及近来基于 Grover 算法中备受关注的量子中间相遇攻击。量子差分算法是基于 B-V 算法进行研究的，随后本文分两阶段进行详细阐述。?Grover?Simon?Grover on X?Grover meets X?B-V?图 2 对称密码体制的量子攻击分类图Figure 2 Classification diagram of quantum attacks on symmetric cryptosystems2量子周期攻击2.1Simon算法的研究目前，Simon 算法11已经成为一种基础性的量子密码分析算法。为获取布尔函数的周期，经典算法需要指数式查询复杂度。使用 Simon 算法获得布尔函数周期的步骤如下：首先通过多次使用 Simon 算法获得 n 1 个线性独立的变量，然后使用经典算法（如高斯消除算法）解个数为 n 1 的二值线性方程组。使用 Simon 算法的主要优势在于它能够在多项式查询复杂度下获得函数 f(x)的周期。对 Simon 承诺条件弱化情形的研究起步较早。文献 12 说明了 Simon 函数的碰撞与测量结果之间的确切关系，证明了在大多数随机情况下，额外的碰撞不会导致 Simon 算法攻击的复杂性显著增加。Simon 函数应避免碰撞过大，现在大多数基于 Simon 算法的密码分析都使用以下的冲突假设(f,s)=maxt0,1n0,sPxf(x)=f(x t)612(1)式中：max 为取最大值函数；Px为概率；(f,s)为量化函数 f(x)距离 Simon 承诺远近的参数。(f,s)与 Simon 算法的失效概率有着紧密联系。(f,s)越接近 1，则函数发生冲突的概率越大，Simon 算法的失效概率越大；(f,s)越接近 0，函数越接近一个完美的周期函数，Simon算法的失效概率越低。给出(f,s)6 1/2 的假设意味着使用 Simon 函数可以在 O(n)次的查询后找到周期 s。文献 12 的进一步结论是，经过 cn 次查询后，可返回计算周期 s 的概率为1 2n(0.6454)cn。特殊地，当取 c=4，n=8 时，得到周期 s 的概率约为 0.998。即 Simon算法作为子程序（重复地执行 4n 次）将保证成功概率接近 1。文献 13 对上述的结论进行了泛化：定义了 4 个扩展的布尔隐藏周期问题，利用函数的周期个数以及是否具有额外碰撞这两个属性进行划分，扩展了 4 种弱化的 Simon 算法的承42应用科学学报第42卷诺条件，经证明这 4 种弱化的承诺条件均可以使用 Simon 算法进行多项式求解。弱化承诺下Simon 算法仍有很多其他相关的重要性质，文献 14 发现在弱化承诺下 Simon 算法具有以下重要性质：若一个函数存在周期，则该函数只存在唯一周期的概率接近 1。文献 15 指出只需要前向蕴含的承诺 x=y s f(x)=f(y)就能够利用 Simon 算法获得独立向量。弱化承诺下 Simon 算法在对称密码分析中具有很强的实用性，促使量子周期攻击快速发展。2.2基于周期构建的攻击量子周期攻击是利用解布尔函数周期问题的量子算法进行密码分析的攻击方法。Simon算法完成量子周期攻击的主要思路是：在目标密码体制中构建函数，该函数即为布尔隐藏周期问题中的函数 f，通过结合 Simon 算法和解传统方程组的方法来确定函数的周期，进而对指定密码体系进行分析。文献 16 利用 Simon 算法实现了开创性的量子密码分析。其中展示的攻击方法是利用量子叠加模型在 O(n)的量子时间复杂度下构建了一个区分器。随后，文献 17 通过构建 Even-Mansour 密码体制上的周期函数实施了量子周期攻击，获取了 Even-Mansour 密码体制的密钥，表明 Even-Mansour 密码体制是不安全的。文献 15 利用 Simon 算法对固定长度密码块链消息认证码（cipher block chaining message authentication code,CBC-MAC）进行了伪造攻击，能够为以前未查询过的消息生成有效的标签。文献 18 所构建的函数f(x)=Ex(m),Exs(m)周期为 s，而 s 正好是相关密钥攻击模型中需要寻找的密钥 K。使用 Simon 周期构建可形成量子滑动攻击。文献 19 针对替换-置换网络（substitution-permutation network,SPN）和 Feistel 密钥簇，在经典滑动攻击的基础上，根据不同的滑动类型（如扭曲滑动，互补滑动和镜像滑动），提出了较为完整的量子滑动攻击。这种量子滑动攻击的主要思路是：使用经典滑动攻击满足的滑动属性构建 Simon 函数，构建的周期 s 中包含所寻找的密钥值 K。文献 20 使用量子滑动攻击对 2/4K-Feistel 和 2/4K-DES 进行密码分析，相比经典的滑动攻击，该方法在时间复杂度上获得了指数级的加速。文献 21 给出了一种在旋转密码块结构上构建周期函数的新方法。对于可调整分组密码，固定 t06=t1，构建函数 f(x)=Ek(x h(t0)h(t0)Ek(x h(t1)h(t1)，此函数的周期为 s=h(t0)h(t1)。文献 22 提出了一种自动搜索周期函数的方法，其主要思想是将计算复杂度中的电路理论引入自动测试中。这种方法涉及使用一系列电路来表示对应密码体制中的合理函数，然后测试所有可能的电路配置来确定这些函数的周期性特征。通过这种自动化方法结合 Simon 算法，实施了有效密钥恢复攻击。在 2017 年的欧洲密码学会议上，文献 23 介绍了一种新策略来对抗文献 21 中描述的攻击方法。这种策略建议用更复杂的运算方法替换传统的异或运算，以增强安全性。鉴于效率和实现方案的均衡，常见的替换方案是模加运算。文献 23 说明此改进可以抵抗量子选择明文攻击。文献 24 对 Kuperberg 算法进行了改进，显著降低了针对 Poly1305（使用模加运算的加密算法）的攻击成本。相较于通用攻击的复杂度为2n，这种改进将复杂度降至 2O(n)，显著提高了效率。2.3离线计算方式的攻击在特定的攻击场景中，假设敌方只能通过传统（经典）方式访问加密体系，这种假设被称为离线计算方式。文献 25 对 Grover meets Simon 算法进行了改进，并提出了离线 Simon 算法。这种算法是 Q1 模型下的一种 Simon 算法，适用于在有限条件下进行加密分析。算法的主要思路是利用目标密码体制 g 以及密码体制中的公开函数 f 构造函数 g?f，在目标体制密码 g 上做经典查询得到量子态|gi。通过对 f 的量子叠加查询得到 g?f，在 g?f 上应用并行第1期冯晓宁，等：对称密码体制的量子攻击43化的 Simon 算法判定 g?f 是否具有周期性：如果 g?f 显示出周期性，则表明找到了正确的密钥。在这种情况下，可以利用 Grover 算法搜索正确密钥。文献 26 对离线 Simon 算法进行了更广泛的推广，指出 g 与 f 的结合方式不必局限于异或的方式。同时，g 也不需要仅限于排列函数。上述离线计算方式以高概率寻找到正确密钥和周期值，具有如下定理：当攻击者具有对 g 的经典查询权限时，离线 Simon 算法对 g 进行了 O(2n)次经典查询，时间复杂度为O(n3+nTf)2m/2)，其中 Tf表示量子查询一次 f 的时间，m 是 Grover meets Simon 算法中的常数。在实现离线计算方式的算法中，主要难点在于正确选择并组合 g 和 f。文献 27 在文献 25 的基础上使用离线计算方式构造对哈希计数器的新攻击。文献 28 给出了 Simon 离线计算方式的第 1 个完整实现，并估计了多种轻量级密码体制的攻击成本。文献 29 在对移动通信网中的 Milenage 算法集进行量子密码分析时，实现了离线 Simon 算法对相关密钥分析进行加速。3Grover 算法相关攻击的研究Grover 算法是典型的量子搜索算法，可解决无序搜索问题。Grover 算法作为一种高性能量子搜索算法，实现了对经典搜索算法的二次加速，在密码分析领域中备受瞩目。3.1Grover meets X算法Grover 算法能够与其他量子算法进行结合并作用在量子对称密码分析中，这一类算法被称为 Grover meets X 算法，其中 X 指结合的量子算法。将 Grover 算法整合到密码分析算法中被视为一种臃肿的操作。许多研究者应用了与 Grover 算法具有等效的放大器定理：设 A 是在量子比特上无测量的量子算法，量子算法 B:0,1q 0,1 是量子算法 A 的分类器，将 A 作用的结果分成 0 和 1，分类器 B 判定态 A|0i 为 1 的成功概率为 p，定义k=d/(4)e，sin2()=p，酉矩阵 Q=Q(A,B)=AS0A1SB，S0仅在|0i 态上起作用，那么经过 k 次迭代 QkA|0i，测量为 1 的概率至少为 max1 p,p。其中酉矩阵 SB定义为|xi=(|xi,B=1|xi,B=0(2)式中：B 为量子算法的分类器；|xi 为酉矩阵 SB作用的量子态。文献 30 证明了白化密钥不会增加 qCPA 下的安全性，提出一种 Grover 和 Simon 融合的量子算法，称此算法为 Grovermeets Simon 算法。此算法依赖延迟测量法则31和并行化 Simon 算法的技术，形成一种逻辑上的等价：当 Grover 算法猜测正确的密钥值时，所定义的函数拥有一个周期 s，且这个周期就是白化密钥的一部分。将融合算法应用于具有白化密钥的分组密码时，仅使用 Grover 算法进行给定分组密码的密钥恢复攻击，其复杂度等同于使用 Grover meets Simon 算法对白化密钥分组密码进行密钥恢复攻击的复杂度。Grover meets Simon 算法对 F 进行 O(n+m)2m/2)次量子查询，时间复杂度为 O(n+m)32m/2)，以常数概率发现正确密钥和周期值。Grover meets Simon 算法对后续研究者产生了深远的影响。文献 32 利用 Grover meetsSimon 算法实施对埃文-曼苏尔之和（sum of Even-Mansour,SoME）的密钥恢复攻击。针对文献 32 中提出的攻击方法，攻击效果在某些 SoME 变体中不够明显的问题，文献 33 进一步讨论了 SoME 密码体制变体攻击的情况。文献 34 应用了 Grover meets Simon 算法，对广义Feistel 结构进行了密钥恢复攻击。文献 35 提出了一个针对 Feistel 结构中子密钥恢复的通用攻击方法。在 R 轮的 Feistel 结构中，对后 R 3 轮子密钥进行 Grover 算法穷举，在前 3 轮44应用科学学报第42卷中构造了一个具有后面轮次密钥参数的 Simon 函数。当后 R 3 轮子密钥猜测正确时，定义的函数拥有一个周期。文献36 提出了一种结合Bernstein-Vazirani 算法和Grover 算法的新算法，用于对Feistel结构实施量子密钥恢复攻击。Grover 算法也可以与一些经典量子算法如 Deutsch-Jozsa 算法进行 meets 类的结合，但此类方法对于对称密码分析的作用尚未可知。3.2Grover on X算法使用 Grover 算法进行密钥恢复攻击涉及两个主要环节：首先，将已公开的经典算法转换成相应的量子版本；然后，在这个量子版本上实施 Grover 算法模块。对于对称密码体制，采用这种攻击方法在本小节中被称为“Grover on X 算法”，其中“X”代表特定的密码体制。这种命名方式旨在强调 Grover 算法在特定密码体制上的应用。美国国家标准与技术研究所在后量子公钥密码学领域提出所需的期望安全级别37。这些安全级别有助于理解使用 Grover 算法进行攻击的难度。Grover on X 算法的攻击难度取决于公开算法的量子实现和 Grover 算法模块。由于 Grover 算法模块一般是固定的（但是这并不意味着 Grover 算法模块的消耗是固定的），许多密码分析者通过优化经典对称密码体制的量子实现算法来降低 Grover 算法量子攻击的复杂度。Grover on X 算法的比较如表 1 所示。表 1 Grover on X 算法的比较Table 1 Comparison of Grover on X algorithms实现算法所需量子门所需 qubit文献X 门H 门Toffoli 门CNOT 门AES276.16276.65282.87282.99196938276.07271.65282.86283.21195339276.26271.65279.77282.37172940277.8271.65279.98282.62102541SIMON32/64243246245.51614224124424624625543文献 38 首次提出了一种量子穷举方法，该方法采用 Grover 算法搜索高级加密标准（advanced encryption standard,AES）的密钥值。从量子电路大小、量子比特数量、量子电路深度等方面分析了该穷举攻击的量子资源开销，其中量子电路的大小与整体量子电路消耗的通用量子逻辑门有关。文献 39 提出了一种简化 AES 算法的量子化版本，该电路采用zig-zag 结构以节约量子比特。文献 40 使用基于塔域分解的 S 盒，设计了 AES 的量子优化实现电路。文献 41 引入逆替代盒运算以减少 zig-zag 结构所需要的量子位，提出了一种减少AES 密钥表中量子位数的方法，使实现 AES 所需的量子比特大幅减少。研究者提出更多对称密码体制的 Grover 算法穷举攻击电路的实现方法。文献 42 提供了 SIMON 所有变体（SIMON 指的是一种对称密码体制，而 Simon 指的是一种量子算法）的量子化版本。该文献不仅详细列出了对 SIMON 密码体制进行 Grover 算法密钥恢复攻击所需的各种量子资源，如 NOT 门、CNOT 门和 Toffoli 门，还提供了实施该攻击所需的量子位第1期冯晓宁，等：对称密码体制的量子攻击45数以及 T-深度和总深度的具体信息。同时，描述了一种在 IBM 量子模拟器上实现的缩小版SIMON 变体。在这个 IBM 模拟器上，可以一定程度地恢复缩小版 SIMON 密码的密钥值。在文献 42 的研究基础上，文献 43 对 SIMON 变体的量子化版本进行了改进，减少了实现SIMON 所需的资源消耗（具体体现于 T-深度和全深度上）。3.3量子中间相遇攻击中间相遇攻击是一种常用于对称密码体制的攻击方法。在中间相遇攻击中，内部状态分别沿着两个独立路径（前向路径和后向路径）计算，最终通过匹配这两个路径，生成完整的路径解。量子中间相遇攻击可看作经典中间相遇攻击的变体，大部分的量子中间相遇攻击是基于 Grover 算法构建的。文献 44 发现，量子计算模型下可以显著加速由 Demiric 和 Selcuk 提出的中间相遇攻击（meet-in-the-middle attack designed by Demiric and Selcuk,DS-MITM），其中包含穷举差分技术。该研究将寻找 Claw 对问题的量子算法嵌入到区分器匹配和查询数据过程。在经典设置下，DS-MITM 方法攻击 6 轮 Feistel 过程时，需要的数据复杂度、时间复杂度以及内存复杂度均为 O(23n/4)。在 Q1 模型下，量子 DS-MITM 方法攻击需要 O(2n/q)的时间复杂度（其中 q 表示量子比特数）和 O(2n/2)次经典查询复杂度，最佳平衡点是 O(2n/2)。在 Q2模型下，最佳平衡点是 O(23n/4)。该研究说明 Q1 模型对经典情况是一个有效的提升；Q2 模型下是否对该攻击有较好的提升，是一个开放性的问题。文献 45 在文献 44 的基础上，针对超过 7 轮的 Feistel 结构，提出了 Q1 模型下的量子中间相遇攻击，这在一定程度上降低了时间复杂度。文献 46 使用文献 44 的方法攻击 AES-128，从而降低了攻击的时间复杂度。最为经典的时空-折中攻击是 Hellman 时空-折中攻击(包含常见的彩虹表技术)。经典情况下，Hellman 时空-折中攻击需要的时空权衡为 TM2D2=N2，T D2；文献 47 给出了量子设置下 Hellman 时空-折中攻击的时空权衡为 T4/3M2D2=N2，T D3/2。在中间相遇攻击的密钥恢复阶段，一种通用的量子加速思路是使用量子嵌套搜索算法达到二次加速的效果。文献 48 利用嵌套的量子搜索算法和 Ambainis 算法构建了飞去来器和混合飞去来器（一种融合了截断攻击的飞去来器）的量子版本，达到了近似二次加速的效果。矩形攻击是飞去来器攻击的进阶版本，近年来，基于矩形攻击的密钥恢复攻击技术发展迅猛。具有非线性关系的密钥之间更适合矩形攻击。文献 49 提出在进行矩形攻击之前先对关键单元进行猜测，并将这种猜测策略应用于量子环境中，从而实现加速。然而，这一领域的研究尚未受到足够的重视。文献 50 研究了量子不可能差分算法，并实现了早夭技术的量子化。主要思路是将早夭技术通用地表示为嵌套搜索问题，此嵌套搜索问题的复杂度为|K1|(T1+|K2|(T2+|Kl1|(Tl1+|Kl|Tl)，其中 Ki为搜索的密钥空间，Ti为每一级需要搜索的表空间。在嵌套搜索问题中多次利用放大器定理（目的在于降低迭代次数），使嵌套搜索问题的复杂度降低为p|K1|(T1+p|K2|(T2+p|Kl1|(Tl1+p|Kl|Tl)，从而实现二次加速。反弹技术是中间相遇攻击用来降低预计算时间复杂度的技巧。文献 51 首次对反弹技术进行了量子化，称为量子反弹技术。量子反弹技术效果显著，在攻击 AES-MMO 时，量子反弹技术能够增加一个加密轮次；在攻击 5 轮 Whirlpool 时，量子反弹技术的速度是经典攻击的两倍。为减少文献 51 对量子随机存储器模型（quantum random access memory,qRAM）的依赖，文献 52 结合非全活跃超级 S 盒技术以降低 qRAM 的使用。其他一些经典中间相遇攻击的量子化设置也逐渐变得流行。文献 53 对经典的在线-离线46应用科学学报第42卷中间相遇攻击进行了量子 Q1 模型的转换。文献 54 将两量子表合并算法与中间相遇攻击相结合，使得量子中间相遇攻击的时间和存储复杂度由列表大小决定。文献 55 对解剖攻击（经典中间相遇攻击的一种）进行了量子化改进，专门针对二次迭代加密的密钥恢复攻击，将寻找Claw 对问题的量子算法融入到该攻击策略中。在四次迭代加密的密钥恢复攻击环境下，这种二次迭代加密的密钥恢复方法被作为一个关键子程序加以应用。此外，该研究结合量子游走算法来搜索有效的中间值。最终，提供了比经典解剖攻击更为显著的增益效果。4量子差分攻击4.1Bernstein-Vazirani算法的研究Bernstein-Vazirani 算法（B-V 算法）是基于 Deutsch-Jozsa 算法发展出的一种变体算法56。分别称布尔函数 f:0,1n 0,1 和布尔函数 f:0,1n 0,1n为一位输出布尔函数和多位输出布尔函数。基于 B-V 算法对布尔函数线性结构的研究拉开了量子差分攻击的序幕。文献 57 提出了适用于多位输出布尔函数的广义 B-V 算法，与经典算法相比，该算法可以提供多项式级别的加速。广义 B-V 算法与密码属性测试方法关系密切，在基于广义B-V 算法的密码属性测试方法中，non-junta 测试表现出色。为确定布尔函数的概率分布，在文献 57 的基础之上，文献 58 重新对“距离”进行了定义，用以反映布尔函数概率分布与均匀分布的偏差。研究利用“距离”与沃尔什谱的关系，获得了学习弹性程度的量子算法。相比于经典算法，B-V 算法具有指数级别的加速效果，但其先验假设是当 f=a x 时，函数 f 与沃尔什谱建立联系。此限制是明显的，因为拥有这类表达形式的布尔函数无法涵盖所有可能的布尔函数族。更为严格的先验假设是一种非部分线性结构的承诺59，这意味着需要所有点 x 0,1n均需要满足线性结构的要求。Simon 算法与 B-V 算法具有紧密联系52。Simon 算法计算函数周期的一个正交向量，n个正交向量可计算出函数的周期值；B-V 算法计算函数线性结构的沃尔什系数，n 个沃尔什系数可计算出函数的线性结构。使用 Simon 算法进行攻击的思路是寻找使等式 F(x)=F(xa)成立的 a，即周期值。使用 B-V 算法进行攻击的思路是寻找等式 F(x)=F(x a)=b 成立的a 值，即线性结构。相比于 Simon 算法，使用 B-V 算法，扩充了攻击范围，即在 b=0 的情况下，线性结构变为了周期值。两者都可以用于量子周期攻击中，但 B-V 算法原理和 Simon 算法原理显然不同。两者在查找周期的过程以及获得每个向量的概率上存在差异，这意味着两者的成功率可能存在某种关联，但还未有此类文献讨论两者具体联系的情况。4.2两阶段的量子差分攻击研究差分密码分析在经典密码分析中是一种典型的选择明文攻击。与经典差分密码分析60相似，量子差分密码分析的过程分为两个主要阶段：量子差分攻击的第 I 阶段是识别出一些具有较高概率的差分特性；第 II 阶段则是根据这些发现的差分特性，测试潜在的子密钥候选项以恢复加密系统的主密钥。根据各个攻击阶段，将量子差分攻击进行分类与比较。总结表如表 2 所示。4.2.1量子差分攻击第 I 阶段文献 69 基于 B-V 算法，提出了一个多项式时间的量子算法，用于求解一位输出布尔函数 f:0,1n 0,1 的线性结构。记 Uf为布尔函数 f 的线性结构 Uif=a Fn2|f(x a)f(x)=i,x Fn2,(i=0,1)；布尔函数的沃尔什谱为 Sf(w)=PxFn2(1)f(x)+wx/2n；对于沃尔什系数集合 Nf=w Fn2|Sf(w)6=0，i 0,1，有 Uif=a Fn2|a w=第1期冯晓宁，等：对称密码体制的量子攻击47表 2 量子差分攻击方法分类Table 2 Classification of quantum differential attack methods类别攻击依赖文献攻击优势经典攻击基础局限量子差分攻击第 I阶段查找布尔函数线性结构的算法61提供寻找差分特征的应用方法密钥独立问题62-63获 得 不 可 能 差分、截断特征、小概率差分等差分特征中间未命中技术密钥独立问题64标签避免技术，与相关密钥分析模型结合相 关 密 钥 分 析模型使用攻击模型前需先评估并确保满足相关条件量子差分攻击第 II阶段Grover算法65消除传统攻击对表结构的依赖基于表的经典差分分析特 殊 差 分 攻 击（如截断）不可获得二次加速量子最大值/最小值框架，量子计数算法66具有典型的量子电路基于计数的经典差分分析需要量子并行化技术文献 66算法67将量子部分搜索算法应用于搜索过程基于计数的经典差分分析提高复杂度68消除量子并行化带来的错误基于计数的经典差分分析受限于二次加速的瓶颈i,w Nf。这个量子算法主要利用布尔函数的沃尔什谱来寻找线性结构。具体来说，当子集W 足够大后，就可以通过解线性方程 x w=i|w W 来获取函数 f 的线性结构。在经典情况下，获得子集 W 的复杂度为 O(n2n)，这意味着实际执行这种计算是不切实际的。通过多项式次数运行 B-V 算法，可以确定子集 W，并在多项式时间内求出一位输出布尔函数的线性结构。多位输出布尔函数的线性结构在量子差分攻击第 I 阶段使用广泛。在差分攻击（差分特征为 F(x)F(x in)=out）中，获取多位输出布尔函数的线性结构等同于识别出高概率的差分特征。对于加密块 E:0,1n 0,1m 0,1n，将加密块 E 分解为 n 个更小的组件函数 E1,E2,En。这里，每个 Ej(1 6 j 6 n)的输入是加密块 E 的输入，而输出则是加密块 E 的第 j 位输出，使用 n+m+1 个量子比特的 n 个 B-V 算法作用于每个 Ej函数上。在这个设置中，前 n 个量子比特被用于表示 n 位的明文，接下来的 m 个量子比特用于存储 m 位的密钥，而最后一个量子比特专门用于记录生成的密文的第 j 位。B-V 算法在每个Ej，1 6 j 6 n 函数上重复执行 O(p(n)次。经过 O(p(n)次循环后，算法通过构建一组线性布尔方程 a w=i,i=0,1 来确定函数的线性结构 a。因此，整个过程共需要 O(np(n)次循环来完成。最终，通过寻找每个 Ej函数的共同解，可以确定具有高概率的差分特征。文献64 提出了一种标签技术，有效解决了在计算公共解时遇到的指数次运算问题。48应用科学学报第42卷在经典方法中寻找差分特征时并不考虑输入的具体密钥，所寻找的差分特征与密钥无关。然而，在上述方法中，需要确保密钥以量子态的形式存在，并将这个密钥态作为输入，与回合制密码结合，形成一个新的函数。在非相关密钥模型下保持密钥态的一致性，即保证密钥差分为 0。在这种情况下，所寻找的差分特征并不是完全与密钥无关的。文献 61 介绍了两种利用 B-V 算法寻找差分特征的方法。第 1 种方法是在每个 S-Box 上单独应用量子算法。而第 2 种方法则将整个加密块作为一个单一实体，在整个过程中应用量子算法。相较于传统的差分分析，第 2 种方法有着明显的优势：它将目标密码的所有差分回合视作一个整体，仅关注输入和输出之间的差异，而非特定的差分特性。这种方法在一定程度上减轻了传统差分密码分析当轮数增加时在寻找差分特征上遇到的困难。文献 62 介绍了 3 种量子算法：第 1 种是通用的量子差分密码分析；第 2 种是应用中间未命中技术的量子不可能差分密码分析，这一方法在文献 59 中得到了详细分析；第 3 种则是一种新型的量子小概率差分分析。此外，文献 63 提出了一种新的方法来查找块密码的截断差分特征，并对该算法的复杂性进行了严格分析。文献 64 将 B-V 算法应用于相关密钥模型。在这一研究中，对攻击的有效性进行了严格分析，并提出了算法有效工作的两个具体条件。4.2.2量子差分攻击第 II 阶段研究人员专注于基于计数的经典差分密码分析。这种方法的工作原理是统计每个候选子密钥值 ki满足条件 E1ki(Ek(x)E1ki(Ek(x in)=out（也称为密钥公式）的次数，其中次数最多的候选子密钥值 ki就是经典差分密码分析得出的正确密钥值。在量子版本的实现中，采用了修改后的量子计数算法70（该算法在量子查找最大值或最小值的框架71下运行），以获得正确密钥值。具体而言，实现密钥公式的量子电路被整合到量子计数算法中，从而能够计算出每个潜在候选子密钥值 ki满足密钥公