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),并且远比典型的攻击更好。

0
下载
关闭预览

相关内容

如何构建你的推荐系统?这份21页ppt教程为你讲解
专知会员服务
64+阅读 · 2021年2月12日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
Fariz Darari简明《博弈论Game Theory》介绍,35页ppt
专知会员服务
109+阅读 · 2020年5月15日
经济学中的数据科学,Data Science in Economics,附22页pdf
专知会员服务
35+阅读 · 2020年4月1日
FlowQA: Grasping Flow in History for Conversational Machine Comprehension
专知会员服务
28+阅读 · 2019年10月18日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
已删除
将门创投
5+阅读 · 2019年4月29日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
Arxiv
0+阅读 · 2021年11月18日
Arxiv
6+阅读 · 2021年6月24日
Arxiv
4+阅读 · 2018年4月30日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关资讯
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
已删除
将门创投
5+阅读 · 2019年4月29日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
分布式TensorFlow入门指南
机器学习研究会
4+阅读 · 2017年11月28日
Top
微信扫码咨询专知VIP会员