Quantum meet-in-the-middle attack on Feistel construction

Inspired by Hosoyamada and Sasaki (in: International conference on security and cryptography for networks, pp 386–403. Springer, 2018), we propose a new quantum meet-in-the-middle (QMITM) attack on r-round (r≥7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r \ge 7$$\end{document}) Feistel construction to reduce the time complexity, which is based on Guo et al. (Des Codes Cryptogr 80(3):587–618, 2016) classical meet-in-the-middle (MITM) attack. In our attack, we adjust the size of truncated differentials to balance the complexities between constructing the tables and querying firstly and introduce a quantum claw finding algorithm to solve the collision search problem in classical MITM attack. The total time complexities of our attack are only O(22n/3·n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O({2^{2n/3}} \cdot n)$$\end{document}, O(219n/24·n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O({2^{19n/24}} \cdot n)$$\end{document} and O(2(r-5)n/4·n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O({2^{(r - 5)n/4}} \cdot n)$$\end{document}, when r=7\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r = 7$$\end{document}, r=8\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r = 8$$\end{document} and r>8\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r > 8$$\end{document}, lower than classical and quantum attacks. Moreover, our attack belongs to Q1 model and is more practical than other quantum attacks.