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

DOI10.1007/S11128-022-03715-2arXiv2107.12724OpenAlexW4353063257MaRDI QIDQ6043544FDOQ6043544

Yinsong Xu, Zheng Yuan

Publication date: 23 May 2023

Published in: Quantum Information Processing (Search for Journal in Brave)

Abstract: Inspired by Hosoyamada et al.'s work [14], we propose a new quantum meet-in-the-middle (QMITM) attack on $r$-round ($rge7$) Feistel construction to reduce the time complexity. Similar to Hosoyamada et al.'s work, our attack on 7-round Feistel is also based on Guo et al.'s classical meet-in-the-middle (MITM) attack [13]. The classic MITM attack consumes a lot of time mainly in three aspects: construct the lookup table, query data and find a match. Therefore, parallel Grover search processors are used to reduce the time of constructing the lookup table. And we adjust the truncated differentials of the 5-round distinguisher proposed by Guo et al. to balance the complexities between constructing the lookup table and querying data. Finally, we introduce a quantum claw finding algorithm to find a match for reducing time. The subkeys can be recovered by this match. Furthermore, for $r$-round ($r>7$) Feistel construction, we treat the above attack on the first 7 rounds as an inner loop and use Grover's algorithm to search the last $r-7$ rounds of subkeys as an outer loop. In summary, the total time complexity of our attack on $r$-round ($rge7$) is only $O(2^{2n/3+(r-7)n/4})$ less than classical and quantum attacks. Moreover, our attack belongs to Q1 model and is more practical than other quantum attacks.

Full work available at URL: https://arxiv.org/abs/2107.12724

zbMATH Keywords

Feistel constructionQ1 modelquantum meet-in-the-middle attackquanutm claw finding algorithm

Mathematics Subject Classification ID

Quantum computation (81P68)

Cites Work

• On the Power of Quantum Computation
• Quantum Complexity Theory
• Quantum Walk Algorithm for Element Distinctness
• The Data Encryption Standard (DES) and its strength against attacks
• The security of Feistel ciphers with six rounds or less
• Generic Key Recovery Attack on Feistel Scheme
• All Subkeys Recovery Attack on Block Ciphers: Extending Meet-in-the-Middle Approach
• Upper Bounds for the Security of Several Feistel Networks
• Quantum Random Access Memory
• A Meet-in-the-Middle Attack on 8-Round AES
• Preimages for step-reduced SHA-2
• On quantum slide attacks
• Grover meets Simon -- quantumly attacking the FX-construction
• Breaking Symmetric Cryptosystems Using Quantum Period Finding
• Quantum Demiric-Selçuk meet-in-the-middle attacks: applications to 6-round generic Feistel constructions
• Quantum attacks on some Feistel block ciphers
• Quantum chosen-ciphertext attacks against Feistel ciphers
• Quantum Algorithms for Element Distinctness
• Extended meet-in-the-middle attacks on some Feistel constructions
• Using Bernstein-Vazirani algorithm to attack block ciphers
• Quantum forgery attacks on COPA, AES-COPA and marble authenticated encryption algorithms

Cited In (2)

• Improved Meet-in-the-Middle Distinguisher on Feistel Schemes
• Quantum Key Recovery Attacks on 3-Round Feistel-2 Structure Without Quantum Encryption Oracles

This page was built for publication: Quantum meet-in-the-middle attack on Feistel construction

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6043544)