{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T14:00:55Z","timestamp":1760623255221,"version":"3.40.3"},"publisher-location":"Cham","reference-count":66,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031174322"},{"type":"electronic","value":"9783031174339"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-17433-9_14","type":"book-chapter","created":{"date-parts":[[2022,10,5]],"date-time":"2022-10-05T18:11:08Z","timestamp":1664993468000},"page":"323-347","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["An Estimator for\u00a0the\u00a0Hardness of\u00a0the\u00a0MQ Problem"],"prefix":"10.1007","author":[{"given":"Emanuele","family":"Bellini","sequence":"first","affiliation":[]},{"given":"Rusydi H.","family":"Makarim","sequence":"additional","affiliation":[]},{"given":"Carlo","family":"Sanna","sequence":"additional","affiliation":[]},{"given":"Javier","family":"Verbel","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,6]]},"reference":[{"key":"14_CR1","unstructured":"Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. Cryptology ePrint Archive, Report 2015\/046 (2015). https:\/\/eprint.iacr.org\/2015\/046"},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"Alman, J., Williams, V.V.: A refined laser method and faster matrix multiplication. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 522\u2013539 (2021)","DOI":"10.1137\/1.9781611976465.32"},{"key":"14_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1007\/978-3-540-30539-2_24","volume-title":"Advances in Cryptology - ASIACRYPT 2004","author":"G Ars","year":"2004","unstructured":"Ars, G., Faug\u00e8re, J.-C., Imai, H., Kawazoe, M., Sugita, M.: Comparison between XL and Gr\u00f6bner basis algorithms. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 338\u2013353. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-30539-2_24"},{"issue":"5\u20138","key":"14_CR4","first-page":"333","volume":"5","author":"A Ayad","year":"2010","unstructured":"Ayad, A.: A survey on the complexity of solving algebraic systems. Int. Math. Forum 5(5\u20138), 333\u2013353 (2010)","journal-title":"Int. Math. Forum"},{"key":"14_CR5","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":"14_CR6","unstructured":"Bard, G.V.: Algorithms for Solving Linear and Polynomial Systems of Equations over Finite Fields with Applications to Cryptanalysis. Theses, University of Maryland (2007)"},{"key":"14_CR7","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.jsc.2014.09.025","volume":"70","author":"M Bardet","year":"2015","unstructured":"Bardet, M., Faug\u00e8re, J.C., Salvy, B.: On the complexity of the F5 Gr\u00f6bner basis algorithm. J. Symb. Comput. 70, 49\u201370 (2015). https:\/\/doi.org\/10.1016\/j.jsc.2014.09.025","journal-title":"J. Symb. Comput."},{"issue":"1","key":"14_CR8","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). https:\/\/doi.org\/10.1016\/j.jco.2012.07.001","journal-title":"J. Complex."},{"key":"14_CR9","unstructured":"Bellini, E., Makarim, R., Verbel, J.: An estimator for the complexity of the $${MQ}$$ problem (2021). https:\/\/github.com\/Crypto-TII\/multivariate_quadratic_estimator"},{"key":"14_CR10","unstructured":"Bellini, E., Esser, A.: Syndrome decoding estimator (2021). https:\/\/github.com\/Crypto-TII\/syndrome_decoding_estimator"},{"key":"14_CR11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88702-7","volume-title":"Post-Quantum Cryptography","author":"DJ Bernstein","year":"2009","unstructured":"Bernstein, D.J., Buchmann, J., Dahmen, E.: Post-Quantum Cryptography. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-540-88702-7"},{"key":"14_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/978-3-319-79063-3_23","volume-title":"Post-Quantum Cryptography","author":"DJ Bernstein","year":"2018","unstructured":"Bernstein, D.J., Yang, B.-Y.: Asymptotically faster quantum algorithms to solve multivariate quadratic equations. In: Lange, T., Steinwandt, R. (eds.) PQCrypto 2018. LNCS, vol. 10786, pp. 487\u2013506. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-79063-3_23"},{"key":"14_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/978-3-030-45727-3_7","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2020","author":"W Beullens","year":"2020","unstructured":"Beullens, W.: Sigma protocols for MQ, PKP and SIS, and fishy signature schemes. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 183\u2013211. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45727-3_7"},{"key":"14_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1007\/978-3-030-77870-5_13","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2021","author":"W Beullens","year":"2021","unstructured":"Beullens, W.: Improved cryptanalysis of UOV and rainbow. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 348\u2013373. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-77870-5_13"},{"key":"14_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/978-3-030-99277-4_17","volume-title":"Selected Areas in Cryptography","author":"W Beullens","year":"2022","unstructured":"Beullens, W.: MAYO: practical post-quantum signatures from oil-and-vinegar maps. In: AlTawy, R., H\u00fclsing, A. (eds.) SAC 2021. LNCS, vol. 13203, pp. 355\u2013376. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-030-99277-4_17"},{"key":"14_CR16","doi-asserted-by":"publisher","unstructured":"Bj\u00f6rklund, A., Kaski, P., Williams, R.: Solving systems of polynomial equations over GF(2) by a parity-counting self-reduction. In: Baier, C., Chatzigiannakis, I., Flocchini, P., Leonardi, S. (eds.) International Colloquium on Automata, Languages and Programming - ICALP 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.26","DOI":"10.4230\/LIPIcs.ICALP.2019.26"},{"key":"14_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/978-3-642-15031-9_14","volume-title":"Cryptographic Hardware and Embedded Systems, CHES 2010","author":"C Bouillaguet","year":"2010","unstructured":"Bouillaguet, C., et al.: Fast exhaustive search for polynomial systems in $${\\mathbb{F}_2}$$. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol. 6225, pp. 203\u2013218. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15031-9_14"},{"key":"14_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1007\/978-3-662-43414-7_11","volume-title":"Selected Areas in Cryptography \u2013 SAC 2013","author":"C Bouillaguet","year":"2014","unstructured":"Bouillaguet, C., Cheng, C.-M., Chou, T., Niederhagen, R., Yang, B.-Y.: Fast exhaustive search for quadratic systems in $$\\mathbb{F}_{2}$$ on FPGAs. In: Lange, T., Lauter, K., Lison\u011bk, P. (eds.) SAC 2013. LNCS, vol. 8282, pp. 205\u2013222. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43414-7_11"},{"key":"14_CR19","unstructured":"Buchmann, J.A., Ding, J., Mohamed, M.S.E., Mohamed, W.S.A.E.: MutantXL: solving multivariate polynomial equations for cryptanalysis. In: Handschuh, H., Lucks, S., Preneel, B., Rogaway, P. (eds.) Symmetric Cryptography. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany (2009). https:\/\/drops.dagstuhl.de\/opus\/volltexte\/2009\/1945"},{"key":"14_CR20","unstructured":"Casanova, A., Faug\u00e8re, J.C., Macario-Rat, G., Patarin, J., Perret, L., Ryckeghem, J.: GeMSS: a great multivariate short signature. NIST CSRC (2017). https:\/\/www-polsys.lip6.fr\/Links\/NIST\/GeMSS.html"},{"key":"14_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-76581-5_1","volume-title":"Public-Key Cryptography \u2013 PKC 2018","author":"M-S Chen","year":"2018","unstructured":"Chen, M.-S., H\u00fclsing, A., Rijneveld, J., Samardjiska, S., Schwabe, P.: SOFIA: $$\\cal{MQ}$$-based signatures in the QROM. In: Abdalla, M., Dahab, R. (eds.) PKC 2018. LNCS, vol. 10770, pp. 3\u201333. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-76581-5_1"},{"key":"14_CR22","unstructured":"Chen, M.S., H\u00fclsing, A., Rijneveld, J., Samardjiska, S., Schwabe, P.: MQDSS specifications (2020). https:\/\/mqdss.org\/specification.html"},{"key":"14_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"356","DOI":"10.1007\/978-3-642-33027-8_21","volume-title":"Cryptographic Hardware and Embedded Systems \u2013 CHES 2012","author":"C-M Cheng","year":"2012","unstructured":"Cheng, C.-M., Chou, T., Niederhagen, R., Yang, B.-Y.: Solving quadratic equations with XL on parallel architectures. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 356\u2013373. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33027-8_21"},{"key":"14_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/3-540-45539-6_27","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 2000","author":"N Courtois","year":"2000","unstructured":"Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 392\u2013407. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-45539-6_27"},{"key":"14_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1007\/3-540-45664-3_15","volume-title":"Public Key Cryptography","author":"N Courtois","year":"2002","unstructured":"Courtois, N., Goubin, L., Meier, W., Tacier, J.-D.: Solving underdefined systems of multivariate quadratic equations. In: Naccache, D., Paillier, P. (eds.) PKC 2002. LNCS, vol. 2274, pp. 211\u2013227. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45664-3_15"},{"key":"14_CR26","series-title":"Undergraduate Texts in Mathematics","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-35651-8","volume-title":"Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3\/e","author":"DA Cox","year":"2007","unstructured":"Cox, D.A., Little, J., O\u2019Shea, D.: Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra, 3\/e. Undergraduate Texts in Mathematics, Springer, New York (2007)"},{"key":"14_CR27","volume-title":"Solving Polynomial Equations. Foundations, Algorithms, and Applications, Algorithms and Computation in Mathematics","author":"A Dickenstein","year":"2005","unstructured":"Dickenstein, A., Emiris, I.Z.: Solving Polynomial Equations. Foundations, Algorithms, and Applications, Algorithms and Computation in Mathematics, vol. 14. Springer, Heidelberg (2005)"},{"key":"14_CR28","unstructured":"Ding, J., Chen, M., Petzoldt, A., Schmidt, D., Yang, B.: Rainbow. NIST CSRC (2017). https:\/\/csrc.nist.gov\/CSRC\/media\/Projects\/Post-Quantum-Cryptography\/documents\/round-1\/submissions"},{"key":"14_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1007\/11496137_12","volume-title":"Applied Cryptography and Network Security","author":"J Ding","year":"2005","unstructured":"Ding, J., Schmidt, D.: Rainbow, a new multivariable polynomial signature scheme. In: Ioannidis, J., Keromytis, A., Yung, M. (eds.) ACNS 2005. LNCS, vol. 3531, pp. 164\u2013175. Springer, Heidelberg (2005). https:\/\/doi.org\/10.1007\/11496137_12"},{"key":"14_CR30","unstructured":"Ding, J., Zhang, Z., Deaton, J.: How much can F5 really do. Cryptology ePrint Archive, Report 2021\/051 (2021). https:\/\/eprint.iacr.org\/2021\/051"},{"key":"14_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-030-77870-5_14","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2021","author":"I Dinur","year":"2021","unstructured":"Dinur, I.: Cryptanalytic applications of the polynomial method for solving multivariate equation systems over GF(2). In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 374\u2013403. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-77870-5_14"},{"key":"14_CR32","doi-asserted-by":"publisher","unstructured":"Dinur, I.: Improved algorithms for solving polynomial systems over GF(2) by multiple parity-counting. In: ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 2550\u20132564 (2021). https:\/\/doi.org\/10.1137\/1.9781611976465.151","DOI":"10.1137\/1.9781611976465.151"},{"key":"14_CR33","unstructured":"Duarte, J.D.: On the complexity of the crossbred algorithm. Cryptology ePrint Archive, Report 2020\/1058 (2020). https:\/\/eprint.iacr.org\/2020\/1058"},{"key":"14_CR34","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1016\/j.jsc.2016.07.031","volume":"80","author":"C Eder","year":"2017","unstructured":"Eder, C., Faug\u00e8re, J.C.: A survey on signature-based algorithms for computing Gr\u00f6bner bases. J. Symb. Comput. 80, 719\u2013784 (2017)","journal-title":"J. Symb. Comput."},{"key":"14_CR35","unstructured":"Esser, A., Bellini, E.: Syndrome decoding estimator. Cryptology ePrint Archive, Report 2021\/1243 (2021). https:\/\/ia.cr\/2021\/1243"},{"issue":"1","key":"14_CR36","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/S0022-4049(99)00005-5","volume":"139","author":"JC Faug\u00e8re","year":"1999","unstructured":"Faug\u00e8re, J.C.: A new efficient algorithm for computing Gr\u00f6bner bases (F4). J. Pure Appl. Algebra 139(1), 61\u201388 (1999)","journal-title":"J. Pure Appl. Algebra"},{"key":"14_CR37","doi-asserted-by":"crossref","unstructured":"Faug\u00e8re, J.C.: A new efficient algorithm for computing Gr\u00f6bner bases without reduction to zero (F5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC 2002, pp. 75\u201383. Association for Computing Machinery, New York (2002)","DOI":"10.1145\/780506.780516"},{"key":"14_CR38","unstructured":"Faug\u00e8re, J., Horan, K., Kahrobaei, D., Kaplan, M., Kashefi, E., Perret, L.: Fast quantum algorithm for solving multivariate quadratic equations. CoRR abs\/1712.07211 (2017)"},{"issue":"4","key":"14_CR39","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1006\/jsco.1993.1051","volume":"16","author":"JC Faug\u00e8re","year":"1993","unstructured":"Faug\u00e8re, 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."},{"key":"14_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1007\/3-540-47721-7_12","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 86","author":"A Fiat","year":"1987","unstructured":"Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186\u2013194. Springer, Heidelberg (1987). https:\/\/doi.org\/10.1007\/3-540-47721-7_12"},{"key":"14_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/978-3-030-81293-5_4","volume-title":"Post-Quantum Cryptography","author":"H Furue","year":"2021","unstructured":"Furue, H., Nakamura, S., Takagi, T.: Improving Thomae-Wolf algorithm for solving underdetermined multivariate quadratic polynomial problem. In: Cheon, J.H., Tillich, J.-P. (eds.) PQCrypto 2021 2021. LNCS, vol. 12841, pp. 65\u201378. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-81293-5_4"},{"key":"14_CR42","doi-asserted-by":"crossref","unstructured":"Furue, H., Duong, D., Takagi, T.: An efficient MQ-based signature with tight security proof. Int. J. Netw. Comput. 10(2), 308\u2013324 (2020). https:\/\/www.ijnc.org\/index.php\/ijnc\/article\/view\/238","DOI":"10.15803\/ijnc.10.2_308"},{"key":"14_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"632","DOI":"10.1007\/978-3-540-72504-6_58","volume-title":"Theory and Applications of Models of Computation","author":"G Fusco","year":"2007","unstructured":"Fusco, G., Bach, E.: Phase transition of multivariate polynomial systems. In: Cai, J.-Y., Cooper, S.B., Zhu, H. (eds.) TAMC 2007. LNCS, vol. 4484, pp. 632\u2013645. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-72504-6_58"},{"key":"14_CR44","unstructured":"Gashkov, S.B., Sergeev, I.S.: Complexity of computations in finite fields. Fundam. Prikl. Mat. 17(4), 95\u2013131 (2011\/12)"},{"key":"14_CR45","doi-asserted-by":"publisher","unstructured":"Hashimoto, Y.: Algorithms to solve massively under-defined systems of multivariate quadratic equations. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E94.A(6), 1257\u20131262 (2011). https:\/\/doi.org\/10.1587\/transfun.E94.A.1257","DOI":"10.1587\/transfun.E94.A.1257"},{"key":"14_CR46","unstructured":"Huang, H., Bao, W.: Algorithm for solving massively underdefined systems of multivariate quadratic equations over finite fields (2015)"},{"key":"14_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-030-26834-3_3","volume-title":"Advances in Information and Computer Security","author":"T Ito","year":"2019","unstructured":"Ito, T., Shinohara, N., Uchiyama, S.: An efficient $$F_4$$-style based algorithm to solve MQ problems. In: Attrapadung, N., Yagi, T. (eds.) IWSEC 2019. LNCS, vol. 11689, pp. 37\u201352. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-26834-3_3"},{"key":"14_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-319-76620-1_1","volume-title":"Number-Theoretic Methods in Cryptology","author":"A Joux","year":"2018","unstructured":"Joux, A., Vitse, V.: A crossbred algorithm for solving Boolean polynomial systems. In: Kaczorowski, J., Pieprzyk, J., Pomyka\u0142a, J. (eds.) NuTMiC 2017. LNCS, vol. 10737, pp. 3\u201321. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-76620-1_1"},{"key":"14_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1007\/3-540-48910-X_15","volume-title":"Advances in Cryptology \u2014 EUROCRYPT \u201999","author":"A Kipnis","year":"1999","unstructured":"Kipnis, A., Patarin, J., Goubin, L.: Unbalanced oil and vinegar signature schemes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 206\u2013222. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48910-X_15"},{"key":"14_CR50","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/3-540-12868-9_99","volume-title":"Computer Algebra","author":"D Lazard","year":"1983","unstructured":"Lazard, D.: Gr\u00f6bner bases, Gaussian elimination and resolution of systems of algebraic equations. In: van Hulzen, J.A. (ed.) EUROCAL 1983. LNCS, vol. 162, pp. 146\u2013156. Springer, Heidelberg (1983). https:\/\/doi.org\/10.1007\/3-540-12868-9_99"},{"key":"14_CR51","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: Symposium on Discrete Algorithms, SODA 2017, pp. 2190\u20132202. Society for Industrial and Applied Mathematics, USA (2017)","DOI":"10.1137\/1.9781611974782.143"},{"key":"14_CR52","doi-asserted-by":"crossref","unstructured":"Makarim, R.H., Stevens, M.: M4GB: an efficient Gr\u00f6bner-basis algorithm. In: Burr, M.A., Yap, C.K., Din, M.S.E. (eds.) Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC 2017, Kaiserslautern, Germany, pp. 293\u2013300. ACM (2017). https:\/\/doi.org\/10.1145\/3087604.3087638","DOI":"10.1145\/3087604.3087638"},{"key":"14_CR53","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1007\/978-3-642-38616-9_8","volume-title":"Post-Quantum Cryptography","author":"H Miura","year":"2013","unstructured":"Miura, H., Hashimoto, Y., Takagi, T.: Extended algorithm for solving underdefined multivariate quadratic equations. In: Gaborit, P. (ed.) PQCrypto 2013. LNCS, vol. 7932, pp. 118\u2013135. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38616-9_8"},{"key":"14_CR54","unstructured":"Moody, D.: The homestretch: the beginning of the end of the NIST PQC 3rd round. In: International Conference on Post-Quantum Cryptography (2021). https:\/\/pqcrypto2021.kr\/download\/program\/2.2_PQCrypto2021.pdf"},{"key":"14_CR55","unstructured":"Mou, C.: Solving Polynomial Systems over Finite Fields: Algorithms, Implementation and Applications. Theses, Universit\u00e9 Pierre et Marie Curie (2013)"},{"key":"14_CR56","unstructured":"Niederhagen, R.: Parallel cryptanalysis. Ph.D. thesis, Eindhoven University of Technology (2012). https:\/\/polycephaly.org\/thesis\/index.shtml"},{"key":"14_CR57","unstructured":"Ning, K.C.: An adaption of the crossbred algorithm for solving multivariate quadratic systems over $$\\mathbb{F} _2$$ on GPUs (2017). https:\/\/pure.tue.nl\/ws\/portalfiles\/portal\/91105984\/NING.K_parallel_cb_v103.pdf"},{"key":"14_CR58","unstructured":"NIST: Submission requirements and evaluation criteria for the post-quantum cryptography standardization process (2017). https:\/\/csrc.nist.gov\/CSRC\/media\/Projects\/Post-Quantum-Cryptography\/documents\/call-for-proposals-final-dec-2016.pdf"},{"key":"14_CR59","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"706","DOI":"10.1007\/978-3-642-22792-9_40","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"K Sakumoto","year":"2011","unstructured":"Sakumoto, K., Shirai, T., Hiwatari, H.: Public-key identification schemes based on multivariate quadratic polynomials. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 706\u2013723. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22792-9_40"},{"key":"14_CR60","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/978-3-319-49445-6_17","volume-title":"Security, Privacy, and Applied Cryptography Engineering","author":"P Schwabe","year":"2016","unstructured":"Schwabe, P., Westerbaan, B.: Solving binary $$\\cal{MQ}$$ with Grover\u2019s algorithm. In: Carlet, C., Hasan, M.A., Saraswat, V. (eds.) SPACE 2016. LNCS, vol. 10076, pp. 303\u2013322. Springer, Cham (2016). https:\/\/doi.org\/10.1007\/978-3-319-49445-6_17"},{"key":"14_CR61","unstructured":"Seres, I.A., Horv\u00e1th, M., Burcsi, P.: The Legendre pseudorandom function as a multivariate quadratic cryptosystem: security and applications. Cryptology ePrint Archive, Report 2021\/182 (2021). https:\/\/ia.cr\/2021\/182"},{"issue":"4","key":"14_CR62","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/BF02165411","volume":"13","author":"V Strassen","year":"1969","unstructured":"Strassen, V.: Gaussian elimination is not optimal. Numer. Math. 13(4), 354\u2013356 (1969)","journal-title":"Numer. Math."},{"key":"14_CR63","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/978-3-642-30057-8_10","volume-title":"Public Key Cryptography \u2013 PKC 2012","author":"E Thomae","year":"2012","unstructured":"Thomae, E., Wolf, C.: Solving underdetermined systems of multivariate quadratic equations revisited. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 156\u2013171. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-30057-8_10"},{"key":"14_CR64","unstructured":"Ullah, E.: New techniques for polynomial system solving. Theses, Universit\u00e4t Passau (2012)"},{"key":"14_CR65","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/978-3-540-27800-9_24","volume-title":"Information Security and Privacy","author":"B-Y Yang","year":"2004","unstructured":"Yang, B.-Y., Chen, J.-M.: Theoretical analysis of XL over small fields. In: Wang, H., Pieprzyk, J., Varadharajan, V. (eds.) ACISP 2004. LNCS, vol. 3108, pp. 277\u2013288. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-27800-9_24"},{"key":"14_CR66","unstructured":"Yasuda, T., Dahan, X., Huang, Y.J., Takagi, T., Sakurai, K.: MQ challenge: hardness evaluation of solving multivariate quadratic problems. In: NIST Workshop on Cybersecurity in a Post-Quantum World, Washington, D.C (2015). https:\/\/www.mqchallenge.org"}],"container-title":["Lecture Notes in Computer Science","Progress in Cryptology - AFRICACRYPT 2022"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-17433-9_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,5]],"date-time":"2022-10-05T18:13:26Z","timestamp":1664993606000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-17433-9_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031174322","9783031174339"],"references-count":66,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-17433-9_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"6 October 2022","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"AFRICACRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Cryptology in Africa","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Fes","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Morocco","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 July 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 July 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"africacrypt2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/africacrypt2022.cs.ru.nl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"easychair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"68","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"25","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"37% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.4","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"6.5","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}