{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,10]],"date-time":"2026-11-10T21:41:31Z","timestamp":1794346891624,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":46,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540716761","type":"print"},{"value":"9783540716778","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-71677-8_18","type":"book-chapter","created":{"date-parts":[[2007,6,20]],"date-time":"2007-06-20T14:05:58Z","timestamp":1182348358000},"page":"266-281","source":"Crossref","is-referenced-by-count":29,"title":["\u2113-Invertible Cycles for $\\mathcal{M}$ ultivariate $\\mathcal{Q}$ uadratic ( ${\\mathcal{MQ}}$ ) Public Key Cryptography"],"prefix":"10.1007","author":[{"given":"Jintai","family":"Ding","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christopher","family":"Wolf","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bo-Yin","family":"Yang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"18_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/3-540-36288-6_20","volume-title":"Public Key Cryptography - PKC 2003","author":"M.-L. Akkar","year":"2002","unstructured":"Akkar, M.-L., Courtois, N.T., Duteuil, R., Goubin, L.: A fast and secure implementation of SFlash. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol.\u00a02567, pp. 267\u2013278. Springer, Heidelberg (2002)"},{"key":"18_CR2","series-title":"Lecture Notes in Computer Science","volume-title":"Applied Cryptography and Network Security","year":"2005","unstructured":"Ioannidis, J., Keromytis, A.D., Yung, M. (eds.): ACNS 2005. LNCS, vol.\u00a03531. Springer, Heidelberg (2005)"},{"key":"18_CR3","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 appeared as INRIA report RR-5049)"},{"key":"18_CR4","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":"18_CR5","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":"18_CR6","unstructured":"Courtois, N., Goubin, L., Patarin, J.: Quartz: Primitive specification (second revised version). Submissions, Quartz (October 2001), https:\/\/www.cosic.esat.kuleuven.be\/nessie"},{"key":"18_CR7","unstructured":"Courtois, N., Goubin, L., Patarin, J.: Sflash: Primitive specification (second revised version). Submissions, Sflash (2002), https:\/\/www.cosic.esat.kuleuven.be\/nessie"},{"key":"18_CR8","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":"18_CR9","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology - CRYPTO \u201993","year":"1994","unstructured":"Stinson, D.R. (ed.): CRYPTO 1993. LNCS, vol.\u00a0773. Springer, Heidelberg (1994)"},{"key":"18_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1007\/3-540-48329-2_37","volume-title":"Advances in Cryptology - CRYPTO \u201993","author":"D. Coppersmith","year":"1994","unstructured":"Coppersmith, D., Stern, J., Vaudenay, S.: Attacks on the birational permutation signature schemes. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol.\u00a0773, pp. 435\u2013443. Springer, Heidelberg (1994)"},{"key":"18_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/11745853_19","volume-title":"Public Key Cryptography - PKC 2006","author":"J. Ding","year":"2006","unstructured":"Ding, J., Gower, J.E.: Inoculating multivariate schemes against differential attacks. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T.G. (eds.) PKC 2006. LNCS, vol.\u00a03958, pp. 290\u2013301. Springer, Heidelberg (2006), http:\/\/eprint.iacr.org\/2005\/255"},{"key":"18_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1007\/11586821_18","volume-title":"Cryptography and Coding","author":"J. Ding","year":"2005","unstructured":"Ding, J., Gower, J.E., Schmidt, D., Wolf, C., Yin, Z.: Complexity Estimates for the F 4 Attack on the Perturbed Matsumoto-Imai Cryptosystem. In: Smart, N.P. (ed.) Cryptography and Coding 2005. LNCS, vol.\u00a03796, pp. 262\u2013277. Springer, Heidelberg (2005)"},{"key":"18_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"305","DOI":"10.1007\/978-3-540-24632-9_22","volume-title":"Public Key Cryptography \u2013 PKC 2004","author":"J. Ding","year":"2004","unstructured":"Ding, J.: A new variant of the Matsumoto-Imai cryptosystem through perturbation. In: Bao, F., Deng, R., Zhou, J. (eds.) PKC 2004. LNCS, vol.\u00a02947, pp. 305\u2013318. Springer, Heidelberg (2004)"},{"key":"18_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"288","DOI":"10.1007\/978-3-540-30580-4_20","volume-title":"Public Key Cryptography - PKC 2005","author":"J. Ding","year":"2005","unstructured":"Ding, J., Schmidt, D.: Cryptanalysis of HFEv and internal perturbation of HFE. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol.\u00a03386, pp. 288\u2013301. Springer, Heidelberg (2005)"},{"key":"18_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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.D., Yung, M. (eds.) ACNS 2005. LNCS, vol.\u00a03531, pp. 164\u2013175. Springer, Heidelberg (2005)"},{"key":"18_CR16","doi-asserted-by":"publisher","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 (F 4). Journal of Pure and Applied Algebra\u00a0139, 61\u201388 (1999)","journal-title":"Journal of Pure and Applied Algebra"},{"key":"18_CR17","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1145\/780506.780516","volume-title":"International Symposium on Symbolic and Algebraic Computation \u2014 ISSAC\u00a02002","author":"J.-C. Faug\u00e8re","year":"2002","unstructured":"Faug\u00e8re, J.-C.: A new efficient algorithm for computing Gr\u00f6bner bases without reduction to zero (F 5). In: International Symposium on Symbolic and Algebraic Computation \u2014 ISSAC\u00a02002, July 2002, pp. 75\u201383. ACM Press, New York (2002)"},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"340","DOI":"10.1007\/3-540-39799-X_24","volume-title":"Advances in Cryptology","author":"H. Fell","year":"1986","unstructured":"Fell, H., Diffie, W.: Analysis of a public key approach based on polynomial substitution. In: Williams, H.C. (ed.) CRYPTO 1985. LNCS, vol.\u00a0218, pp. 340\u2013349. Springer, Heidelberg (1986)"},{"key":"18_CR19","unstructured":"Felke, P.: On the affine transformations of HFE-cryptosystems and systems with branches. Cryptology ePrint Archive, Report 2004\/367 (2004), http:\/\/eprint.iacr.org\/2004\/367 , version from 2004-12-17"},{"key":"18_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/11426639_20","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"P.-A. Fouque","year":"2005","unstructured":"Fouque, P.-A., Granboulan, L., Stern, J.: Differential cryptanalysis for multivariate schemes. In: Cramer, R.J.F. (ed.) EUROCRYPT 2005. LNCS, vol.\u00a03494, pp. 341\u2013353. Springer, Heidelberg (2005)"},{"key":"18_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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":"18_CR22","volume-title":"Algebraic curves. An introduction to algebraic geometry","author":"W. Fulton","year":"1989","unstructured":"Fulton, W.: Algebraic curves. An introduction to algebraic geometry (a Reprint of 1969 original in Advanced Book Classics). Addison-Wesley Publishing, Redwood City (1989)"},{"issue":"21","key":"18_CR23","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1049\/el:20020855","volume":"38","author":"P. Fitzpatrick","year":"2002","unstructured":"Fitzpatrick, P., Wolf, C.: Direct division in factor rings. Electronic Letters\u00a038(21), 1253\u20131254 (2002), Extended version: http:\/\/eprint.iacr.org\/2004\/353","journal-title":"Electronic Letters"},{"key":"18_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/3-540-44448-3_4","volume-title":"Advances in Cryptology - ASIACRYPT 2000","author":"L. Goubin","year":"2000","unstructured":"Goubin, L., Courtois, N.T.: Cryptanalysis of the TTM cryptosystem. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol.\u00a01976, pp. 44\u201357. Springer, Heidelberg (2000)"},{"key":"18_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"108","DOI":"10.1007\/3-540-16776-5_713","volume-title":"Algebraic Algorithms and Error-Correcting Codes","author":"H. Imai","year":"1986","unstructured":"Imai, H., Matsumoto, T.: Algebraic methods for constructing asymmetric cryptosystems. In: Calmet, J. (ed.) Algebraic Algorithms and Error-Correcting Codes. LNCS, vol.\u00a0229, pp. 108\u2013119. Springer, Heidelberg (1986)"},{"key":"18_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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":"18_CR27","unstructured":"Lop\u00e9z, J., Dahab, R.: An overview of elliptic curve cryptography. Technical report, Institute of Computing, State University of Campinas, Brazil, 22nd of May 2000. http:\/\/citeseer.nj.nec.com\/333066.html or http:\/\/www.dcc.unicamp.br\/ic-tr-ftp\/2000\/00-14.ps.gz"},{"key":"18_CR28","unstructured":"Computational Algebra Group, University of Sydney. The MAGMA Computational Algebra System for Algebra, Number Theory and Geometry. http:\/\/magma.maths.usyd.edu.au\/magma\/"},{"key":"18_CR29","unstructured":"NESSIE: New European Schemes for Signatures, Integrity, and Encryption. Information Society Technologies programme of the European commission (IST-1999-12324). http:\/\/www.cryptonessie.org\/ ."},{"key":"18_CR30","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":"18_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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":"18_CR32","unstructured":"Patarin, J.: The oil and vinegar signature scheme. Presented at the Dagstuhl Workshop on Cryptography, September 1997. transparencies (1997)"},{"key":"18_CR33","series-title":"Lecture Notes in Computer Science","volume-title":"Public Key Cryptography - PKC 2005","year":"2005","unstructured":"Vaudenay, S. (ed.): PKC 2005. LNCS, vol.\u00a03386. Springer, Heidelberg (2005)"},{"key":"18_CR34","series-title":"Lecture Notes in Computer Science","volume-title":"Topics in Cryptology \u2013 CT-RSA 2006","year":"2006","unstructured":"Pointcheval, D. (ed.): CT-RSA 2006. LNCS, vol.\u00a03860. Springer, Heidelberg (2006)"},{"key":"18_CR35","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Advances in Cryptology - CRYPTO \u201993","author":"A. Shamir","year":"1994","unstructured":"Shamir, A.: Efficient signature schemes based on birational permutations. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol.\u00a0773, pp. 1\u201312. Springer, Heidelberg (1994)"},{"issue":"5","key":"18_CR36","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":"18_CR37","first-page":"1963","volume":"12","author":"S. Tsujii","year":"1986","unstructured":"Tsujii, S., Kurosawa, K., Itoh, T., Fujioka, A., Matsumoto, T.: A public key cryptosystem based on the difficulty of solving a system of nonlinear equations. ICICE Transactions (D) J69-D\u00a012, 1963\u20131970 (1986)","journal-title":"ICICE Transactions (D) J69-D"},{"key":"18_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1007\/978-3-540-30598-9_21","volume-title":"Security in Communication Networks","author":"C. Wolf","year":"2005","unstructured":"Wolf, C., Braeken, A., Preneel, B.: Efficient cryptanalysis of RSE(2)PKC and RSSE(2)PKC. In: Blundo, C., Cimato, S. (eds.) SCN 2004. LNCS, vol.\u00a03352, pp. 294\u2013309. Springer, Heidelberg (2005), http:\/\/eprint.iacr.org\/2004\/237"},{"key":"18_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"244","DOI":"10.1007\/978-3-540-30580-4_17","volume-title":"Public Key Cryptography - PKC 2005","author":"L.-C. Wang","year":"2005","unstructured":"Wang, L.-C., Hu, Y.-H., Lai, F., Chou, C.y., Yang, B.-Y.: Tractable rational map signature. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol.\u00a03386, pp. 244\u2013257. Springer, Heidelberg (2005)"},{"key":"18_CR40","unstructured":"Wolf, C., Preneel, B.: Asymmetric cryptography: Hidden Field Equations. In: Neittaanm\u00e4ki, P., Rossi, T., Korotov, S., O\u00f1ate, E., P\u00e9riaux, J., Kn\u00f6rzer, D. (eds.) European Congress on Computational Methods in Applied Sciences and Engineering\u00a02004, Jyv\u00e4skyl\u00e4 University (2004), Extended version: http:\/\/eprint.iacr.org\/2004\/072\/"},{"key":"18_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/11554868_4","volume-title":"Progress in Cryptology \u2013 Mycrypt 2005","author":"C. Wolf","year":"2005","unstructured":"Wolf, C., Preneel, B.: Equivalent keys in HFE, C*, and variations. In: Dawson, E., Vaudenay, S. (eds.) Mycrypt 2005. LNCS, vol.\u00a03715, pp. 33\u201349. Springer, Heidelberg (2005), http:\/\/eprint.iacr.org\/2004\/360\/"},{"key":"18_CR42","unstructured":"Wolf, C., Preneel, B.: Taxonomy of public key schemes based on the problem of multivariate quadratic equations. Cryptology ePrint Archive, Report 2005\/077, 12th of May 2005. http:\/\/eprint.iacr.org\/2005\/077\/"},{"key":"18_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/11605805_9","volume-title":"Topics in Cryptology \u2013 CT-RSA 2006","author":"L.-C. Wang","year":"2006","unstructured":"Wang, L.-C., Yang, B.-Y., Hu, Y.-H., Lai, F.: A \u201cmedium-field\u201d multivariate public-key encryption scheme. In: Pointcheval, D. (ed.) CT-RSA 2006. LNCS, vol.\u00a03860, pp. 132\u2013149. Springer, Heidelberg (2006)"},{"key":"18_CR44","series-title":"Lecture Notes in Computer Science","first-page":"67","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":"18_CR45","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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)"},{"key":"18_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"518","DOI":"10.1007\/11506157_43","volume-title":"Information Security and Privacy","author":"B.-Y. Yang","year":"2005","unstructured":"Yang, B.-Y., Chen, J.-M.: Building secure tame-like multivariate public-key cryptosystems: The new TTS. In: Boyd, C., Gonz\u00e1lez Nieto, J.M. (eds.) ACISP 2005. LNCS, vol.\u00a03574, pp. 518\u2013531. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Public Key Cryptography \u2013 PKC 2007"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-71677-8_18.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,15]],"date-time":"2021-08-15T01:47:21Z","timestamp":1628992041000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-71677-8_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540716761","9783540716778"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-71677-8_18","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-540-71677-8","asserted-by":"object"}]},"subject":[]}}