Tight Bounds for Simon’s Algorithm

Belal Ehsan Baaquie, L. C. Kwek

Richard J. Lipton, Kenneth W. Regan

Reece Robertson, Emery Doucet, Ernest Spicer +1 more

Tharrmashastha Sapv, Debajyoti Bera, Arpita Maitra +1 more

Xavier Bonnetain

Simon’s algorithm is the first example of a quantum algorithm exponentially faster than any classical algorithm, and has many applications in cryptanalysis. While these quantum attacks are often extremely efficient, they are generally missing some precise cost estimate. This article aims at resolving this issue by computing precise query costs for the different use cases of Simon’s algorithm in cryptanalysis.

Qiqing Xia, Qianru Zhu, Huiqin Xie +1 more

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.