{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,29]],"date-time":"2026-09-29T14:52:21Z","timestamp":1790693541365,"version":"4.1.0"},"publisher-location":"Berlin, Heidelberg","reference-count":37,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642386152","type":"print"},{"value":"9783642386169","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38616-9_4","type":"book-chapter","created":{"date-parts":[[2013,6,4]],"date-time":"2013-06-04T03:55:16Z","timestamp":1370318116000},"page":"52-66","source":"Crossref","is-referenced-by-count":35,"title":["Degree of Regularity for HFEv and HFEv-"],"prefix":"10.1007","author":[{"given":"Jintai","family":"Ding","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bo-Yin","family":"Yang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"4_CR1","unstructured":"Bardet, M., Faug\u00e8re, J.-C., Salvy, B.: On the complexity of Gr\u00f6bner basis computation of semi-regular overdetermined algebraic equations. In: Proceedings of the International Conference on Polynomial System Solving, pp. 71\u201374 (2004); Previously INRIA report RR-5049"},{"key":"4_CR2","unstructured":"Bardet, M., Faug\u00e8re, J.-C., Salvy, B., Yang, B.-Y.: Asymptotic expansion of the degree of regularity for semi-regular systems of equations. In: Gianni, P. (ed.) MEGA 2005 Sardinia, Italy (2005)"},{"key":"4_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/978-3-642-19379-8_27","volume-title":"Public Key Cryptography \u2013 PKC 2011","author":"L. Bettale","year":"2011","unstructured":"Bettale, L., Faug\u00e8re, J.-C., Perret, L.: Cryptanalysis of multivariate and odd-characteristic HFE variants. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol.\u00a06571, pp. 441\u2013458. Springer, Heidelberg (2011)"},{"key":"4_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/978-3-642-10366-7_27","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2009","author":"O. Billet","year":"2009","unstructured":"Billet, O., Macario-Rat, G.: Cryptanalysis of the square cryptosystems. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol.\u00a05912, pp. 451\u2013468. Springer, Heidelberg (2009)"},{"key":"4_CR5","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., Chen, H.-C., Cheng, C.-M., Chou, T., Niederhagen, R., Shamir, A., Yang, B.-Y.: Fast exhaustive search for polynomial systems in ${\\mathbb{F}_2}$ . In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol.\u00a06225, pp. 203\u2013218. Springer, Heidelberg (2010)"},{"key":"4_CR6","unstructured":"Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, Innsbruck (1965)"},{"key":"4_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1007\/978-3-642-00862-7_17","volume-title":"Topics in Cryptology \u2013 CT-RSA 2009","author":"C. Clough","year":"2009","unstructured":"Clough, C., Baena, J., Ding, J., Yang, B.-Y., Chen, M.-S.: Square, a new multivariate encryption scheme. In: Fischlin, M. (ed.) CT-RSA 2009. LNCS, vol.\u00a05473, pp. 252\u2013264. Springer, Heidelberg (2009)"},{"key":"4_CR8","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.\u00a02274, pp. 211\u2013227. Springer, Heidelberg (2002)"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/3-540-45353-9_20","volume-title":"Topics in Cryptology - CT-RSA 2001","author":"N.T. Courtois","year":"2001","unstructured":"Courtois, N.T.: The security of hidden field equations (HFE). In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol.\u00a02020, pp. 266\u2013281. Springer, Heidelberg (2001)"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/3-540-36288-6_25","volume-title":"Public Key Cryptography - PKC 2003","author":"N.T. Courtois","year":"2002","unstructured":"Courtois, N.T., Daum, M., Felke, P.: On the security of HFE, HFEv- and Quartz. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol.\u00a02567, pp. 337\u2013350. Springer, Heidelberg (2002)"},{"key":"4_CR11","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 - EUROCRYPT 2000","author":"N.T. Courtois","year":"2000","unstructured":"Courtois, N.T., Klimov, A., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol.\u00a01807, pp. 392\u2013407. Springer, Heidelberg (2000), http:\/\/www.minrank.org\/xlfull.pdf"},{"key":"4_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/978-3-540-30539-2_23","volume-title":"Advances in Cryptology - ASIACRYPT 2004","author":"C. Diem","year":"2004","unstructured":"Diem, C.: The XL-algorithm and a conjecture from commutative algebra. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol.\u00a03329, pp. 323\u2013337. Springer, Heidelberg (2004)"},{"key":"4_CR13","unstructured":"Ding, J., Buchmann, J., Mohamed, M.S.E., Mohamed, W.S.A.E., Weinmann, R.-P.: Mutant XL. Talk at the First International Conference on Symbolic Computation and Cryptography (SCC 2008), Beijing (2008)"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Ding, J., Hodges, T.J.: Inverting HFE systems is quasi-polynomial for all fields. In: Rogaway [31], pp. 724\u2013742","DOI":"10.1007\/978-3-642-22792-9_41"},{"key":"4_CR15","unstructured":"Ding, J., Kleinjung, T.: Degree of regularity for HFE\u2212. Cryptology ePrint Archive, Report 2011\/570 (2011), http:\/\/eprint.iacr.org\/"},{"key":"4_CR16","first-page":"193","volume-title":"Post Quantum Cryptography","author":"J. Ding","year":"2008","unstructured":"Ding, J., Yang, B.-Y.: Multivariate public key cryptography. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.) Post Quantum Cryptography, 1st edn., pp. 193\u2013241. Springer, Berlin (2008) ISBN 3-540-88701-6","edition":"1"},{"key":"4_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1007\/978-3-642-17373-8_32","volume-title":"Advances in Cryptology - ASIACRYPT 2010","author":"V. Dubois","year":"2010","unstructured":"Dubois, V., Gama, N.: The degree of regularity of HFE systems. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol.\u00a06477, pp. 557\u2013576. Springer, Heidelberg (2010)"},{"key":"4_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/978-3-540-71677-8_17","volume-title":"Public Key Cryptography \u2013 PKC 2007","author":"V. Dubois","year":"2007","unstructured":"Dubois, V., Granboulan, L., Stern, J.: Cryptanalysis of HFE with internal perturbation. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol.\u00a04450, pp. 249\u2013265. Springer, Heidelberg (2007)"},{"key":"4_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/978-3-540-45146-4_3","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"J.-C. Faug\u00e8re","year":"2003","unstructured":"Faug\u00e8re, J.-C., Joux, A.: Algebraic Cryptanalysis of Hidden Field Equation (HFE) Cryptosystems Using Gr\u00f6bner Bases. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol.\u00a02729, pp. 44\u201360. Springer, Heidelberg (2003)"},{"key":"4_CR20","series-title":"Lecture Notes in Computer Science","volume-title":"Public Key Cryptography \u2013 PKC 2012","year":"2012","unstructured":"Fischlin, M., Buchmann, J., Manulis, M. (eds.): PKC 2012. LNCS, vol.\u00a07293. Springer, Heidelberg (2012)"},{"key":"4_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/11818175_20","volume-title":"Advances in Cryptology - CRYPTO 2006","author":"L. Granboulan","year":"2006","unstructured":"Granboulan, L., Joux, A., Stern, J.: Inverting HFE is quasipolynomial. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol.\u00a04117, pp. 345\u2013356. Springer, Heidelberg (2006)"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Huang, Y.-J., Liu, F.-H., Yang, B.-Y.: Public-key cryptography from new multivariate quadratic assumptions. In: Fischlin et\u00a0al. [20], pp. 190\u2013205","DOI":"10.1007\/978-3-642-30057-8_12"},{"key":"4_CR23","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 - 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.\u00a01592, pp. 206\u2013222. Springer, Heidelberg (1999)"},{"key":"4_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/3-540-48405-1_2","volume-title":"Advances in Cryptology - CRYPTO \u201999","author":"A. Kipnis","year":"1999","unstructured":"Kipnis, A., Shamir, A.: Cryptanalysis of the HFE public key cryptosystem by relinearization. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol.\u00a01666, pp. 19\u201330. Springer, Heidelberg (1999), http:\/\/www.minrank.org\/hfesubreg.ps"},{"key":"4_CR25","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.) ISSAC 1983 and EUROCAL 1983. LNCS, vol.\u00a0162, pp. 146\u2013156. Springer, Heidelberg (1983)"},{"key":"4_CR26","unstructured":"Lidl, R., Niederreiter, H.: Finite Fields, 2nd edn. Encyclopedia of Mathematics and its Application, vol.\u00a020. Cambridge University Press (2003)"},{"key":"4_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1007\/3-540-44750-4_20","volume-title":"Advances in Cryptology - CRYPTO \u201995","author":"J. Patarin","year":"1995","unstructured":"Patarin, J.: Cryptanalysis of the Matsumoto and Imai Public Key Scheme of Eurocrypt \u201988. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol.\u00a0963, pp. 248\u2013261. Springer, Heidelberg (1995)"},{"key":"4_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/3-540-68339-9_4","volume-title":"Advances in Cryptology - EUROCRYPT \u201996","author":"J. Patarin","year":"1996","unstructured":"Patarin, J.: Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): Two New Families of Asymmetric Algorithms. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol.\u00a01070, pp. 33\u201348. Springer, Heidelberg (1996), http:\/\/www.minrank.org\/hfe.pdf"},{"key":"4_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1007\/3-540-45353-9_21","volume-title":"Topics in Cryptology - CT-RSA 2001","author":"J. Patarin","year":"2001","unstructured":"Patarin, J., Courtois, N.T., Goubin, L.: QUARTZ, 128-bit long digital signatures. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol.\u00a02020, pp. 282\u2013288. Springer, Heidelberg (2001)"},{"issue":"4","key":"4_CR30","doi-asserted-by":"crossref","first-page":"317","DOI":"10.26421\/QIC3.4-3","volume":"3","author":"J. Proos","year":"2003","unstructured":"Proos, J., Zalka, C.: Shor\u2019s discrete logarithm quantum algorithm for elliptic curves. Quantum Information & Computation\u00a03(4), 317\u2013344 (2003)","journal-title":"Quantum Information & Computation"},{"key":"4_CR31","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","year":"2011","unstructured":"Rogaway, P. (ed.): Advances in Cryptology \u2013 CRYPTO 2011. LNCS, vol.\u00a06841. Springer, Heidelberg (2011)"},{"key":"4_CR32","doi-asserted-by":"crossref","unstructured":"Sakumoto, K.: Public-key identification schemes based on multivariate cubic polynomials. In: Fischlin et\u00a0al. [20], pp. 172\u2013189","DOI":"10.1007\/978-3-642-30057-8_11"},{"key":"4_CR33","doi-asserted-by":"crossref","unstructured":"Sakumoto, K., Shirai, T., Hiwatari, H.: Public-key identification schemes based on multivariate quadratic polynomials. In: Rogaway [31], pp. 706\u2013723","DOI":"10.1007\/978-3-642-22792-9_40"},{"issue":"5","key":"4_CR34","doi-asserted-by":"publisher","first-page":"1484","DOI":"10.1137\/S0097539795293172","volume":"26","author":"P.W. Shor","year":"1997","unstructured":"Shor, P.W.: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing\u00a026(5), 1484\u20131509 (1997)","journal-title":"SIAM Journal on Computing"},{"key":"4_CR35","doi-asserted-by":"crossref","unstructured":"Thomae, E., Wolf, C.: Solving underdetermined systems of multivariate quadratic equations revisited. In: Fischlin et\u00a0al. [20], pp. 156\u2013171.","DOI":"10.1007\/978-3-642-30057-8_10"},{"key":"4_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1007\/11496618_7","volume-title":"Information Security and Cryptology \u2013 ICISC 2004","author":"B.-Y. Yang","year":"2005","unstructured":"Yang, B.-Y., Chen, J.-M.: All in the XL family: Theory and practice. In: Park, C.-s., Chee, S. (eds.) ICISC 2004. LNCS, vol.\u00a03506, pp. 67\u201386. Springer, Heidelberg (2005)"},{"key":"4_CR37","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.\u00a03108, pp. 277\u2013288. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Post-Quantum Cryptography"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38616-9_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T17:33:34Z","timestamp":1645637614000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38616-9_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642386152","9783642386169"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38616-9_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}