{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,30]],"date-time":"2026-03-30T21:51:38Z","timestamp":1774907498554,"version":"3.50.1"},"reference-count":48,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2012,2,12]],"date-time":"2012-02-12T00:00:00Z","timestamp":1329004800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Des. Codes Cryptogr."],"published-print":{"date-parts":[[2013,10]]},"DOI":"10.1007\/s10623-012-9617-2","type":"journal-article","created":{"date-parts":[[2012,2,11]],"date-time":"2012-02-11T10:36:07Z","timestamp":1328956567000},"page":"1-52","source":"Crossref","is-referenced-by-count":86,"title":["Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic"],"prefix":"10.1007","volume":"69","author":[{"given":"Luk","family":"Bettale","sequence":"first","affiliation":[]},{"given":"Jean-Charles","family":"Faug\u00e8re","sequence":"additional","affiliation":[]},{"given":"Ludovic","family":"Perret","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2012,2,12]]},"reference":[{"key":"9617_CR1","doi-asserted-by":"crossref","DOI":"10.1090\/gsm\/003","volume-title":"An Introduction to Gr\u00f6bner Bases, Graduate Studies in Mahematics, vol. 3","author":"W.W. Adams","year":"1994","unstructured":"Adams W.W., Loustaunau P.: An Introduction to Gr\u00f6bner Bases, Graduate Studies in Mahematics, vol. 3. AMS, Providence (1994)"},{"key":"9617_CR2","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 International Conference on Polynomial System Solving (ICPSS), pp. 71\u201375 (2004)."},{"key":"9617_CR3","unstructured":"Bardet M., Faug\u00e8re J.C., Salvy B., Yang B.Y.: Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems. In: Proceedings of MEGA 2005, Eighth International Symposium on Effective Methods in Algebraic Geometry (2005)."},{"key":"9617_CR4","doi-asserted-by":"crossref","unstructured":"Bettale L., Faug\u00e8re J.C., Perret L.: Hybrid approach for solving multivariate systems over finite fields. J. Math. Cryptol. 177\u2013197 (2009).","DOI":"10.1515\/JMC.2009.009"},{"key":"9617_CR5","unstructured":"Bettale L., Faug\u00e8re J.C., Perret L.: Cryptanalysis of multivariate and odd-characteristic hfe variants. In: Public Key Cryptography\u2014PKC 2011. Lecture Notes in Computer Science, vol. 6571, pp. 441\u2013458. Springer, Berlin (2011)."},{"key":"9617_CR6","unstructured":"Billet O., Patarin J., Seurin Y.: Analysis of intermediate field systems. In: SCC 2008 (2008)."},{"key":"9617_CR7","unstructured":"Bogdanov A., Eisenbarth T., Rupp A., Wolf C.: Time-area optimized public-key engines: MQ-cryptosystems as replacement for elliptic curves? In: Cryptographic Hardware and Embedded Systems\u2014CHES \u201908, LNCS, pp. 45\u201361 (2008)."},{"issue":"3\u20134","key":"9617_CR8","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1006\/jsco.1996.0125","volume":"24","author":"W. Bosma","year":"1997","unstructured":"Bosma W., Cannon J.J., Playoust C.: The Magma algebra system I: the user language. J. Symb. Comput. 24(3\u20134), 235\u2013265 (1997)","journal-title":"J. Symb. Comput."},{"key":"9617_CR9","unstructured":"Buchberger B.: Ein algorithmus zum auffinden der basiselemente des restklassenringes nach einem nulldimensionalen polynomideal. PhD thesis, University of Innsbruck (1965)."},{"issue":"3\u20134","key":"9617_CR10","doi-asserted-by":"crossref","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."},{"issue":"3\u20134","key":"9617_CR11","doi-asserted-by":"crossref","first-page":"471","DOI":"10.1016\/j.jsc.2005.09.008","volume":"41","author":"B. Buchberger","year":"2006","unstructured":"Buchberger B.: Comments on the translation of my phd thesis. J. Symb. Comput. 41(3\u20134), 471\u2013474 (2006)","journal-title":"J. Symb. Comput."},{"key":"9617_CR12","doi-asserted-by":"crossref","unstructured":"Buss W., Frandsen G., Shallit J.: The computational complexity of some problems of linear algebra. J. Comput. Syst. Sci. (1999).","DOI":"10.1006\/jcss.1998.1608"},{"key":"9617_CR13","unstructured":"Chen C.H.O., Chen M.S., Ding J., Werner F., Yang B.Y.: Odd-char multivariate hidden field equations. Cryptology ePrint Archive (2008) http:\/\/eprint.iacr.org\/2008\/543 ."},{"key":"9617_CR14","unstructured":"Chen A.I.T., Chen M.S., Chen T.R., Cheng C.M., Ding J., Kuo E.L.H., Lee F.Y.S., Yang B.Y.: SSE implementation of multivariate PKCs on modern x86 CPUs. In: Cryptographic Hardware and Embedded Systems\u2014CHES 2009, Lecture Notes in Computer Science, vol. 5747, pp. 33\u201348. Springer, Berlin (2009)."},{"key":"9617_CR15","unstructured":"Courtois N.T.: Efficient zero-knowledge authentication based on a linear algebra problem MinRank. In: Advances in Cryptology\u2014ASIACRYPT 2001, Lecture Notes in Computer Science, vol. 2248, pp. 402\u2013421. Springer, Berlin (2001)."},{"key":"9617_CR16","unstructured":"Courtois N., Goubin L.: Cryptanalysis of the TTM cryptosystem. In: Advances in Cryptology\u2014ASIACRYPT \u201900, Lecture Notes in Computer Science, vol. 1976, pp. 44\u201357. Springer, Berlin (2000)."},{"key":"9617_CR17","volume-title":"Ideals, Varieties and Algorithms","author":"D.A. Cox","year":"2005","unstructured":"Cox D.A., Little J.B., O\u2019Shea D.: Ideals, Varieties and Algorithms. Sringer, Berlin (2005)"},{"issue":"4","key":"9617_CR18","doi-asserted-by":"crossref","first-page":"192","DOI":"10.1016\/0020-0190(78)90067-4","volume":"7","author":"R. DeMillo","year":"1978","unstructured":"DeMillo R., Lipton R.: A probabilistic remark on algebraic program testing. Inf. Process. Lett. 7(4), 192\u2013194 (1978)","journal-title":"Inf. Process. Lett."},{"key":"9617_CR19","unstructured":"Ding J., Hodges T.J.: Inverting HFE systems is quasi-polynomial for all fields. In: Rogaway P. (ed.) CRYPTO, Lecture Notes in Computer Science, vol. 6841, pp. 724\u2013742. Springer, Berlin (2011)."},{"key":"9617_CR20","unstructured":"Ding J., Schmidt D., Werner F.: Algebraic attack on HFE revisited. In: Information Security, Lecture Notes in Computer Science, vol. 5222, pp. 215\u2013227. Springer, Berlin (2008)."},{"key":"9617_CR21","unstructured":"Dubois V., Gama N.: The degree of regularity of HFE systems. In: Advances in Cryptology\u2014ASIACRYPT 2011, Lecture Notes in Computer Science, vol. 6477, pp. 557\u2013576. Springer, Berlin (2011)."},{"key":"9617_CR22","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1016\/S0022-4049(99)00005-5","volume":"139","author":"J.C. Faug\u00e8re","year":"1999","unstructured":"Faug\u00e8re J.C.: A new efficient algorithm for computing Gr\u00f6bner bases (F4). J. Pure Appl. Algebra 139, 61\u201388 (1999)","journal-title":"J. Pure Appl. Algebra"},{"key":"9617_CR23","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, pp. 75\u201383. ACM Press (2002).","DOI":"10.1145\/780506.780516"},{"key":"9617_CR24","unstructured":"Faug\u00e8re J.C.: Algebraic cryptanalysis of HFE using Gr\u00f6bner bases. Reasearch report RR-4738, INRIA http:\/\/hal.inria.fr\/inria-00071849\/PDF\/RR-4738.pdf (2003)."},{"key":"9617_CR25","unstructured":"Faug\u00e8re J.C.: FGb: a library for computing Gr\u00f6bner bases. In: Fukuda K., Hoeven J., Joswig M., Takayama N. (eds.) Mathematical Software\u2014ICMS 2010, Lecture Notes in Computer Science, vol. 6327, pp. 84\u201387. Springer, Berlin. http:\/\/www-salsa.lip6.fr\/~jcf\/Papers\/ICMS.pdf (2010)."},{"key":"9617_CR26","unstructured":"Faug\u00e8re J.C., Joux A.: Algebraic cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gr\u00f6bner bases. In: Advances in Cryptology\u2014CRYPTO 2003, Lecture Notes in Computer Science, vol. 2729, pp. 44\u201360. Springer, Berlin (2003)."},{"key":"9617_CR27","unstructured":"Faug\u00e8re J.C., Levy-dit-Vehel F., Perret L.: Cryptanalysis of MinRank. In: Advances in Cryptology\u2014CRYPTO 2008, Lecture Notes in Computer Science, vol. 5157, pp. 280\u2013296. Springer, Berlin (2008)."},{"key":"9617_CR28","unstructured":"Faug\u00e8re J.C., Safey El Din M., Spaenlehauer P.J.: Computing loci of rank defects of linear matrices using Gr\u00f6bner bases and applications to cryptology. In: Koepf W. (eds.), ISSAC, pp. 257\u2013264. ACM (2010)."},{"key":"9617_CR29","unstructured":"Faug\u00e8re J.C., Safey El Din M., Spaenlehauer P.J.: Gr\u00f6bner bases of bihomogeneous ideals generated by polynomials of bidegree (1,1): algorithms and complexity. J. Symb. Comput. 1\u201339 (2010)."},{"key":"9617_CR30","unstructured":"Faug\u00e8re J.C., Safey El Din M., Spaenlehauer P.J.: On the complexity of the generalized minrank problem, preprint (2011)."},{"key":"9617_CR31","doi-asserted-by":"crossref","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, 117\u2013144 (1985)","journal-title":"Math. Scand."},{"key":"9617_CR32","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. Garey","year":"1979","unstructured":"Garey M.R., Johnson D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, New York (1979)"},{"key":"9617_CR33","unstructured":"Granboulan L., Joux A., Stern J.: Inverting HFE is quasipolynomial. In: Advances in Cryptology\u2014CRYPTO 2006, Lecture Notes in Computer Science, vol. 4117, pp. 345\u2013356. Springer, Berlin (2006)."},{"key":"9617_CR34","unstructured":"Jiang X., Ding J., Hu L.: Kipnis-Shamir attack on HFE revisited. In: Information Security and Cryptology, Lecture Notes in Computer Science, vol. 4990, pp. 399\u2013411. Springer, Berlin (2007)."},{"key":"9617_CR35","unstructured":"Kipnis A., Shamir A.: Cryptanalysis of the HFE public key cryptosystem by relinearization. In: Advances in Cryptology\u2014CRYPTO \u201999, Lecture Notes in Computer Science, vol. 1666, pp. 19\u201330. Springer, Berlin (1999)."},{"key":"9617_CR36","unstructured":"Kipnis A., Patarin J., Goubin L.: Unbalanced oil and vinegar signature schemes. In: Advances in Cryptology\u2014EUROCRYPT \u201999, Lecture Notes in Computer Science, vol. 1592, pp. 206\u2013222. Springer, Berlin (1999)."},{"key":"9617_CR37","unstructured":"Matsumoto T., Imai H.: Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In: Advances in Cryptology\u2014EUROCRYPT \u201988, Lecture Notes in Computer Science, vol. 330, pp. 419\u2013453. Springer, Berlin (1988)."},{"issue":"5","key":"9617_CR38","doi-asserted-by":"crossref","first-page":"2207","DOI":"10.1080\/00927879908826559","volume":"27","author":"T.T. Moh","year":"1999","unstructured":"Moh T.T.: A public key system with signature and master key functions. Commun. Algebra 27(5), 2207\u20132222 (1999)","journal-title":"Commun. Algebra"},{"key":"9617_CR39","unstructured":"Nguyen P.: New trends in cryptology, european project stork: Strategic roadmap for advances in cryptology\u2014crypto. ist-2002-38273. http:\/\/www.di.ens.fr\/~pnguyen\/pub.html#Ng03 (2003)."},{"key":"9617_CR40","unstructured":"Patarin J.: Cryptoanalysis of the Matsumoto and Imai public key scheme of Eurocrypt \u201988. In: Advances in Cryptology\u2014CRYPTO \u201995, pp. 248\u2013261. Springer, Berlin (1995)."},{"key":"9617_CR41","unstructured":"Patarin J.: Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In: Advances in Cryptology\u2014EUROCRYPT \u201996, Lecture Notes in Computer Science, vol. 1070, pp. 33\u201348. Springer, Berlin (1996)."},{"issue":"4","key":"9617_CR42","doi-asserted-by":"crossref","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"J.T. Schwartz","year":"1980","unstructured":"Schwartz J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701\u2013717 (1980)","journal-title":"J. ACM"},{"key":"9617_CR43","doi-asserted-by":"crossref","DOI":"10.1090\/coll\/023","volume-title":"Orthogonal Polynomials","author":"G. Szeg\u00f6","year":"1939","unstructured":"Szeg\u00f6 G.: Orthogonal Polynomials, 4th edn. American Mathematical Society, Providence (1939)","edition":"4"},{"key":"9617_CR44","unstructured":"Wang L.C., Hu Y.H., Lai F., yen Chou C., Yang B.Y.: Tractable rational map signature. In: Public Key Cryptography\u2014PKC \u201905, Lecture Notes in Computer Science, vol. 3386, pp. 244\u2013257. Springer, Berlin (2005)."},{"key":"9617_CR45","unstructured":"Wolf C., Preneel B.: Equivalent keys in HFE, C*, and variations. In: Progress in Cryptology\u2014Mycrypt 2005, Lecture Notes in Computer Science, vol. 3715, pp. 33\u201349. Springer, Berlin (2005)."},{"key":"9617_CR46","unstructured":"Wolf C., Preneel B.: Large superfluous keys in multivariate quadratic asymmetric systems. In: Public Key Cryptography\u2014PKC 2005, Lecture Notes in Computer Science, vol. 3386, pp. 275\u2013287. Springer, Berlin (2005)."},{"issue":"4","key":"9617_CR47","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1515\/jmc.2011.004","volume":"4","author":"C. Wolf","year":"2011","unstructured":"Wolf C., Preneel B.: Equivalent keys in multivariate quadratic public key systems. J. Math. Cryptol. 4(4), 375\u2013415 (2011)","journal-title":"J. Math. Cryptol."},{"key":"9617_CR48","unstructured":"Zippel R.: Probabilistic algorithms for sparse polynomials. In: Symbolic and Algebraic Computation (EUROSAM\u201979), International Symposium, Lecture Notes in Computer Science, vol. 72, pp. 216\u2013226. Springer, Berlin (1979)."}],"container-title":["Designs, Codes and Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-012-9617-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10623-012-9617-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10623-012-9617-2","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T15:23:51Z","timestamp":1561303431000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10623-012-9617-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,2,12]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,10]]}},"alternative-id":["9617"],"URL":"https:\/\/doi.org\/10.1007\/s10623-012-9617-2","relation":{},"ISSN":["0925-1022","1573-7586"],"issn-type":[{"value":"0925-1022","type":"print"},{"value":"1573-7586","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,2,12]]}}}