Quantum Cryptanalysis on Two Feistel-Type Constructions
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 2n/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 216 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(238) to O(226) by a factor of 212.
Related
- Cipher-Structure-Aware Variational Quantum Cryptanalysis: A Reversible Public-Diagnostic Framework
- Grammatical Constructions for Binomial Convolutions of Fibonacci-Type Numbers and Their Products
- Effective-Hamiltonian Quantum Solvers for Differential Equations: Alternative Constructions and Function Encodings
- Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal Constructions
- Generalised Bit-Vector Abstractions for Formal Verification of Quantum Error-Detection and Entanglement Circuits over {H,X,C-NOT}: CSS Constructions, Soundness, and Mutation-Based Validation
BibTeX
@misc{zhu2026quantum,
title = {{Quantum Cryptanalysis on Two Feistel-Type Constructions}},
author = {Yan-Ying Zhu and Bin-Bin Cai and Fei Gao and Song Lin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.27506},
eprint = {2610.27506},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.27506},
}
RIS
TY - UNPB
TI - Quantum Cryptanalysis on Two Feistel-Type Constructions
AU - Yan-Ying Zhu
AU - Bin-Bin Cai
AU - Fei Gao
AU - Song Lin
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.27506
UR - https://arxiv.org/abs/2610.27506
AB - 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.
ER -