Page 378 - 《软件学报》2026年第5期
P. 378
软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2026,37(5):2257−2273 [doi: 10.13328/j.cnki.jos.007448] [CSTR: 32375.14.jos.007448] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563
*
三类非平衡广义 Feistel 结构的量子中间相遇攻击
杜小妮 1,2 , 吴家辉 1 , 徐 莹 1 , 孙 瑞 1
1
(西北师范大学 数学与统计学院, 甘肃 兰州 730070)
2
(西北师范大学 密码技术与数据分析重点实验室, 甘肃 兰州 730070)
通信作者: 杜小妮, E-mail: 2023221866@nwnu.edu.cn
摘 要: 研究 3 类非平衡广义 Feistel 结构的中间相遇攻击, 并在 Q1 模型下对这 3 类结构进行量子中间相遇攻击.
首先, 采用多重集和差分枚举技术对 3 分支 Type-III 型广义 Feistel 结构构建 4 轮中间相遇区分器, 分别向前向后
扩展 1 轮进行 6 轮中间相遇攻击, 并利用 Grover 算法和量子爪搜索算法对该结构进行 6 轮量子密钥恢复攻击, 该
攻击所需的时间复杂度为 O(2 3ℓ/2 ·ℓ) 次量子查询, 其中ℓ为广义 Feistel 结构的分支长度. 其次, 对 3 分支 Type-I 型广
义 Feistel 结构的 9 轮区分器分别向前向后扩展 1 轮进行 11 轮中间相遇攻击及量子密钥恢复攻击, 相应的时间复
杂度分别为 O(2 ) 次 11 轮加密和 O(2 3ℓ/2 ·ℓ) 次量子查询. 最后, 以 3-cell 型广义 Feistel 结构为例探讨了 n-cell 型广
2ℓ
义 Feistel 结构的量子中间相遇过程, 对 n-cell 型广义 Feistel 结构构建 2n 轮中间相遇区分器, 并进行 2(n+1) 轮中间
2ℓ
相遇攻击及量子密钥恢复攻击, 且时间复杂度分别为 O(2 ) 次 2(n+1) 轮加密和 O(2 3ℓ/2 ·ℓ) 次量子查询. 结果表明,
相比于经典环境, Q1 模型下消耗的时间复杂度更低.
关键词: 广义 Feistel 结构; 量子中间相遇攻击; Q1 模型; 量子爪搜索算法; Grover 算法
中图法分类号: TP309
中文引用格式: 杜小妮, 吴家辉, 徐莹, 孙瑞. 三类非平衡广义Feistel结构的量子中间相遇攻击. 软件学报, 2026, 37(5): 2257–2273.
http://www.jos.org.cn/1000-9825/7448.htm
英文引用格式: Du XN, Wu JH, Xu Y, Sun R. Quantum Meet-in-the-middle Attacks on Three Types of Unbalanced Generalized Feistel
Structures. Ruan Jian Xue Bao/Journal of Software, 2026, 37(5): 2257–2273 (in Chinese). http://www.jos.org.cn/1000-9825/7448.htm
Quantum Meet-in-the-middle Attacks on Three Types of Unbalanced Generalized Feistel
Structures
1
1
1,2
DU Xiao-Ni , WU Jia-Hui , XU Ying , SUN Rui 1
1
(College of Mathematics and Statistic, Northwest Normal University, Lanzhou 730070, China)
2
(Key Laboratory of Cryptography and Data Analytics, Northwest Normal University, Lanzhou 730070, China)
Abstract: This study investigates meet-in-the-middle attacks on three types of unbalanced generalized Feistel structures and conducts
quantum meet-in-the-middle attacks in Q1 model. First, for the 3-branch Type-III generalized Feistel structure, a 4-round meet-in-the-
middle distinguisher is constructed using multiset and differential enumeration techniques. By expanding one round forward and one round
backward, a 6-round meet-in-the-middle attack is conducted. With the help of Grover’s algorithm and the quantum claw finding algorithm,
3ℓ/2
a 6-round quantum key recovery attack is performed, requiring O(2 ·ℓ) quantum queries, where ℓ is the branch length of the generalized
Feistel structure. Then, for the 3-branch Type-I structure, a 9-round distinguisher is similarly extended by one round in both directions to
2ℓ
conduct an 11-round meet-in-the-middle attack and a quantum key recovery attack with time complexities of O(2 ) 11-round encryptions
3ℓ/2
and O(2 ·ℓ) quantum queries. Finally, taking the 3-cell generalized Feistel structure as a representative case, this study explores a
quantum meet-in-the-middle attack on an n-cell structure. A 2n-round meet-in-the-middle distinguisher is constructed, enabling a 2(n+1)-
2ℓ
round meet-in-the-middle attack and quantum key recovery attack. The associated time complexities are O(2 ) 2(n+1)-round encryptions
* 基金项目: 国家自然科学基金 (62172337); 甘肃省自然科学基金重点项目 (23JRRA685); 甘肃省基础研究创新群体基金 (23JRRA684)
收稿时间: 2025-01-11; 修改时间: 2025-03-08; 采用时间: 2025-04-19; jos 在线出版时间: 2025-08-20
CNKI 网络首发时间: 2025-08-20
