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

DOI10.1007/S11128-022-03715-2MaRDI QIDQ6043544zbMATH OpenOpenAlexFDO

Authors Yinsong Xu, Zheng Yuan

Publication date 23 May 2023

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

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)

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.

Recommendations

• Quantum Demiric-Selçuk meet-in-the-middle attacks: applications to 6-round generic Feistel constructions
• Quantum all-subkeys-recovery attacks on 6-round Feistel-2^ structure based on multi-equations quantum claw finding
• New Demiric–Selçuk meet-in-the-middle attacks on Misty and Feistel schemes
• Quantum Demiric-Selcuk meet-in-the-middle attacks on reduced-round AES
• Quantum Key Recovery Attacks on 3-Round Feistel-2 Structure Without Quantum Encryption Oracles

Cites work

• A Meet-in-the-Middle Attack on 8-Round AES
• All subkeys recovery attack on block ciphers: extending meet-in-the-middle approach
• Breaking symmetric cryptosystems using quantum period finding
• Extended meet-in-the-middle attacks on some Feistel constructions
• Generic key recovery attack on Feistel scheme
• Grover meets Simon -- quantumly attacking the FX-construction
• On quantum slide attacks
• On the Power of Quantum Computation
• Preimages for step-reduced SHA-2
• Quantum Algorithms for Element Distinctness
• Quantum Complexity Theory
• Quantum Demiric-Selçuk meet-in-the-middle attacks: applications to 6-round generic Feistel constructions
• Quantum Walk Algorithm for Element Distinctness
• Quantum attacks on some Feistel block ciphers
• Quantum chosen-ciphertext attacks against Feistel ciphers
• Quantum forgery attacks on COPA, AES-COPA and marble authenticated encryption algorithms
• Quantum random access memory
• The Data Encryption Standard (DES) and its strength against attacks
• The security of Feistel ciphers with six rounds or less
• Upper Bounds for the Security of Several Feistel Networks
• Using Bernstein-Vazirani algorithm to attack block ciphers

Cited in

(3)

• Improved Meet-in-the-Middle Distinguisher on Feistel Schemes
• Quantum Key Recovery Attacks on 3-Round Feistel-2 Structure Without Quantum Encryption Oracles
• New Demiric–Selçuk meet-in-the-middle attacks on Misty and Feistel schemes

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)