{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,30]],"date-time":"2026-07-30T11:56:07Z","timestamp":1785412567346,"version":"3.56.0"},"reference-count":36,"publisher":"International Association for Cryptologic Research","issue":"1","license":[{"start":{"date-parts":[[2025,1,8]],"date-time":"2025-01-08T00:00:00Z","timestamp":1736294400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-22-PETQ-0008 PQ-TLS"],"award-info":[{"award-number":["ANR-22-PETQ-0008 PQ-TLS"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2025,3,11]]},"abstract":"<jats: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.<\/jats:p>\n                  <jats: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.<\/jats:p>\n                  <jats: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.<\/jats:p>","DOI":"10.62056\/anjbksuc2","type":"journal-article","created":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T17:23:17Z","timestamp":1744132997000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":0,"title":["Faster Quantum Algorithms for MQ2 and Applications"],"prefix":"10.62056","volume":"2","author":[{"given":"Quentin","family":"Edme","sequence":"first","affiliation":[{"name":"Independent researcher","place":["France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4997-2276","authenticated-orcid":false,"given":"Pierre-Alain","family":"Fouque","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/04040yw90","id-type":"ROR","asserted-by":"publisher"}],"name":"Univ Rennes, Inria, CNRS, IRISA","place":["Rennes, 35000, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1329-8630","authenticated-orcid":false,"given":"Andr\u00e9","family":"Schrottenloher","sequence":"additional","affiliation":[{"id":[{"id":"https:\/\/ror.org\/04040yw90","id-type":"ROR","asserted-by":"publisher"}],"name":"Univ Rennes, Inria, CNRS, IRISA","place":["Rennes, 35000, France"]}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"48349","published-online":{"date-parts":[[2025,4,8]]},"reference":[{"key":"ref1:nist","volume-title":"Call for Additional Digital Signature Schemes for the\n  Post-Quantum Cryptography Standardization Process","author":"NIST","year":"2022"},{"key":"ref2:DBLP:conf\/eurocrypt\/AlbrechtR0TZ15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1007\/978-3-662-46800-5_17","article-title":"Ciphers for MPC and FHE","volume":"9056","author":"Martin R. Albrecht","year":"2015"},{"key":"ref3:DBLP:conf\/icisc\/WeiWFDHHW21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-031-08896-4_10","article-title":"Preimage Attacks on 4-Round Keccak by Solving Multivariate\n  Quadratic Systems","volume":"13218","author":"Congming Wei","year":"2021"},{"key":"ref4:DBLP:conf\/eurocrypt\/Dinur21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-030-77870-5_14","article-title":"Cryptanalytic Applications of the Polynomial Method for\n  Solving Multivariate Equation Systems over GF(2)","volume":"12696","author":"Itai Dinur","year":"2021"},{"key":"ref5:DBLP:conf\/ccs\/KimHSLMLLKCY023","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1145\/3576915.3616579","article-title":"AIM: Symmetric Primitive for Shorter Signatures with\n  Stronger Security","author":"Seongkwang Kim","year":"2023"},{"key":"ref6:DBLP:conf\/ccs\/DobraunigKRSZ22","doi-asserted-by":"publisher","first-page":"843","DOI":"10.1145\/3548606.3559353","article-title":"Shorter Signatures Based on Tailor-Made Minimalist\n  Symmetric-Key Crypto","author":"Christoph Dobraunig","year":"2022"},{"key":"ref7:DBLP:journals\/tosc\/LiuMOM23","doi-asserted-by":"publisher","first-page":"166","DOI":"10.46586\/TOSC.V2023.I4.166-186","article-title":"Algebraic Attacks on RAIN and AIM Using Equivalent\n  Representations","volume":"2023","author":"Fukang Liu","year":"2023","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref8:faugere2002new","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1145\/780506.780516","article-title":"A new efficient algorithm for computing Gr\u00f6bner bases\n  without reduction to zero (F5)","author":"Jean-Charles Faug\u00e8re","year":"2002"},{"key":"ref9:DBLP:conf\/soda\/LokshtanovPTWY17","doi-asserted-by":"publisher","first-page":"2190","DOI":"10.1137\/1.9781611974782.143","article-title":"Beating Brute Force for Systems of Polynomial Equations over\n  Finite Fields","author":"Daniel Lokshtanov","year":"2017"},{"key":"ref10:DBLP:conf\/soda\/Dinur21","doi-asserted-by":"publisher","first-page":"2550","DOI":"10.1137\/1.9781611976465.151","article-title":"Improved Algorithms for Solving Polynomial Systems over\n  GF(2) by Multiple Parity-Counting","author":"Itai Dinur","year":"2021"},{"key":"ref11:DBLP:conf\/ches\/BouillaguetCCCNSY10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/978-3-642-15031-9_14","article-title":"Fast Exhaustive Search for Polynomial Systems in\n  $\\mathbb{F}_2$","volume":"6225","author":"Charles Bouillaguet","year":"2010"},{"key":"ref12:DBLP:conf\/nutmic\/JouxV17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-76620-1_1","article-title":"A Crossbred Algorithm for Solving Boolean Polynomial\n  Systems","volume":"10737","author":"Antoine Joux","year":"2017"},{"key":"ref13:DBLP:conf\/sosa\/BouillaguetDT22","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/1.9781611977066.22","article-title":"A Simple Deterministic Algorithm for Systems of Quadratic\n  Polynomials over $\\mathbb{F}_2$","author":"Charles Bouillaguet","year":"2022"},{"key":"ref14:DBLP:conf\/space\/SchwabeW16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-319-49445-6_17","article-title":"Solving Binary MQ with Grover's Algorithm","volume":"10076","author":"Peter Schwabe","year":"2016"},{"key":"ref15:DBLP:conf\/waifi\/Pring18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/978-3-030-05153-2_17","article-title":"Exploiting Preprocessing for Quantum Search to Break\n  Parameters for MQ Cryptosystems","volume":"11321","author":"Benjamin Pring","year":"2018"},{"key":"ref16:DBLP:journals\/iacr\/FaugereHKKKP17","first-page":"1236","article-title":"Fast Quantum Algorithm for Solving Multivariate Quadratic\n  Equations","author":"Jean-Charles Faug\u00e8re","year":"2017","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref17:DBLP:conf\/pqcrypto\/BernsteinY18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/978-3-319-79063-3_23","article-title":"Asymptotically Faster Quantum Algorithms to Solve\n  Multivariate Quadratic Equations","volume":"10786","author":"Daniel J. Bernstein","year":"2018"},{"key":"ref18:DBLP:journals\/jc\/BardetFSS13","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/J.JCO.2012.07.001","article-title":"On the complexity of solving quadratic Boolean systems","volume":"29","author":"Magali Bardet","year":"2013","journal-title":"J. Complex."},{"key":"ref19:DBLP:conf\/eurocrypt\/CourtoisKPS00","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/3-540-45539-6_27","article-title":"Efficient Algorithms for Solving Overdefined Systems of\n  Multivariate Polynomial Equations","volume":"1807","author":"Nicolas T. Courtois","year":"2000"},{"key":"ref20:DBLP:conf\/stoc\/Grover96","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1145\/237814.237866","article-title":"A Fast Quantum Mechanical Algorithm for Database Search","author":"Lov K. Grover","year":"1996"},{"key":"ref21:DBLP:conf\/eurocrypt\/JaquesNRV20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-030-45724-2_10","article-title":"Implementing Grover Oracles for Quantum Key Search on AES\n  and LowMC","volume":"12106","author":"Samuel Jaques","year":"2020"},{"key":"ref22:DBLP:journals\/iacr\/Schrottenloher022","doi-asserted-by":"publisher","first-page":"9","DOI":"10.62056\/AEE0FHBMO","article-title":"Quantum Procedures for Nested Search Problems: with\n  Applications in Cryptanalysis","volume":"1","author":"Andr\u00e9 Schrottenloher","year":"2024","journal-title":"IACR Commun. Cryptol."},{"key":"ref23:Qiskit","doi-asserted-by":"publisher","DOI":"10.5281\/zenodo.2573505","volume-title":"Qiskit: An Open-source Framework for Quantum Computing","author":"Qiskit contributors","year":"2023"},{"key":"ref24:benadjila2024mq","doi-asserted-by":"publisher","first-page":"468","DOI":"10.1109\/EUROSP60621.2024.00032","article-title":"MQ on my Mind: Post-Quantum Signatures from the\n  Non-Structured Multivariate Quadratic Problem","author":"Ryad Benadjila","year":"2024"},{"key":"ref25:chase2020picnic","article-title":"The Picnic signature algorithm","author":"Melissa Chase","year":"2020","journal-title":"Submission to NIST Post-Quantum Cryptography project,\n  version 3.0"},{"key":"ref26:DBLP:journals\/tosc\/LiuMSI22","doi-asserted-by":"publisher","first-page":"102","DOI":"10.46586\/TOSC.V2022.I3.102-122","article-title":"New Low-Memory Algebraic Attacks on LowMC in the Picnic\n  Setting","volume":"2022","author":"Fukang Liu","year":"2022","journal-title":"IACR Trans. Symmetric Cryptol."},{"key":"ref27:nielsen2002quantum","volume-title":"Quantum computation and quantum information","author":"Isaac Nielsen Michael A and Chuang","year":"2002"},{"key":"ref28:masol1998limit","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1007\/BF02525245","article-title":"Limit distribution of the number of solutions of a system of\n  random Boolean equations with a linear part","volume":"50","author":"VI Masol","year":"1998","journal-title":"Ukrainian Mathematical Journal"},{"key":"ref29:ars2004comparison","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1007\/978-3-540-30539-2_24","article-title":"Comparison Between XL and Gr\u00f6bner Basis Algorithms","volume":"3329","author":"Gw\u00e9nol\u00e9 Ars","year":"2004"},{"key":"ref30:DBLP:conf\/pkc\/ChenHRSS18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-76581-5_1","article-title":"SOFIA: MQ-Based Signatures in the QROM","volume":"10770","author":"Ming-Shing Chen","year":"2018"},{"key":"ref31:brassard2002quantum","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1090\/conm\/305\/05215","article-title":"Quantum amplitude amplification and estimation","volume":"305","author":"Gilles Brassard","year":"2002","journal-title":"Contemporary Mathematics"},{"key":"ref32:gidneyblog","volume-title":"Constructing Large Controlled Nots","author":"Craig Gidney","year":"2015"},{"key":"ref33:DBLP:journals\/tches\/BonnetainJ22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.46586\/TCHES.V2022.I1.1-27","article-title":"Quantum Period Finding against Symmetric Primitives in\n  Practice","volume":"2022","author":"Xavier Bonnetain","year":"2022","journal-title":"IACR Trans. Cryptogr. Hardw. Embed. Syst."},{"key":"ref34:DBLP:conf\/asiacrypt\/BanikBVY21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-030-92062-3_11","article-title":"New Attacks on LowMC Instances with a Single\n  Plaintext\/Ciphertext Pair","volume":"13090","author":"Subhadeep Banik","year":"2021"},{"key":"ref35:DBLP:journals\/cic\/BanikCV24","doi-asserted-by":"publisher","first-page":"22","DOI":"10.62056\/AYZOJBKRZ","article-title":"New Attacks on LowMC Using Partial Sets in the Single-Data\n  Setting","volume":"1","author":"Subhadeep Banik","year":"2024","journal-title":"IACR Commun. Cryptol."},{"key":"ref36:DBLP:conf\/indocrypt\/JangBKSC22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/978-3-031-22912-1_23","article-title":"Improved Quantum Analysis of SPECK and LowMC","volume":"13774","author":"Kyungbae Jang","year":"2022"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T17:24:13Z","timestamp":1744133053000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/2\/1\/17"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,8]]},"references-count":36,"journal-issue":{"issue":"1","published-online":{"date-parts":[[2025,4,8]]}},"URL":"https:\/\/doi.org\/10.62056\/anjbksuc2","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,8]]},"assertion":[{"value":"2025-01-08","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-03-11","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc2-1-21"}}