Tight Analysis of Grover-Meets-Simon and Alg-PolyQ2 Attacks via Formalizing Quantum Rank-Solving under Deferred Measurement
By: Qiqing Xia, Qianru Zhu, Huiqin Xie and Li Yang
References
- Shao, C.; Li, Y.; Li, H. Quantum algorithm design: techniques and applications. J. Syst. Sci. Complex. 2019, 32, 375–452.
- Shor, P.W. Algorithms for quantum computation: discrete logarithms and factoring. Proc. 35th Annu. Symp. Found. Comput. Sci. 1994, 124–134.
- Shor, P.W. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev. 1999, 41, 303–332.
- 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.
- 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.
- 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.
- 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.
- Grover, L.K. A fast quantum mechanical algorithm for database search. Proc. 28th Annu. ACM Symp. Theory Comput. 1996, 212–219.
- Grover, L.K. Quantum mechanics helps in searching for a needle in a haystack. Phys. Rev. Lett. 1997, 79, 325.
- Bernstein, D.J.; et al. Introduction to post-quantum cryptography. Post-Quantum Cryptogr. 2009, 1, 1–10.
- Diffie, W.; Hellman, M.E. New directions in cryptography. Democratizing Cryptography 2022, 365–390.
- Horowitz, M.; Grumbling, E. Quantum computing: progress and prospects. 2019.
- Brassard, G.; Hoyer, P.; Mosca, M.; Tapp, A. Quantum amplitude amplification and estimation. Contemp. Math. 2002, 305, 53–74.
- Brassard, G.; Høyer, P.; Tapp, A. Quantum cryptanalysis of hash and claw-free functions. Latin Am. Symp. Theor. Inform. 1998, 163–169.
- Ambainis, A. Quantum walk algorithm for element distinctness. SIAM J. Comput. 2007, 37, 210–239.
- Aaronson, S.; Shi, Y. Quantum lower bounds for the collision and the element distinctness problems. J. ACM 2004, 51, 595–605.
- Zhandry, M. A note on the quantum collision and set equality problems. arXivpreprint arXiv:1312.1027 2013.
- Hosoyamada, A.; Sasaki, Y.; Xagawa, K. Quantum multicollision-finding algorithm. Int. Conf. Theory Appl. Cryptology Inf. Secur. 2017, 179–210.
- Simon, D.R. On the power of quantum computation. SIAM J. Comput. 1997, 26, 1474–1483.
- 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.
- Kuwakado, H.; Morii, M. Security on the quantum-type Even-Mansour cipher. Proc. Int. Symp. Inf. Theory and Its Applications, 2012, 312–316.
- Santoli, T.; Schaffner, C. Using Simon’s algorithm to attack symmetric-key cryptographic primitives. Quantum Inf. Comput., 2017, 17, 65–78.
- Kaplan, M.; Leurent, G.; Leverrier, A.; Naya-Plasencia, M. Breaking symmetric cryptosystems using quantum period finding. Advances in Cryptology—CRYPTO, 2016, 207–237.
- 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.
- Xie, H.; Yang, L. Quantum miss-in-the-middle attack. arXivpreprint arXiv:1812.08499, 2018.
- Roetteler, M.; Steinwandt, R. A note on quantum related-key attacks. Inf. Process. Lett., 2015, 115, 40–44.
- Bonnetain, X.; Naya-Plasencia, M.; Schrottenloher, A. On quantum slide attacks. Sel. Areas Cryptogr., 2020, 492–519.
- Bonnetain, X.; Naya-Plasencia, M. Hidden shift quantum cryptanalysis and implications. Advances in Cryptology—ASIACRYPT, 2018, 560–592.
- Zhou, B.-M.; Yuan, Z. Quantum key-recovery attack on Feistel constructions: Bernstein–Vazirani meet Grover algorithm. Quantum Inf. Process., 2021, 20, 1–14.
- Leander, G.; May, A. Grovermeets Simon—Quantumly attacking the FX-construction. Advances in Cryptology— ASIACRYPT, 2017, 161–178.
- Dong, X.; Li, Z.; Wang, X. Quantum cryptanalysis on some generalized Feistel schemes. Sci. China Inf. Sci., 2019, 62, 1–12.
- Dong, X.; Wang, X. Quantum key-recovery attack on Feistel structures. Sci. China Inf. Sci., 2018, 61, 1–7.
- Shinagawa, K.; Iwata, T. Quantum attacks on sum of Even-Mansour pseudorandom functions. Inf. Process. Lett., 2022, 173, 106172.
- 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.
- Nielsen, M.A.; Chuang, I. Quantum computation and quantum information. Am. Assoc. Phys. Teachers, 2002.
- Diep, D.N.; Giang, D.H. Quantum Gauss-Jordan elimination. arXivpreprint quant-ph/0511062, 2005.
- Bonnetain, X.; Jaques, S. Quantum period finding against symmetric primitives in practice. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2022, 1–27.
- 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.
- 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.
- 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: https://doi.org/10.2478/qic-2025-0024 | Journal eISSN: 3106-0544 (formerly 1533-7146) | Journal ISSN: 1533-7146
Language: English
Page range: 421 - 437
Submitted on: Jul 24, 2025
Accepted on: Aug 18, 2025
Published on: Dec 31, 2025
Published by: Cerebration Science Publishing Co., Limited
In partnership with: Paradigm Publishing Services
Publication frequency: 1 issue per year
Keywords:
Related subjects:
© 2025 Qiqing Xia, Qianru Zhu, Huiqin Xie, Li Yang, published by Cerebration Science Publishing Co., Limited
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.