Quantum Information & Computation
Volume 25, Issue 5
RESEARCH ARTICLE Open access

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

Qiqing Xia, Qianru Zhu, Huiqin Xie, Li Yang

Author affiliations
  • Qiqing Xia1
  • Qianru Zhu1
  • Huiqin Xie2
  • Li Yang1
  1. Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China; State Key Laboratory of Cyberspace Security Defense, Beijing, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing, China
  2. Beijing Electronic Science and Technology Institute, Beijing, China

pp. 421-437 · 10.2478/qic-2025-0024

Read PDF View on Reference Global
On this page

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.
Open accessCC BY-NC-ND 4.0

Keywords

  • Grover-meets-Simon
  • Alg-PolyQ2
  • deferred measurement
  • quantum rank-solving
  • formal analysis
  • success probability

Suggested citation

Qiqing Xia, Qianru Zhu, Huiqin Xie, Li Yang (2025). Tight Analysis of Grover-Meets-Simon and Alg-PolyQ2 Attacks via Formalizing Quantum Rank-Solving under Deferred Measurement. Quantum Information & Computation, 25(5), 421-437. https://doi.org/10.2478/qic-2025-0024

Download BibTeX

References (40)

  1. Shao, C.; Li, Y.; Li, H. Quantum algorithm design: techniques and applications. J. Syst. Sci. Complex. 2019, 32, 375–452.DOI: 10.1007/s11424-019-9008-0Google Scholar
  2. Shor, P.W. Algorithms for quantum computation: discrete logarithms and factoring. Proc. 35th Annu. Symp. Found. Comput. Sci. 1994, 124–134.DOI: 10.1109/SFCS.1994.365700Google Scholar
  3. Shor, P.W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 1999, 41, 303–332.DOI: 10.1137/S0036144598347011Google Scholar
  4. Alagic, G.; Alperin-Sheriff, J.; Apon, D.; Cooper, D.; Dang, Q.; Liu, Y.-K.; Miller, C.; Moody, D.; Peralta, R.; et al. Status report on the first round of the NIST post-quantum cryptography standardization process. 2019.DOI: 10.6028/NIST.IR.8240Google Scholar
  5. Alagic, G.; Alperin-Sheriff, J.; Apon, D.; Cooper, D.; Dang, Q.; Kelsey, J.; Liu, Y.-K.; Miller, C.; Moody, D.; Peralta, R.; et al. Status report on the second round of the NIST post-quantum cryptography standardization process. US Dept. Commerce, NIST
    2020, 2, 69.    DOI: 10.6028/NIST.IR.8240Google Scholar
  6. Alagic, G.; Apon, D.; Cooper, D.; Dang, Q.; Dang, T.; Kelsey, J.; Lichtinger, J.; Liu, Y.-K.; Miller, C.; et al. Status report on the third round of the NIST post-quantum cryptography standardization process. 2022.DOI: 10.6028/NIST.IR.8413-upd1Google Scholar
  7. Alagic, G.; Bros, M.; Ciadoux, P.; Cooper, D.; Dang, Q.; Dang, T.; Kelsey, J.; Lichtinger, J.; Liu, Y.-K.; Miller, C.; et al. Status report on the fourth round of the NIST post-quantum cryptography standardization process. NIST, Gaithersburg, MD, USA
    2025.    DOI: 10.6028/NIST.IR.8545Google Scholar
  8. Grover, L.K. A fast quantum mechanical algorithm for database search. Proc. 28th Annu. ACM Symp. Theory Comput. 1996, 212–219.DOI: 10.1145/237814.237866Google Scholar
  9. Grover, L.K. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 1997, 79, 325.DOI: 10.1103/PhysRevLett.79.325Google Scholar
  10. Bernstein, D.J.; et al. Introduction to post-quantum cryptography. Post-Quantum Cryptogr. 2009, 1, 1–10.DOI: 10.1007/978-3-540-88702-7Google Scholar
  11. Diffie, W.; Hellman, M.E. New directions in cryptography. Democratizing Cryptography
    2022, 365–390.    DOI: 10.1145/3549993.3550007Google Scholar
  12. Horowitz, M.; Grumbling, E. Quantum computing: progress and prospects. 2019.DOI: 10.17226/25196Google Scholar
  13. Brassard, G.; Hoyer, P.; Mosca, M.; Tapp, A. Quantum amplitude amplification and estimation. Contemp. Math. 2002, 305, 53–74.DOI: 10.1090/conm/305/05215Google Scholar
  14. Brassard, G.; Høyer, P.; Tapp, A. Quantum cryptanalysis of hash and claw-free functions. Latin Am. Symp. Theor. Inform. 1998, 163–169.DOI: 10.1007/BFb0054319Google Scholar
  15. Ambainis, A. Quantum walk algorithm for element distinctness. SIAM J. Comput. 2007, 37, 210–239.DOI: 10.1137/S0097539705447311Google Scholar
  16. Aaronson, S.; Shi, Y. Quantum lower bounds for the collision and the element distinctness problems. J. ACM
    2004, 51, 595–605.    DOI: 10.1145/1008731.1008735Google Scholar
  17. Zhandry, M. A note on the quantum collision and set equality problems. arXivpreprint arXiv:1312.1027 2013.Google Scholar
  18. Hosoyamada, A.; Sasaki, Y.; Xagawa, K. Quantum multicollision-finding algorithm. Int. Conf. Theory Appl. Cryptology Inf. Secur. 2017, 179–210.DOI: 10.1007/978-3-319-70697-9_7Google Scholar
  19. Simon, D.R. On the power of quantum computation. SIAM J. Comput. 1997, 26, 1474–1483.DOI: 10.1137/S0097539796298637Google Scholar
  20. Kuwakado, H.; Morii, M. Quantum distinguisher between the 3-round Feistel cipher and the random permutation. Proc. IEEE Int. Symp. Inf. Theory, 2010, 2682–2685.DOI: 10.1109/ISIT.2010.5513654Google Scholar
  21. Kuwakado, H.; Morii, M. Security on the quantum-type Even-Mansour cipher. Proc. Int. Symp. Inf. Theory and Its Applications, 2012, 312–316.Google Scholar
  22. Santoli, T.; Schaffner, C. Using Simon’s algorithm to attack symmetric-key cryptographic primitives. Quantum Inf. Comput., 2017, 17, 65–78.DOI: 10.26421/QIC17.1-2-4Google Scholar
  23. Kaplan, M.; Leurent, G.; Leverrier, A.; Naya-Plasencia, M. Breaking symmetric cryptosystems using quantum period finding. Advances in Cryptology—CRYPTO, 2016, 207–237.DOI: 10.1007/978-3-662-53008-5_8Google Scholar
  24. Ito, G.; Hosoyamada, A.; Matsumoto, R.; Sasaki, Y.; Iwata, T. Quantum chosen-ciphertext attacks against Feistel ciphers. Cryptographers’ Track at the RSA Conf., 2019, 391–411.DOI: 10.1007/978-3-030-12612-4_20Google Scholar
  25. Xie, H.; Yang, L. Quantum miss-in-the-middle attack. arXivpreprint arXiv:1812.08499, 2018.Google Scholar
  26. Roetteler, M.; Steinwandt, R. A note on quantum related-key attacks. Inf. Process. Lett., 2015, 115, 40–44.DOI: 10.1016/j.ipl.2014.08.009Google Scholar
  27. Bonnetain, X.; Naya-Plasencia, M.; Schrottenloher, A. On quantum slide attacks. Sel. Areas Cryptogr., 2020, 492–519.DOI: 10.1007/978-3-030-38471-5_20Google Scholar
  28. Bonnetain, X.; Naya-Plasencia, M. Hidden shift quantum cryptanalysis and implications. Advances in Cryptology—ASIACRYPT, 2018, 560–592.DOI: 10.1007/978-3-030-03326-2_19Google Scholar
  29. Zhou, B.-M.; Yuan, Z. Quantum key-recovery attack on Feistel constructions: Bernstein–Vazirani meet Grover algorithm. Quantum Inf. Process., 2021, 20, 1–14.DOI: 10.1007/s11128-021-03256-0Google Scholar
  30. Leander, G.; May, A. Grovermeets Simon—Quantumly attacking the FX-construction. Advances in Cryptology— ASIACRYPT, 2017, 161–178.DOI: 10.1007/978-3-319-70697-9_6Google Scholar
  31. Dong, X.; Li, Z.; Wang, X. Quantum cryptanalysis on some generalized Feistel schemes. Sci. China Inf. Sci., 2019, 62, 1–12.DOI: 10.1007/s11432-017-9436-7Google Scholar
  32. Dong, X.; Wang, X. Quantum key-recovery attack on Feistel structures. Sci. China Inf. Sci., 2018, 61, 1–7.DOI: 10.1007/s11432-017-9468-yGoogle Scholar
  33. Shinagawa, K.; Iwata, T. Quantum attacks on sum of Even-Mansour pseudorandom functions. Inf. Process. Lett., 2022, 173, 106172.DOI: 10.1016/j.ipl.2021.106172Google Scholar
  34. Bonnetain, X.; Hosoyamada, A.; Naya-Plasencia, M.; Sasaki, Y.; Schrottenloher, A. Quantum attacks without superposition queries: the offline Simon’s algorithm. Advances in Cryptology—ASIACRYPT, 2019, 552–583.DOI: 10.1007/978-3-030-34578-5_20Google Scholar
  35. Nielsen, M.A.; Chuang, I. Quantum computation and quantum information. Am. Assoc. Phys. Teachers, 2002.DOI: 10.1119/1.1463744Google Scholar
  36. Diep, D.N.; Giang, D.H. Quantum Gauss-Jordan elimination. arXivpreprint quant-ph/0511062, 2005.Google Scholar
  37. Bonnetain, X.; Jaques, S. Quantum period finding against symmetric primitives in practice. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2022, 1–27.DOI: 10.46586/tches.v2022.i1.1-27Google Scholar
  38. Xia, Q.; Zhu, Q.; Xie, H.; Yang, L. Algorithm for solving quantum linear systems of equations with coherent superposition and extended applications. Comput. J., 2025, 68, 520–538.DOI: 10.1093/comjnl/bxae129Google Scholar
  39. Biron, D.; Biham, O.; Biham, E.; Grassl, M.; Lidar, D.A. Generalized Grover search algorithm for arbitrary initial amplitude distribution. Lect. Notes Comput. Sci., 1999, 140–147.DOI: 10.1007/3-540-49208-9_10Google Scholar
  40. Biham, E.; Biham, O.; Biron, D.; Grassl, M.; Lidar, D.A. Grover’s quantum search algorithm for an arbitrary initial amplitude distribution. Phys. Rev. A, 1999, 60, 2742.DOI: 10.1103/PhysRevA.60.2742Google Scholar