基于D-Wave Advantage的量子计算实用化SPN结构对称密码攻击研究  

Research on Quantum Computing for Practical SPN Structure Symmetric Ciphers Attacks Using the D-Wave Advantage

作　　者：裴植 洪春雷 王启迪 胡巧云 王潮[1] PEI Zhi;HONG Chun-Lei;WANG Qi-Di;HU Qiao-Yun;WANG Chao(Key Laboratory of Specialty Fiber Optics and Optical Access Networks,Shanghai University,Shanghai 200444)

机构地区：[1]上海大学特种光纤与光接入网重点实验室,上海200444

出　　处：《计算机学报》2025年第1期234-248,共15页Chinese Journal of Computers

基　　金：密码科学技术全国重点实验室开放课题基金资助。

摘　　要：截至2023年,谷歌的量子霸权芯片Sycamore尚不能用于密码攻击。量子计算在理论上对公钥密码有致命性威胁,但对对称密码影响甚微,目前业内已经从缩减版密码算法开始积极探索对称密码的量子攻击。SPN结构是对称密码算法中的一种代表性结构,目前基于真实量子计算机的各类量子算法均未能对该结构未经缩减的全规模密码算法进行攻击。基于量子退火算法独有的隧穿效应,使得该算法有利于科学问题的指数级解空间搜索,可将其视为一类具有全局寻优能力的人工智能算法。受传统密码分析方法的影响,本文提出一种对称密码攻击架构:量子退火耦合传统数学方法密码攻击的新型计算架构——QuCMC(Quantum Annealing-Classical Mixed Cryptanalysis)。基于该架构,首先利用可分性刻画SPN结构对称密码算法的线性层和非线性层传播规律,将区分器搜索问题转化为MILP模型求解问题。进一步将MILP模型转化为D-Wave CQM模型,在求解该模型的过程中利用量子波动产生的量子隧穿效应跳出传统智能算法极易陷入的局部亚优解,获得更优的解,即攻击目标对称密码算法的积分区分器。本文使用D-Wave Advantage量子计算机攻击了PRESENT、GIFT-64、RECTANGLE三种SPN结构代表算法,均成功搜索到最长9轮的积分区分器。并且实验结果表明,量子退火算法在跳出局部亚优解能力与降低求解时间两个方面,均优于经典启发式全局寻优算法模拟退火。本研究首次成功利用真实量子计算机对多种全规模SPN结构对称密码算法完成了攻击,攻击效果与传统数学方法持平。The emergence of quantum computers brings new challenges and opportunities for the security analysis of modern cryptography.The nascent interdisciplinary realm of quantum computing and symmetric ciphers holds immense potential,with numerous unexplored problems awaiting comprehensive investigation.As of 2023,Google's quantum supremacy chip Sycamore is still not capable of performing cryptanalysis.Quantum computing is widely regarded as a significant threat to the security of public key cryptography,but it has little impact on symmetric ciphers.The prospect of quantum computing attacks on symmetric ciphers presents both an exhilarating and formidable challenge.Currently,the industry is starting to actively explore quantum computing attacks on symmetric ciphers,initially focusing on reduced-version algorithms.SubstitutionPermutation Network(SPN)structure is a representative structure of symmetric cipher algorithms,and currently,various quantum algorithms have not been able to attack full-scale SPN structure symmetric cipher algorithms.The quantum annealing algorithm proposed in 1994 aims to solve the problem of finding the minimum value of a multivariate function.The quantum annealing algorithm can empower various fields with diverse applications,including but not limited to financial services,manufacturing logistics,deep neural networks,cryptanalysis and design,machine learning,and city brain.Thanks to the unique tunneling effect of quantum annealing algorithm,this algorithm is advantageous for exponential search space exploration of scientific problems.It can be regarded as a class of artificial intelligence algorithms with global optimization capabilities.Inspired by traditional cryptanalysis methods,we proposed a novel computational architecture for symmetric cryptanalysis:Quantum Annealing-Classical Mixed Cryptanalysis(QuCMC),which combines the quantum annealing algorithm with traditional mathematical methods.Utilizing this architecture,we initially applied the division property to describe the propagation rule

关 键 词：对称密码 量子计算 量子退火 D-Wave量子计算机 量子隧穿效应 

分 类 号：TP309[自动化与计算机技术—计算机系统结构]