Faster Quantum Algorithms for MQ2 and Applications

Quentin Edme; Pierre-Alain Fouque; André Schrottenloher

doi:10.62056/anjbksuc2

Faster Quantum Algorithms for MQ2 and Applications

Authors

Quentin Edme, Pierre-Alain Fouque, André Schrottenloher

Quentin Edme

Independent researcher, France

Pierre-Alain Fouque

Univ Rennes, Inria, CNRS, IRISA, Rennes, France
pierre-alain dot fouque at irisa dot fr

André Schrottenloher

Univ Rennes, Inria, CNRS, IRISA, Rennes, France
andre dot schrottenloher at inria dot fr

Keywords: Quantum cryptanalysis Boolean equation systems Multivariate quadratic systems Quantum search LowMC RAIN

Abstract

We study quantum algorithms for multivariate quadratic Boolean equation systems by focusing on their precise gate count. While better asymptotic algorithms are known, currently gate counts were only computed for exhaustive search (Schwabe and Westerbaan, SPACE 2016) and a variant of Grover's search using preprocessing (Pring, WAIFI 2018). This limits the applicability of Boolean equation solving to cryptanalysis, which considers relatively small numbers of variables (from 40 to 200) and is concerned with the exact complexity of the solver.

In this paper, we introduce two new quantum algorithms. The first algorithm is an optimized quantum exhaustive search which amortizes the cost of polynomial evaluation at each quantum search iterate. The second algorithm adapts a method of Bouillaguet et al. (SOSA 2022) which proceeds by linearization of the system. In both cases, we implement the quantum circuits, study their complexity, and obtain significant improvements over previous results.

Next, we apply these new algorithms to the cryptanalysis of the block ciphers LowMC and RAIN in the single-data setting. By adapting attacks from Liu et al. (ToSC 2022) and Liu et al. (ToSC 2023) we obtain the first quantum cryptanalysis results on these ciphers.

References

[AFI⁺04]

Gwénolé Ars, Jean-Charles Faugère, Hideki Imai, Mitsuru Kawazoe, and Makoto Sugita. Comparison Between XL and Gröbner Basis Algorithms. In ASIACRYPT, volume 3329 of Lecture Notes in Computer Science, pages 338–353. 2004. Springer. DOI: 10.1007/978-3-540-30539-2_24

Google Scholar ePrint

[ARS⁺15]

Martin R. Albrecht, Christian Rechberger, Thomas Schneider, Tyge Tiessen, and Michael Zohner. Ciphers for MPC and FHE. In EUROCRYPT (1), volume 9056 of Lecture Notes in Computer Science, pages 430–454. 2015. Springer. DOI: 10.1007/978-3-662-46800-5_17

Google Scholar ePrint

[BBVY21]

Subhadeep Banik, Khashayar Barooti, Serge Vaudenay, and Hailun Yan. New Attacks on LowMC Instances with a Single Plaintext/Ciphertext Pair. In ASIACRYPT (1), volume 13090 of Lecture Notes in Computer Science, pages 303–331. 2021. Springer. DOI: 10.1007/978-3-030-92062-3_11

Google Scholar ePrint

[BCC⁺10]

Charles Bouillaguet, Hsieh-Chung Chen, Chen-Mou Cheng, Tung Chou, Ruben Niederhagen, Adi Shamir, and Bo-Yin Yang. Fast Exhaustive Search for Polynomial Systems in $\mathbb{F}_2$. In CHES, volume 6225 of Lecture Notes in Computer Science, pages 203–218. 2010. Springer. DOI: 10.1007/978-3-642-15031-9_14

Google Scholar ePrint

[BCV24]

Subhadeep Banik, Andrea Caforio, and Serge Vaudenay. New Attacks on LowMC Using Partial Sets in the Single-Data Setting. IACR Commun. Cryptol., 1(1):22, 2024. DOI: 10.62056/AYZOJBKRZ

Google Scholar ePrint

[BDT22]

