arXiv:2610.27506
Quantum Cryptanalysis on Two Feistel-Type Constructions
Yan-Ying Zhu, Bin-Bin Cai, Fei Gao, Song Lin
Abstract
With the rapid advancement of quantum computing, the security of traditional cryptographic systems is facing significant challenges. As a fundamental component of symmetric cryptography, block ciphers have attracted increasing attention regarding their quantum security in recent years. In this paper, we propose new quantum attacks on two Feistel-type constructions, i.e., New Structure IV and the lightweight block cipher LBlock, under the quantum chosen-plaintext attack (qCPA) model. First, we construct an 8-round quantum distinguisher for New Structure IV and perform an $r(r>12)$-round quantum key-recovery attack. Compared with Li et al.'s qCPA-based result presented at INSCRYPT 2024, our attack reduces the time complexity by a factor of $2^{n/2}$, where $n$ denotes the subkey length. Second, we design a 9-round quantum distinguisher for LBlock and extend it to an $r(r>15)$-round quantum key-recovery attack. The proposed quantum distinguisher covers one more round than Liu et al.'s automated-search distinguisher at ASIACRYPT 2025, which results in a $2^{16}$ reduction in the time complexity of our $r$-round quantum key-recovery attack on LBlock. Furthermore, by analyzing the structure of the round function and the key scheduling of LBlock, we reduce the subkey guess space for the 15-round attack from 76 bits to 52 bits, lowering the time complexity from \(O(2^{38})\) to \(O(2^{26})\) by a factor of \(2^{12}\).
AI Summary
The paper studies quantum chosen-plaintext attacks (qCPA) on New Structure IV, a four-branch Feistel-type construction, and the lightweight block cipher LBlock. It seeks longer Simon-based distinguishers and lower-cost subkey recovery using the existing Grover-meets-Simon framework. For New Structure IV, it constructs an 8-round distinguisher, extending the previously reported 7-round result. Plaintexts have the form $(c,\alpha_b,x,x)$; XORing selected ciphertext branches across two choices of $\alpha_b$ produces a function with an explicitly derived XOR period. Appending rounds and searching over subkeys gives a stated attack complexity of $O(2^{((r-12)n+3n)/2})$ for $r>12$, where $n$ is the branch/subkey length, improving the previous bound by a factor of $2^{n/2}$. For LBlock, it constructs a 9-round distinguisher, versus the previous 8 rounds, by tracking dependencies through the nibble-level round structure and deriving a periodic function from one output nibble. Partial decryption through six additional rounds requires guessing 76 subkey bits, giving a stated 15-round complexity of $O(2^{38})$. Nine relations derived from the invertible key schedule reduce the independent guesses to 52 bits and the stated complexity to $O(2^{26})$. The generic extension to $r>15$ rounds costs $O(2^{38+16(r-15)})$. The attacks require coherent chosen-plaintext oracle access; the concrete LBlock improvement concerns 15 of its 32 rounds. Extension to other constructions, further distinguisher improvements, and scalability under stronger attack models are left for future work.
Central claim may not hold: The periodicity lemmas do not establish the uniqueness or additional-collision conditions needed to justify recovery of their specified hidden periods. The key-recovery attacks assume without justification that only correct guessed subkeys yield periodic functions, and this assertion is false for the allowed affine round functions of New Structure IV. The concrete LBlock attack uses a four-bit-domain periodicity verifier without establishing sufficiently sound wrong-key rejection or providing additional tests to justify searching 52 guessed bits.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.