Quantum attacks on Feistel constructions have attracted much attention from worldwide cryptologists. To reduce the time complexity of quantum attacks on 7-round Feistel construction, we propose a novel quantum meet-in-the-middle (QMITM) attack in Q1 model. Inspired by Hosoyamada et al.'s work [Hosoyamada2018A], we have introduced quantum computing in the offline computation of the classic meet-in-the-middle (MITM) attack [Guo2016]. In the attack, the differential characteristic of 7-round Feistel construction is given via 5-round distinguisher firstly. And then we propose a quantum claw finding algorithm based on quantum walk, which speeds up the process of finding a match in the offline computation phase. The keys in 7-round Feistel construction could be recovered by the match at last. Compared with quantum attacks in Q2 model, our attack reduces the time complexity from $O({2^{3n/4}})$ to $O({2^{2n/3}})$, and is significantly better than classic attacks. Moreover, our attack belongs to Q1 model, which is more practical than Q2 model.
翻译:对Feistel建筑的量子攻击引起了世界范围内的密码学家的极大关注。为了减少对7轮Feestel建筑的量子攻击的时间复杂性,我们提议在Q1模型中采用新型的量子会议(QMITM)攻击。在Hosoyamada等人的工作[Hosoyamada2018A]的启发下,我们引入了量子计算,在经典中场会议(MITM)攻击的离线计算中采用了量子计算[Guo2016]。在这次攻击中,7轮Feestel建筑的差别性特征首先通过5轮分辨器进行。然后我们提出基于量子行走的量子抓取算算算算法,加速了在离线计算阶段找到匹配的过程。7轮Feestel建筑的钥匙可以最后通过匹配。与Q2模型的量子攻击相比,我们的攻击降低了时间复杂性,从$O(%2×3N/4 ⁇ 4美元)到$($2×2n/3 ⁇ _Q),并且远比典型的攻击更好。