Tight Analysis of Grover-Meets-Simon and Alg-PolyQ2 Attacks via Formalizing Quantum Rank-Solving under Deferred Measurement

Abstract The combination of quantum algorithms is one promising approach to attacking symmetric cryptography. In this paper, we study in detail the Grover-meets-Simon and Alg-PolyQ2 algorithms under deferred measurement, which combine the ideas of Grover’s and Simon’s algorithms and are applicable to attacking the FX construction. By converting intermediate measurements into unitary operations deferred to the end of the quantum circuit, both quantum algorithms involve a quantum rank-solving problem. To address it, we first provide a formal analysis of the generalized quantum Gauss–Jordan elimination and characterize the resulting quantum state after the corresponding unitary operations, which serves as a subroutine in these two algorithms. Subsequently, we derive the tight bounds of the attack success probability of these two algorithms based on the initial amplitude, offering a novel perspective that confirms their effectiveness. Furthermore, our research perspective provides an idea for analyzing the attack success probability for some quantum algorithms integrating Grover’s algorithm without considering quantum input length, and contributes to a deeper understanding of these attacks’ underlying mechanisms under the deferred measurement principle.