{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:16:43Z","timestamp":1758266203454},"reference-count":18,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Fundamentals"],"published-print":{"date-parts":[[2021,1,1]]},"DOI":"10.1587\/transfun.2020cip0025","type":"journal-article","created":{"date-parts":[[2020,12,31]],"date-time":"2020-12-31T22:16:39Z","timestamp":1609452999000},"page":"135-142","source":"Crossref","is-referenced-by-count":3,"title":["Solving the MQ Problem Using Gr\u00f6bner Basis Techniques"],"prefix":"10.1587","volume":"E104.A","author":[{"given":"Takuma","family":"ITO","sequence":"first","affiliation":[{"name":"National Institute of Information and Communications Technology"},{"name":"Graduate School of Science, Tokyo Metropolitan University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Naoyuki","family":"SHINOHARA","sequence":"additional","affiliation":[{"name":"National Institute of Information and Communications Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shigenori","family":"UCHIYAMA","sequence":"additional","affiliation":[{"name":"Graduate School of Science, Tokyo Metropolitan University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] T. Ito, N. Shinohara, and S. Uchiyama, \u201cAn efficient <i>F<\/i><sub>4<\/sub>-style based algorithm to solve MQ problems,\u201d Advances in Information and Computer Security-14th International Workshop on Security, IWSEC 2019, Tokyo, Japan, Aug. 2019, Proceedings, N. Attrapadung and T. Yagi, eds., Lecture Notes in Computer Science, vol.11689, pp.37-52, Springer, 2019. 10.1007\/978-3-030-26834-3_3","DOI":"10.1007\/978-3-030-26834-3_3"},{"key":"2","doi-asserted-by":"publisher","unstructured":"[2] P.W. Shor, \u201cPolynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,\u201d SIAM Rev., vol.41, no.2, pp.303-332, 1999. 10.1137\/s0036144598347011","DOI":"10.1137\/S0036144598347011"},{"key":"3","unstructured":"[3] A. Casanova, J. Faug\u00e8re, G. Macario-Rat, J. Patarin, L. Perret, and J. Ryckeghem, \u201cGeMSS: A great multivariate short signature,\u201d https:\/\/www-polsys.lip6.fr\/Links\/NIST\/GeMSS_specification.pdf"},{"key":"4","doi-asserted-by":"crossref","unstructured":"[4] W. Beullens and B. Preneel, \u201cField lifting for smaller UOV public keys,\u201d Progress in Cryptology-INDOCRYPT 2017-18th International Conference on Cryptology in India, Chennai, India, Dec. 2017, Proceedings, pp.227-246, 2017. 10.1007\/978-3-319-71667-1_12","DOI":"10.1007\/978-3-319-71667-1_12"},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] M. Chen, A. H\u00fclsing, J. Rijneveld, S. Samardjiska, and P. Schwabe, \u201cFrom 5-pass <i>MQ<\/i>-based identification to <i>MQ<\/i>-based signatures,\u201d Advances in Cryptology-ASIACRYPT 2016-22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam, Dec. 2016, Proceedings, Part II, pp.135-165, 2016. 10.1007\/978-3-662-53890-6_5","DOI":"10.1007\/978-3-662-53890-6_5"},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] J. Ding and D. Schmidt, \u201cRainbow, a new multivariable polynomial signature scheme,\u201d Applied Cryptography and Network Security, Third International Conference, ACNS 2005, New York, NY, USA, June 2005, Proceedings, pp.164-175, 2005. 10.1007\/11496137_12","DOI":"10.1007\/11496137_12"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] T. Yasuda, X. Dahan, Y. Huang, T. Takagi, and K. Sakurai, \u201cA multivariate quadratic challenge toward post-quantum generation cryptography,\u201d ACM Commun. Comput. Algebra, vol.49, no.3, pp.105-107, 2015. 10.1145\/2850449.2850462","DOI":"10.1145\/2850449.2850462"},{"key":"8","unstructured":"[8] T. Yasuda, X. Dahan, Y. Huang, T. Takagi, and K. Sakurai, \u201cMQ challenge: Hardness evaluation of solving multivariate quadratic problems,\u201d IACR Cryptology ePrint Archive, vol.2015, p.275, 2015."},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] J.C. Faug\u00e9re, \u201cA new efficient algorithm for computing gr\u00f6bner bases (<i>F<\/i><sub>4<\/sub>),\u201d J. Pure Appl. Algebra, vol.139, no.1-3, pp.61-88, 1999. 10.1016\/s0022-4049(99)00005-5","DOI":"10.1016\/S0022-4049(99)00005-5"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] R.H. Makarim and M. Stevens, \u201cM4GB: An efficient gr\u00f6bner-basis algorithm,\u201d Proc. 2017 ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC 2017, Kaiserslautern, Germany, July 2017, pp.293-300, 2017. 10.1145\/3087604.3087638","DOI":"10.1145\/3087604.3087638"},{"key":"11","doi-asserted-by":"publisher","unstructured":"[11] N. Courtois, A. Klimov, J. Patarin, and A. Shamir, \u201cEfficient algorithms for solving overdefined systems of multivariate polynomial equations,\u201d Advances in Cryptology-EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 2000, Proceeding, pp.392-407, 2000. 10.1007\/3-540-45539-6_27","DOI":"10.1007\/3-540-45539-6_27"},{"key":"12","doi-asserted-by":"crossref","unstructured":"[12] B. Yang and J. Chen, \u201cAll in the XL family: Theory and practice,\u201d Information Security and Cryptology-ICISC 2004, 7th International Conference, Seoul, Korea, Dec. 2004, Revised Selected Papers, pp.67-86, 2004. 10.1007\/11496618_7","DOI":"10.1007\/11496618_7"},{"key":"13","doi-asserted-by":"crossref","unstructured":"[13] C. Cheng, T. Chou, R. Niederhagen, and B. Yang, \u201cSolving quadratic equations with XL on parallel architectures,\u201d Cryptographic Hardware and Embedded Systems-CHES 2012-14th International Workshop, Leuven, Belgium, Sept. 2012. Proceedings, pp.356-373, 2012. 10.1007\/978-3-642-33027-8_21","DOI":"10.1007\/978-3-642-33027-8_21"},{"key":"14","doi-asserted-by":"crossref","unstructured":"[14] A. Joux and V. Vitse, \u201cA crossbred algorithm for solving boolean polynomial systems,\u201d Number-Theoretic Methods in Cryptology-First International Conference, NuTMiC 2017, Warsaw, Poland, Sept. 2017, Revised Selected Papers, pp.3-21, 2017. 10.1007\/978-3-319-76620-1_1","DOI":"10.1007\/978-3-319-76620-1_1"},{"key":"15","doi-asserted-by":"publisher","unstructured":"[15] C. Bouillaguet, C. Cheng, T. Chou, R. Niederhagen, and B. Yang, \u201cFast exhaustive search for quadratic systems in \ud835\udd3d<sub>2<\/sub> on FPGAs,\u201d Selected Areas in Cryptography-SAC 2013-20th International Conference, Burnaby, BC, Canada, Aug. 2013, Revised Selected Papers, pp.205-222, 2013. 10.1007\/978-3-662-43414-7_11","DOI":"10.1007\/978-3-662-43414-7_11"},{"key":"16","unstructured":"[16] M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, 1979."},{"key":"17","doi-asserted-by":"publisher","unstructured":"[17] J. Faug\u00e8re, P.M. Gianni, D. Lazard, and T. Mora, \u201cEfficient computation of zero-dimensional Gr\u00f6bner bases by change of ordering,\u201d J. Symb. Comput., vol.16, no.4, pp.329-344, 1993. 10.1006\/jsco.1993.1051","DOI":"10.1006\/jsco.1993.1051"},{"key":"18","doi-asserted-by":"crossref","unstructured":"[18] T. Becker and V. Weispfenning, Gr\u00f6ebner Bases: A Computationnal Approach to Commutative Algebra, Graduate Texts in Mathematics, Springer, 1993. 10.1007\/978-1-4612-0913-3","DOI":"10.1007\/978-1-4612-0913-3"}],"container-title":["IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E104.A\/1\/E104.A_2020CIP0025\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,2]],"date-time":"2021-01-02T03:37:43Z","timestamp":1609558663000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transfun\/E104.A\/1\/E104.A_2020CIP0025\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,1]]},"references-count":18,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021]]}},"URL":"https:\/\/doi.org\/10.1587\/transfun.2020cip0025","relation":{},"ISSN":["0916-8508","1745-1337"],"issn-type":[{"value":"0916-8508","type":"print"},{"value":"1745-1337","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,1]]}}}