Charles Bouillaguet, Claire Delaplace, and Monika Trimoska. A Simple Deterministic Algorithm for Systems of Quadratic Polynomials over $\mathbb{F}_2$. In SOSA, pages 285–296. 2022. SIAM. DOI: 10.1137/1.9781611977066.22

Google Scholar ePrint

[BFR24]

Ryad Benadjila, Thibauld Feneuil, and Matthieu Rivain. MQ on my Mind: Post-Quantum Signatures from the Non-Structured Multivariate Quadratic Problem. In EuroS&P, pages 468–485. 2024. IEEE. DOI: 10.1109/EUROSP60621.2024.00032

Google Scholar ePrint

[BFSS13]

Magali Bardet, Jean-Charles Faugère, Bruno Salvy, and Pierre-Jean Spaenlehauer. On the complexity of solving quadratic Boolean systems. J. Complex., 29(1):53–75, 2013. DOI: 10.1016/J.JCO.2012.07.001

Google Scholar ePrint

[BHMT02]

Gilles Brassard, Peter Hoyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. Contemporary Mathematics, 305:53–74, 2002. DOI: 10.1090/conm/305/05215

Google Scholar ePrint

[BJ22]

Xavier Bonnetain and Samuel Jaques. Quantum Period Finding against Symmetric Primitives in Practice. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2022(1):1–27, 2022. DOI: 10.46586/TCHES.V2022.I1.1-27

Google Scholar ePrint

[BY18]

Daniel J. Bernstein and Bo-Yin Yang. Asymptotically Faster Quantum Algorithms to Solve Multivariate Quadratic Equations. In PQCrypto, volume 10786 of Lecture Notes in Computer Science, pages 487–506. 2018. Springer. DOI: 10.1007/978-3-319-79063-3_23

Google Scholar ePrint

[CDG⁺20]

Melissa Chase, David Derler, Steven Goldfeder, Jonathan Katz, Vladimir Kolesnikov, Claudio Orlandi, Sebastian Ramacher, Christian Rechberger, Daniel Slamanig, Xiao Wang, and Greg Zaverucha. The Picnic signature algorithm. Submission to NIST Post-Quantum Cryptography project, version 3.0, 2020.

Google Scholar ePrint

[CHR⁺18]

Ming-Shing Chen, Andreas Hülsing, Joost Rijneveld, Simona Samardjiska, and Peter Schwabe. SOFIA: MQ-Based Signatures in the QROM. In Public Key Cryptography (2), volume 10770 of Lecture Notes in Computer Science, pages 3–33. 2018. Springer. DOI: 10.1007/978-3-319-76581-5_1

Google Scholar ePrint

[CKPS00]

Nicolas T. Courtois, Alexander Klimov, Jacques Patarin, and Adi Shamir. Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. In EUROCRYPT, volume 1807 of Lecture Notes in Computer Science, pages 392–407. 2000. Springer. DOI: 10.1007/3-540-45539-6_27

Google Scholar ePrint

[Din21a]

Itai Dinur. Cryptanalytic Applications of the Polynomial Method for Solving Multivariate Equation Systems over GF(2). In EUROCRYPT (1), volume 12696 of Lecture Notes in Computer Science, pages 374–403. 2021. Springer. DOI: 10.1007/978-3-030-77870-5_14

Google Scholar ePrint

[Din21b]

Itai Dinur. Improved Algorithms for Solving Polynomial Systems over GF(2) by Multiple Parity-Counting. In SODA, pages 2550–2564. 2021. SIAM. DOI: 10.1137/1.9781611976465.151

Google Scholar ePrint

[DKR⁺22]

Christoph Dobraunig, Daniel Kales, Christian Rechberger, Markus Schofnegger, and Greg Zaverucha. Shorter Signatures Based on Tailor-Made Minimalist Symmetric-Key Crypto. In CCS, pages 843–857. 2022. ACM. DOI: 10.1145/3548606.3559353

Google Scholar ePrint

[Fau02]

Jean-Charles Faugère. A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In Proceedings of the 2002 international symposium on Symbolic and algebraic computation, pages 75–83. 2002. DOI: 10.1145/780506.780516

