轻量级分组密码Piccolo的量子密码分析  

Quantum cryptanalysis of lightweight block cipher Piccolo

作　　者：杜小妮 王香玉[1] 梁丽芳 李锴彬 DU Xiaoni;WANG Xiangyu;LIANG Lifang;LI Kaibin(College of Mathematics and Statistic,Northwest Normal University,Lanzhou 730070,China;Key Laboratory of Cryptography and Data Analytics,Northwest Normal University,Lanzhou 730070,China;College of Computer Science and Engineering,Northwest Normal University,Lanzhou 730070,China)

机构地区：[1]西北师范大学数学与统计学院,甘肃兰州730070 [2]西北师范大学密码技术与数据分析重点实验室,甘肃兰州730070 [3]西北师范大学计算机科学与工程学院,甘肃兰州730070

出　　处：《通信学报》2023年第6期175-182,共8页Journal on Communications

基　　金：国家自然科学基金资助项目(No.62172337);甘肃省自然科学基金重点资助项目(No.23JRRA685)。

摘　　要：根据Piccolo算法RP置换的结构特点,提出3轮量子区分器,并用Grover meets Simon算法进行6轮量子密钥恢复攻击。分析结果表明,该攻击可恢复密钥56 bit,时间复杂度为2^(28),共需量子比特数为464;当攻击轮数大于6轮时,时间复杂度为2^(28+16(r-6)),降至Grover量子暴力搜索的1/2^(68)。与传统差分和线性分析相比,所提攻击方法时间复杂度更低,且较Grover暴力搜索的时间复杂度大幅降低,为后续轻量级分组密码的量子攻击的研究奠定了基础。By taking the characteristics of the structure of Piccolo algorithm RP permutation into consideration,a 3-round quantum distinguisher was proposed.Based on Grover meets Simon algorithm,the 6-round of quantum key recovery attack was given.The results show that the key can be recovered 56 bit with the time complexity 2^(28) and the occupation of 464 qubit.Moreover,if attack rounds r>6,the time complexity is 2^(28+16(r-6)),which is 1/2^(68) of Grover quantum brute-force search.The time complexity of the proposed attack method is significantly reduced compared with Grover search and is also better than that of traditional cryptanalysis,which lays a foundation for the subsequent research on quantum attacks of lightweight block ciphers.

关 键 词：量子密码分析 Piccolo算法 GROVER算法 Simon算法 

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