{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T15:23:43Z","timestamp":1763997823581,"version":"3.45.0"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T00:00:00Z","timestamp":1756339200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T00:00:00Z","timestamp":1756339200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"CISPA - Helmholtz-Zentrum f\u00fcr Informationssicherheit gGmbH"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>In this work, we introduce a novel variant of the multivariate quadratic problem, which is at the core of one of the most promising post-quantum alternatives: multivariate cryptography. In this variant, the solution of a given multivariate quadratic system must also be regular, i.e. each fixed-length block of consecutive entries has only one nonzero entry. We prove the NP-completeness of this variant and show similarities and differences with other computational problems used in cryptography. Then we analyze its hardness by reviewing the most common solvers for polynomial systems over finite fields, derive asymptotic formulas for the corresponding complexities and compare the different approaches.<\/jats:p>","DOI":"10.1007\/s10623-025-01717-6","type":"journal-article","created":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T14:45:25Z","timestamp":1756392325000},"page":"5179-5229","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The regular multivariate quadratic problem"],"prefix":"10.1007","volume":"93","author":[{"given":"Antoine","family":"Joux","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rocco","family":"Mora","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,28]]},"reference":[{"key":"1717_CR1","doi-asserted-by":"crossref","unstructured":"Augot D., Finiasz M., Sendrier N.: A family of fast syndrome based cryptographic hash functions. In: Progress in Cryptology\u2013Mycrypt 2005: First International Conference on Cryptology in Malaysia, Kuala Lumpur, Malaysia, September 28-30, 2005. Proceedings 1, pp. 64\u201383. Springer (2005).","DOI":"10.1007\/11554868_6"},{"key":"1717_CR2","unstructured":"Bardet M.: \u00c9tude des syst\u00e8mes alg\u00e9briques surd\u00e9termin\u00e9s. Applications aux codes correcteurs et \u00e0 la cryptographie. PhD Thesis, Universit\u00e9 Pierre et Marie Curie-Paris VI (2004)."},{"key":"1717_CR3","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.dam.2021.11.014","volume":"309","author":"S Barbero","year":"2022","unstructured":"Barbero S., Bellini E., Sanna C., Verbel J.: Practical complexities of probabilistic algorithms for solving Boolean polynomial systems. Discret. Appl. Math. 309, 13\u201331 (2022).","journal-title":"Discret. Appl. Math."},{"key":"1717_CR4","doi-asserted-by":"crossref","unstructured":"Bouillaguet C., Chen H.-C., Cheng C-M., Chou T., Niederhagen R., Shamir A., Yang B.-Y.: Fast exhaustive search for polynomial systems in F2. In: International Workshop on Cryptographic Hardware and Embedded Systems, pp. 203\u2013218. Springer (2010).","DOI":"10.1007\/978-3-642-15031-9_14"},{"key":"1717_CR5","doi-asserted-by":"crossref","unstructured":"Bui D., Carozza E., Couteau G., Goudarzi D., Joux A.: Faster signatures from MPC-in-the-head. In: ASIACRYPT 2024-International Conference on the Theory and Application of Cryptology and Information Security (2024).","DOI":"10.1007\/978-981-96-0875-1_13"},{"key":"1717_CR6","doi-asserted-by":"crossref","unstructured":"Boyle E., Couteau G., Gilboa N., Ishai Y.: Compressing vector OLE. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 896\u2013912 (2018).","DOI":"10.1145\/3243734.3243868"},{"issue":"3","key":"1717_CR7","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1515\/JMC.2009.009","volume":"3","author":"L Bettale","year":"2009","unstructured":"Bettale L., Faugere J., Perret L.: Hybrid approach for solving multivariate systems over finite fields. J. Math. Cryptol. 3(3), 177\u2013197 (2009).","journal-title":"J. Math. Cryptol."},{"key":"1717_CR8","doi-asserted-by":"crossref","unstructured":"Benadjila R., Feneuil T., Rivain M.: MQ on my mind: post-quantum signatures from the non-structured multivariate quadratic problem. In: 2024 IEEE 9th European Symposium on Security and Privacy (EuroS &P), pp. 468\u2013485. IEEE (2024).","DOI":"10.1109\/EuroSP60621.2024.00032"},{"issue":"1","key":"1717_CR9","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.jco.2012.07.001","volume":"29","author":"M Bardet","year":"2013","unstructured":"Bardet M., Faug\u00e8re J.-C., Salvy B., Spaenlehauer P.-J.: On the complexity of solving quadratic Boolean systems. J. Complex. 29(1), 53\u201375 (2013).","journal-title":"J. Complex."},{"key":"1717_CR10","unstructured":"Bardet M., Faugere J.-C., Salvy B., Yang B.-Y.: Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems. In: Proceedings of MEGA, vol. 5, pp. 2\u20132 (2005)."},{"key":"1717_CR11","unstructured":"Bj\u00f6rklund A., Kaski P., Williams R.: Solving systems of polynomial equations over GF (2) by a parity-counting self-reduction. In: International Colloquium on Automata, Languages and Programming, pp. 1\u201313. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2019)."},{"issue":"3","key":"1717_CR12","doi-asserted-by":"publisher","first-page":"384","DOI":"10.1109\/TIT.1978.1055873","volume":"24","author":"E Berlekamp","year":"1978","unstructured":"Berlekamp E., McEliece R., Van Tilborg H.: On the inherent intractability of certain coding problems (corresp.). IEEE Trans. Inf. Theory 24(3), 384\u2013386 (1978).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1717_CR13","doi-asserted-by":"crossref","unstructured":"Briaud P., \u00d8ygarden M.: A new algebraic approach to the regular syndrome decoding problem and implications for PCG constructions. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 391\u2013422. Springer (2023).","DOI":"10.1007\/978-3-031-30589-4_14"},{"issue":"3\u20134","key":"1717_CR14","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1016\/j.jsc.2005.09.007","volume":"41","author":"B Buchberger","year":"2006","unstructured":"Buchberger B.: Bruno Buchberger\u2019s PhD Thesis 1965: an algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. J. Symb. Comput. 41(3\u20134), 475\u2013511 (2006).","journal-title":"J. Symb. Comput."},{"key":"1717_CR15","doi-asserted-by":"crossref","unstructured":"Carozza E., Couteau G., Joux A.: Short signatures from regular syndrome decoding in the head. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 532\u2013563. Springer (2023).","DOI":"10.1007\/978-3-031-30589-4_19"},{"key":"1717_CR16","doi-asserted-by":"crossref","unstructured":"Cheng C.-M., Chou T., Niederhagen R., Yang B.-Y.: Solving quadratic equations with XL on parallel architectures. In: International Workshop on Cryptographic Hardware and Embedded Systems, pp. 356\u2013373. Springer (2012).","DOI":"10.1007\/978-3-642-33027-8_21"},{"key":"1717_CR17","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1016\/j.jsc.2022.05.001","volume":"114","author":"A Caminata","year":"2023","unstructured":"Caminata A., Gorla E.: Solving degree, last fall degree, and related invariants. J. Symb. Comput. 114, 322\u2013335 (2023).","journal-title":"J. Symb. Comput."},{"key":"1717_CR18","doi-asserted-by":"crossref","unstructured":"Courtois N., Klimov A., Patarin J., Shamir A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: International Conference on the Theory and Applications of Cryptographic Techniques, pp. 392\u2013407. Springer (2000).","DOI":"10.1007\/3-540-45539-6_27"},{"key":"1717_CR19","doi-asserted-by":"publisher","unstructured":"Cox D.A., Little J., O\u2019Shea D.: Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra (2015). https:\/\/doi.org\/10.1007\/978-3-319-16721-3.","DOI":"10.1007\/978-3-319-16721-3"},{"key":"1717_CR20","doi-asserted-by":"crossref","unstructured":"Cui H., Liu H., Yan D., Yang K., Yu Y., Zhang K.: Resolved: shorter signatures from regular syndrome decoding and vole-in-the-head. In: IACR International Conference on Public-Key Cryptography, pp. 229\u2013258. Springer (2024).","DOI":"10.1007\/978-3-031-57718-5_8"},{"issue":"205","key":"1717_CR21","first-page":"333","volume":"62","author":"D Coppersmith","year":"1994","unstructured":"Coppersmith D.: Solving homogeneous linear equations over GF (2) via block Wiedemann algorithm. Math. Comput. 62(205), 333\u2013350 (1994).","journal-title":"Math. Comput."},{"key":"1717_CR22","doi-asserted-by":"crossref","unstructured":"Dinur I.: Cryptanalytic applications of the polynomial method for solving multivariate equation systems over GF (2). In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, pp. 374\u2013403. Springer (2021).","DOI":"10.1007\/978-3-030-77870-5_14"},{"key":"1717_CR23","doi-asserted-by":"crossref","unstructured":"Dinur I.: Improved algorithms for solving polynomial systems over GF (2) by multiple parity-counting. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2550\u20132564. SIAM (2021).","DOI":"10.1137\/1.9781611976465.151"},{"key":"1717_CR24","doi-asserted-by":"crossref","unstructured":"Esser A., Santini P.: Not just regular decoding: asymptotics and improvements of regular syndrome decoding attacks. In: Annual International Cryptology Conference, pp. 183\u2013217. Springer (2024).","DOI":"10.1007\/978-3-031-68391-6_6"},{"issue":"1\u20133","key":"1717_CR25","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/S0022-4049(99)00005-5","volume":"139","author":"J-C Faugere","year":"1999","unstructured":"Faugere J.-C.: A new efficient algorithm for computing Gr\u00f6bner bases (F4). J. Pure Appl. Algebra 139(1\u20133), 61\u201388 (1999).","journal-title":"J. Pure Appl. Algebra"},{"key":"1717_CR26","doi-asserted-by":"crossref","unstructured":"Faugere J.C.: A new efficient algorithm for computing Gr\u00f6bner bases without reduction to zero (F 5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, pp. 75\u201383 (2002).","DOI":"10.1145\/780506.780516"},{"issue":"4","key":"1717_CR27","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1006\/jsco.1993.1051","volume":"16","author":"J-C Faugere","year":"1993","unstructured":"Faugere J.-C., Gianni P., Lazard D., Mora T.: Efficient computation of zero-dimensional Gr\u00f6bner bases by change of ordering. J. Symb. Comput. 16(4), 329\u2013344 (1993).","journal-title":"J. Symb. Comput."},{"issue":"2","key":"1717_CR28","doi-asserted-by":"publisher","first-page":"117","DOI":"10.7146\/math.scand.a-12092","volume":"56","author":"R Fr\u00f6berg","year":"1985","unstructured":"Fr\u00f6berg R.: An inequality for Hilbert series of graded algebras. Math. Scand. 56(2), 117\u2013144 (1985).","journal-title":"Math. Scand."},{"issue":"1\u20132","key":"1717_CR29","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/0166-218X(79)90012-X","volume":"1","author":"AS Fraenkel","year":"1979","unstructured":"Fraenkel A.S., Yesha Y.: Complexity of problems in games, graphs and algebraic equations. Discret. Appl. Math. 1(1\u20132), 15\u201330 (1979).","journal-title":"Discret. Appl. Math."},{"issue":"2","key":"1717_CR30","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/s00145-022-09423-5","volume":"35","author":"C Hazay","year":"2022","unstructured":"Hazay C., Orsini E., Scholl P., Soria-Vazquez E.: Tinykeys: a new approach to efficient multi-party computation. J. Cryptol. 35(2), 13 (2022).","journal-title":"J. Cryptol."},{"key":"1717_CR31","doi-asserted-by":"crossref","unstructured":"Lazard D.: Gr\u00f6bner bases, gaussian elimination and resolution of systems of algebraic equations. In: European Conference on Computer Algebra, pp. 146\u2013156. Springer (1983).","DOI":"10.1007\/3-540-12868-9_99"},{"key":"1717_CR32","doi-asserted-by":"crossref","unstructured":"Lokshtanov D., Paturi R., Tamaki S., Williams R., Yu H.: Beating brute force for systems of polynomial equations over finite fields. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 2190\u20132202. SIAM (2017).","DOI":"10.1137\/1.9781611974782.143"},{"key":"1717_CR33","volume-title":"The Algebraic Theory of Modular Systems","author":"FS Macaulay","year":"1994","unstructured":"Macaulay F.S.: The Algebraic Theory of Modular Systems. Cambridge University Press, Cambridge (1994)."},{"key":"1717_CR34","doi-asserted-by":"crossref","unstructured":"Montgomery P.L.: A block Lanczos algorithm for finding dependencies over GF (2). In: International Conference on the Theory and Applications of Cryptographic Techniques, pp. 106\u2013120. Springer (1995).","DOI":"10.1007\/3-540-49264-X_9"},{"issue":"4","key":"1717_CR35","first-page":"598","volume":"41","author":"AA Razborov","year":"1987","unstructured":"Razborov A.A.: Lower bounds on the size of bounded depth circuits over a complete basis with logical addition. Mat. Zametki 41(4), 598\u2013607 (1987).","journal-title":"Mat. Zametki"},{"key":"1717_CR36","volume-title":"Analytic Combinatorics","author":"R Sedgewick","year":"2009","unstructured":"Sedgewick R., Flajolet P.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)."},{"key":"1717_CR37","doi-asserted-by":"crossref","unstructured":"Smolensky R.: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pp. 77\u201382 (1987).","DOI":"10.1145\/28395.28404"},{"issue":"5","key":"1717_CR38","doi-asserted-by":"publisher","first-page":"757","DOI":"10.1006\/jsco.2002.0533","volume":"33","author":"E Thom\u00e9","year":"2002","unstructured":"Thom\u00e9 E.: Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm. J. Symb. Comput. 33(5), 757\u2013775 (2002).","journal-title":"J. Symb. Comput."},{"key":"1717_CR39","doi-asserted-by":"crossref","unstructured":"Valiant L.G., Vazirani V.V.: NP is as easy as detecting unique solutions. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pp. 458\u2013463 (1985).","DOI":"10.1145\/22145.22196"},{"issue":"1","key":"1717_CR40","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1109\/TIT.1986.1057137","volume":"32","author":"D Wiedemann","year":"1986","unstructured":"Wiedemann D.: Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theory 32(1), 54\u201362 (1986).","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1717_CR41","unstructured":"Williams R.R.: The polynomial method in circuit complexity applied to algorithm design (invited talk). In: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Schloss-Dagstuhl-Leibniz Zentrum f\u00fcr Informatik (2014)."},{"key":"1717_CR42","doi-asserted-by":"crossref","unstructured":"Wong R.: Asymptotic approximations of integrals. SIAM (2001).","DOI":"10.1137\/1.9780898719260"}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-025-01717-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10623-025-01717-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-025-01717-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,24]],"date-time":"2025-11-24T15:18:25Z","timestamp":1763997505000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10623-025-01717-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,28]]},"references-count":42,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["1717"],"URL":"https:\/\/doi.org\/10.1007\/s10623-025-01717-6","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"type":"print","value":"0925-1022"},{"type":"electronic","value":"1573-7586"}],"subject":[],"published":{"date-parts":[[2025,8,28]]},"assertion":[{"value":"10 March 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 August 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 August 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 August 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}