Paper 2026/2171

Improved Quantum Linear Key-Recovery Attacks with Walsh-Spectrum Puncturing

Abstract

Quantum linear key-recovery attacks using QFT-based correlation state preparation can achieve superquadratic speedups, but their complexity grows rapidly with the active subkey dimension, potentially erasing the advantage over Grover's search. WSP (EUROCRYPT 2024) provides a natural mechanism for alleviating this bottleneck by replacing the key-recovery map with a spectrally punctured approximation of smaller active dimension. In this work, we establish a puncture-aware framework for QFT-based quantum key recovery, extending quantum linear cryptanalysis to key-recovery problems whose active-subkey dimension can be reduced through spectral puncturing. We further propose Q-Puncture, an automated optimization method tailored to quantum key-recovery complexity. Applied to Serpent, RECTANGLE-128, and PIPO-128, Q-Puncture yields a new family of punctured quantum linear key-recovery attacks whose modeled quantum complexities improve upon generic Grover search. The resulting attacks improve upon comparable QFT-based results, extend them to new settings, and provide further examples in which structured quantum cryptanalysis surpasses the generic quadratic speedup of Grover's search.