Google Scholar ePrint

[FHK⁺17]

Jean-Charles Faugère, Kelsey Horan, Delaram Kahrobaei, Marc Kaplan, Elham Kashefi, and Ludovic Perret. Fast Quantum Algorithm for Solving Multivariate Quadratic Equations. IACR Cryptol. ePrint Arch., 2017.

Google Scholar ePrint

[Gid15]

Craig Gidney. Constructing Large Controlled Nots. https://algassert.com/circuits/2015/06/05/Constructing-Large-Controlled-Nots.html. 2015.

Google Scholar ePrint

[Gro96]

Lov K. Grover. A Fast Quantum Mechanical Algorithm for Database Search. In STOC, pages 212–219. 1996. ACM. DOI: 10.1145/237814.237866

Google Scholar ePrint

[JBK⁺22]

Kyungbae Jang, Anubhab Baksi, Hyunji Kim, Hwajeong Seo, and Anupam Chattopadhyay. Improved Quantum Analysis of SPECK and LowMC. In INDOCRYPT, volume 13774 of Lecture Notes in Computer Science, pages 517–540. 2022. Springer. DOI: 10.1007/978-3-031-22912-1_23

Google Scholar ePrint

[JNRV20]

Samuel Jaques, Michael Naehrig, Martin Roetteler, and Fernando Virdia. Implementing Grover Oracles for Quantum Key Search on AES and LowMC. In EUROCRYPT (2), volume 12106 of Lecture Notes in Computer Science, pages 280–310. 2020. Springer. DOI: 10.1007/978-3-030-45724-2_10

Google Scholar ePrint

[JV17]

Antoine Joux and Vanessa Vitse. A Crossbred Algorithm for Solving Boolean Polynomial Systems. In NuTMiC, volume 10737 of Lecture Notes in Computer Science, pages 3–21. 2017. Springer. DOI: 10.1007/978-3-319-76620-1_1

Google Scholar ePrint

[KHS⁺23]

Seongkwang Kim, Jincheol Ha, Mincheol Son, ByeongHak Lee, Dukjae Moon, Joohee Lee, Sangyub Lee, Jihoon Kwon, Jihoon Cho, Hyojin Yoon, and Jooyoung Lee. AIM: Symmetric Primitive for Shorter Signatures with Stronger Security. In CCS, pages 401–415. 2023. ACM. DOI: 10.1145/3576915.3616579

Google Scholar ePrint

[LM{\O }M23]

Fukang Liu, Mohammad Mahzoun, Morten Øygarden, and Willi Meier. Algebraic Attacks on RAIN and AIM Using Equivalent Representations. IACR Trans. Symmetric Cryptol., 2023(4):166–186, 2023. DOI: 10.46586/TOSC.V2023.I4.166-186

Google Scholar ePrint

[LMSI22]

Fukang Liu, Willi Meier, Santanu Sarkar, and Takanori Isobe. New Low-Memory Algebraic Attacks on LowMC in the Picnic Setting. IACR Trans. Symmetric Cryptol., 2022(3):102–122, 2022. DOI: 10.46586/TOSC.V2022.I3.102-122

Google Scholar ePrint

[LPT⁺17]

Daniel Lokshtanov, Ramamohan Paturi, Suguru Tamaki, R. Ryan Williams, and Huacheng Yu. Beating Brute Force for Systems of Polynomial Equations over Finite Fields. In SODA, pages 2190–2202. 2017. SIAM. DOI: 10.1137/1.9781611974782.143

Google Scholar ePrint

[Mas98]

VI Masol. Limit distribution of the number of solutions of a system of random Boolean equations with a linear part. Ukrainian Mathematical Journal, 50(9):1389–1404, 1998. DOI: 10.1007/BF02525245

Google Scholar ePrint

[NC02]

Isaac Nielsen Michael A and Chuang. Quantum computation and quantum information. 2002.

Google Scholar ePrint

[NIS22]

NIST. Call for Additional Digital Signature Schemes for the Post-Quantum Cryptography Standardization Process. https://csrc.nist.gov/csrc/media/Projects/pqc-dig-sig/documents/call-for-proposals-dig-sig-sept-2022.pdf. 2022.

Google Scholar ePrint

[Pri18]

Benjamin Pring. Exploiting Preprocessing for Quantum Search to Break Parameters for MQ Cryptosystems. In WAIFI, volume 11321 of Lecture Notes in Computer Science, pages 291–307. 2018. Springer. DOI: 10.1007/978-3-030-05153-2_17

Google Scholar ePrint

[{Qis}23]

Qiskit contributors. Qiskit: An Open-source Framework for Quantum Computing. 2023.

Google Scholar ePrint

[SS24]

André Schrottenloher and Marc Stevens. Quantum Procedures for Nested Search Problems: with Applications in Cryptanalysis. IACR Commun. Cryptol., 1(3):9, 2024. DOI: 10.62056/AEE0FHBMO

Google Scholar ePrint

[SW16]

Peter Schwabe and Bas Westerbaan. Solving Binary MQ with Grover's Algorithm. In SPACE, volume 10076 of Lecture Notes in Computer Science, pages 303–322. 2016. Springer. DOI: 10.1007/978-3-319-49445-6_17

Google Scholar ePrint

[WWF⁺21]

Congming Wei, Chenhao Wu, Ximing Fu, Xiaoyang Dong, Kai He, Jue Hong, and Xiaoyun Wang. Preimage Attacks on 4-Round Keccak by Solving Multivariate Quadratic Systems. In ICISC, volume 13218 of Lecture Notes in Computer Science, pages 195–216. 2021. Springer. DOI: 10.1007/978-3-031-08896-4_10

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/anjbksuc2

History

Submitted: 2025-01-08
Accepted: 2025-03-11
Published: 2025-04-08

How to cite

Quentin Edme, Pierre-Alain Fouque, and André Schrottenloher, Faster Quantum Algorithms for MQ2 and Applications. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/anjbksuc2.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{10.62056/anjbksuc2,
         author={Quentin Edme and Pierre-Alain Fouque and André Schrottenloher},
         title={Faster Quantum Algorithms for {MQ}2 and Applications},
         volume={2},
         number={1},
         year={2025},
         date={2025-04-08},
         issn={3006-5496},
         doi={10.62056/anjbksuc2},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}

TY  - JOUR
AU  - Quentin Edme
AU  - Pierre-Alain Fouque
AU  - André Schrottenloher
PY  - 2025
TI  - Faster Quantum Algorithms for MQ2 and Applications
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 2
IS  - 1
DO  - 10.62056/anjbksuc2
UR  - https://doi.org/10.62056/anjbksuc2
AB  - <p>We study quantum algorithms for multivariate quadratic Boolean equation systems by focusing on their precise gate count. While better asymptotic algorithms are known, currently gate counts were only computed for exhaustive search (Schwabe and Westerbaan, SPACE 2016) and a variant of Grover's search using preprocessing (Pring, WAIFI 2018). This limits the applicability of Boolean equation solving to cryptanalysis, which considers relatively small numbers of variables (from 40 to 200) and is concerned with the exact complexity of the solver.</p><p>In this paper, we introduce two new quantum algorithms. The first algorithm is an optimized quantum exhaustive search which amortizes the cost of polynomial evaluation at each quantum search iterate. The second algorithm adapts a method of Bouillaguet et al. (SOSA 2022) which proceeds by linearization of the system. In both cases, we implement the quantum circuits, study their complexity, and obtain significant improvements over previous results.</p><p>Next, we apply these new algorithms to the cryptanalysis of the block ciphers LowMC and RAIN in the single-data setting. By adapting attacks from Liu et al. (ToSC 2022) and Liu et al. (ToSC 2023) we obtain the first quantum cryptanalysis results on these ciphers. </p>
ER  -

Quentin Edme, Pierre-Alain Fouque, and André Schrottenloher, Faster Quantum Algorithms for MQ2 and Applications. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/anjbksuc2.