{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,10]],"date-time":"2025-11-10T13:38:16Z","timestamp":1762781896211,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662464465"},{"type":"electronic","value":"9783662464472"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-46447-2_7","type":"book-chapter","created":{"date-parts":[[2015,3,16]],"date-time":"2015-03-16T01:21:25Z","timestamp":1426468885000},"page":"150-174","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":15,"title":["A Polynomial-Time Key-Recovery Attack on MQQ Cryptosystems"],"prefix":"10.1007","author":[{"given":"Jean-Charles","family":"Faug\u00e8re","sequence":"first","affiliation":[]},{"given":"Danilo","family":"Gligoroski","sequence":"additional","affiliation":[]},{"given":"Ludovic","family":"Perret","sequence":"additional","affiliation":[]},{"given":"Simona","family":"Samardjiska","sequence":"additional","affiliation":[]},{"given":"Enrico","family":"Thomae","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,3,17]]},"reference":[{"key":"7_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-55220-5_1","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"R Barbulescu","year":"2014","unstructured":"Barbulescu, R., Gaudry, P., Joux, A., Thom\u00e9, E.: A heuristic quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 1\u201316. Springer, Heidelberg (2014)"},{"key":"7_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: Proc. of International Conference on Polynomial System Solving (ICPSS), pp. 71\u201375 (2004)"},{"key":"7_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: Proc. of MEGA 2005, Eighth Int. Symposium on Effective Methods in Algebraic Geometry (2005)"},{"key":"7_CR4","unstructured":"Bernstein, D.J., Lange, T. (eds.): eBACS: ECRYPT Benchmarking of Cryptographic Systems (2014). \n                      http:\/\/bench.cr.yp.to"},{"key":"7_CR5","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. 6571, pp. 441\u2013458. Springer, Heidelberg (2011)"},{"issue":"1","key":"7_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10623-012-9617-2","volume":"69","author":"L Bettale","year":"2013","unstructured":"Bettale, L., Faugre, J.C., Perret, L.: Cryptanalysis of HFE, multi-HFE and variants for odd and even characteristic. Designs, Codes and Cryptography 69(1), 1\u201352 (2013)","journal-title":"Designs, Codes and Cryptography"},{"key":"7_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/11832072_23","volume-title":"Security and Cryptography for Networks","author":"O Billet","year":"2006","unstructured":"Billet, O., Gilbert, H.: Cryptanalysis of rainbow. In: De Prisco, R., Yung, M. (eds.) SCN 2006. LNCS, vol. 4116, pp. 336\u2013347. Springer, Heidelberg (2006)"},{"issue":"3\u20134","key":"7_CR8","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1006\/jsco.1996.0125","volume":"24","author":"W Bosma","year":"1997","unstructured":"Bosma, W., Cannon, J., Playoust, C.: The Magma Algebra System. I. The User Language. J. Symbolic Comput. 24(3\u20134), 235\u2013265 (1997). Computational algebra and number theory (London, 1993)","journal-title":"J. Symbolic Comput."},{"key":"7_CR9","unstructured":"Bouillaguet, C.: Etudes d\u2019hypoth\u00e8ses algorithmiques et attaques de primitives cryptographiques. Ph.D. thesis, Paris Diderot, France (2011)"},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"Buss, W., Frandsen, G., Shallit, J.: The computational complexity of some problems of linear algebra. Journal of Computer and System Sciences (1999)","DOI":"10.1006\/jcss.1998.1608"},{"key":"7_CR11","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. 1976, p. 44. Springer, Heidelberg (2000)"},{"key":"7_CR12","unstructured":"Courtois, N., Goubin, L., Patarin, J.: Sflash, a fast asymmetric signature scheme for low-cost smartcards - primitive specification and supporting documentation. \n                      https:\/\/www.cosic.esat.kuleuven.ac.be\/nessie\/workshop\/"},{"key":"7_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1007\/3-540-45682-1_24","volume-title":"Advances in Cryptology - ASIACRYPT 2001","author":"NT Courtois","year":"2001","unstructured":"Courtois, N.T.: Efficient zero-knowledge authentication based on a linear algebra problem minrank. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, p. 402. Springer, Heidelberg (2001)"},{"key":"7_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/978-3-540-68914-0_15","volume-title":"Applied Cryptography and Network Security","author":"J Ding","year":"2008","unstructured":"Ding, J., Yang, B.-Y., Chen, C.-H.O., Chen, M.-S., Cheng, C.-M.: New differential-algebraic attacks and reparametrization of rainbow. In: Bellovin, S.M., Gennaro, R., Keromytis, A.D., Yung, M. (eds.) ACNS 2008. LNCS, vol. 5037, pp. 242\u2013257. Springer, Heidelberg (2008)"},{"key":"7_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-74143-5_1","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"V Dubois","year":"2007","unstructured":"Dubois, V., Fouque, P.-A., Shamir, A., Stern, J.: Practical cryptanalysis of SFLASH. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 1\u201312. Springer, Heidelberg (2007)"},{"key":"7_CR16","unstructured":"ETSI: 2nd Quantum-Safe Crypto Workshop in partnership with the IQC. \n                      http:\/\/www.etsi.org\/news-events\/events\/770-etsi-crypto-workshop-2014\n                      \n                     (Retrieved: September 2014)"},{"issue":"4","key":"7_CR17","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/j.jsc.2010.10.014","volume":"46","author":"JC Faug\u00e8re","year":"2011","unstructured":"Faug\u00e8re, J.C., Din, M.S.E., Spaenlehauer, P.J.: Gr\u00f6bner bases of bihomogeneous ideals generated by polynomials of bidegree (1, 1): Algorithms and complexity. J. Symb. Comput. 46(4), 406\u2013437 (2011)","journal-title":"J. Symb. Comput."},{"key":"7_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-540-85174-5_16","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"J-C Faug\u00e8re","year":"2008","unstructured":"Faug\u00e8re, J.-C., Levy-dit-Vehel, F., Perret, L.: Cryptanalysis of minrank. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 280\u2013296. Springer, Heidelberg (2008)"},{"key":"7_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-642-17619-7_13","volume-title":"Cryptology and Network Security","author":"J-C Faug\u00e8re","year":"2010","unstructured":"Faug\u00e8re, J.-C., \u00d8deg\u00e5rd, R.S., Perret, L., Gligoroski, D.: Analysis of the MQQ public key cryptosystem. In: Heng, S.-H., Wright, R.N., Goi, B.-M. (eds.) CANS 2010. LNCS, vol. 6467, pp. 169\u2013183. Springer, Heidelberg (2010)"},{"key":"7_CR20","unstructured":"Gantmacher, F.: The Theory of Matrices, Vol. 1. Chelsea (1959)"},{"key":"7_CR21","unstructured":"Gligoroski, D., Markovski, S., Knapskog, S.J.: Multivariate quadratic trapdoor functions based on multivariate quadratic quasigroups. In: Proc. of the American Conference on Applied Mathematics, MATH, pp. 44\u201349. World Scientific and Engineering Academy and Society (WSEAS) (2008)"},{"key":"7_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/978-3-642-32298-3_13","volume-title":"Trusted Systems","author":"D Gligoroski","year":"2012","unstructured":"Gligoroski, D., \u00d8deg\u00e5rd, R.S., Jensen, R.E., Perret, L., Faug\u00e8re, J.-C., Knapskog, S.J., Markovski, S.: MQQ-SIG. In: Chen, L., Yung, M., Zhu, L. (eds.) INTRUST 2011. LNCS, vol. 7222, pp. 184\u2013203. Springer, Heidelberg (2012)"},{"key":"7_CR23","unstructured":"Gligoroski, D., Samardjiska, S.: The Multivariate Probabilistic Encryption Scheme MQQ-ENC. In: SCC (2012)"},{"key":"7_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"108","DOI":"10.1007\/3-540-16776-5_713","volume-title":"Algebraic Algorithms and Error-Correcting Codes","author":"H Imai","year":"1985","unstructured":"Imai, H., Matsumoto, T.: Algebraic methods for constructing asymmetric cryptosystems. In: Calmet, J. (ed.) Algebraic Algorithms and Error-Correcting Codes. LNCS, vol. 229, pp. 108\u2013119. Springer, Heidelberg (1985)"},{"key":"7_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/978-3-540-79499-8_31","volume-title":"Information Security and Cryptology","author":"X Jiang","year":"2008","unstructured":"Jiang, X., Ding, J., Hu, L.: Kipnis-shamir attack on HFE revisited. In: Pei, D., Yung, M., Lin, D., Wu, C. (eds.) Inscrypt 2007. LNCS, vol. 4990, pp. 399\u2013411. Springer, Heidelberg (2008)"},{"key":"7_CR26","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. 1592, p. 206. Springer, Heidelberg (1999)"},{"key":"7_CR27","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. 1666, p. 19. Springer, Heidelberg (1999)"},{"issue":"2","key":"7_CR28","doi-asserted-by":"publisher","first-page":"152","DOI":"10.2307\/2317262","volume":"76","author":"J MacWilliams","year":"1969","unstructured":"MacWilliams, J.: Orthogonal matrices over finite fields. Orthogonal matrices over finite fields. The American Mathematical Monthly 76(2), 152\u2013164 (1969)","journal-title":"The American Mathematical Monthly"},{"issue":"5","key":"7_CR29","doi-asserted-by":"publisher","first-page":"2207","DOI":"10.1080\/00927879908826559","volume":"27","author":"TT Moh","year":"1999","unstructured":"Moh, T.T.: A public key system with signature and master key functions. Communications in Algebra 27(5), 2207\u20132222 (1999)","journal-title":"Communications in Algebra"},{"key":"7_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"392","DOI":"10.1007\/978-3-642-10433-6_26","volume-title":"Cryptology and Network Security","author":"MSE Mohamed","year":"2009","unstructured":"Mohamed, M.S.E., Ding, J., Buchmann, J., Werner, F.: Algebraic attack on the MQQ public key cryptosystem. In: Garay, J.A., Miyaji, A., Otsuka, A. (eds.) CANS 2009. LNCS, vol. 5888, pp. 392\u2013401. Springer, Heidelberg (2009)"},{"key":"7_CR31","unstructured":"NESSIE: New european schemes for signatures, integrity, and encryption (2003). \n                      https:\/\/www.cosic.esat.kuleuven.be\/nessie\/\n                      \n                     (Retrieved: September 2014)"},{"key":"7_CR32","unstructured":"NIST: Workshop on Cybersecurity in a Post-Quantum World. \n                      http:\/\/www.nist.gov\/itl\/csd\/ct\/post-quantum-crypto-workshop-2015.cfm\n                      \n                     (Retrieved: September 2014)"},{"key":"7_CR33","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. 1070, pp. 33\u201348. Springer, Heidelberg (1996)"},{"key":"7_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1007\/11426639_21","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"L Perret","year":"2005","unstructured":"Perret, L.: A fast cryptanalysis of the isomorphism of polynomials with one secret problem. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 354\u2013370. Springer, Heidelberg (2005)"},{"issue":"3","key":"7_CR35","first-page":"146","volume":"7","author":"S Samardjiska","year":"2012","unstructured":"Samardjiska, S., Chen, Y., Gligoroski, D.: Algorithms for construction of Multivariate Quadratic Quasigroups (MQQs) and their parastrophe operations in arbitrary galois fields. J. Inf. Assurance and Security 7(3), 146\u2013172 (2012)","journal-title":"J. Inf. Assurance and Security"},{"key":"7_CR36","unstructured":"Thomae, E.: About the Security of Multivariate Quadratic Public Key Schemes. Ph.D. thesis, Ruhr-University Bochum, Germany (2013)"},{"key":"7_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"188","DOI":"10.1007\/978-3-642-31410-0_12","volume-title":"Progress in Cryptology - AFRICACRYPT 2012","author":"E Thomae","year":"2012","unstructured":"Thomae, E., Wolf, C.: Cryptanalysis of enhanced TTS, STS and all its variants, or: why cross-terms are important. In: Mitrokotsa, A., Vaudenay, S. (eds.) AFRICACRYPT 2012. LNCS, vol. 7374, pp. 188\u2013202. Springer, Heidelberg (2012)"},{"issue":"3","key":"7_CR38","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1007\/s10623-006-0015-5","volume":"40","author":"C Wolf","year":"2006","unstructured":"Wolf, C., Braeken, A., Preneel, B.: On the security of stepwise triangular systems. Designs, Codes and Cryptography 40(3), 285\u2013302 (2006)","journal-title":"Designs, Codes and Cryptography"},{"key":"7_CR39","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\n                      \n                        \n                      \n                      $$^{*}$$\n                    , and variations. In: Dawson, E., Vaudenay, S. (eds.) Mycrypt 2005. LNCS, vol. 3715, pp. 33\u201349. Springer, Heidelberg (2005)"},{"key":"7_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/978-3-540-30580-4_19","volume-title":"Public Key Cryptography - PKC 2005","author":"C Wolf","year":"2005","unstructured":"Wolf, C., Preneel, B.: Large superfluous keys in multivariate quadratic asymmetric systems. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 275\u2013287. Springer, Heidelberg (2005)"},{"key":"7_CR41","doi-asserted-by":"publisher","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. Journal of Mathematical Cryptology 4, 375\u2013415 (2011)","journal-title":"Journal of Mathematical Cryptology"},{"key":"7_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1007\/978-3-540-28632-5_27","volume-title":"Cryptographic Hardware and Embedded Systems - CHES 2004","author":"B-Y Yang","year":"2004","unstructured":"Yang, B.-Y., Chen, J.-M., Chen, Y.-H.: TTS: high-speed signatures on a low-cost smart card. In: Joye, M., Quisquater, J.-J. (eds.) CHES 2004. LNCS, vol. 3156, pp. 371\u2013385. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Public-Key Cryptography -- PKC 2015"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-46447-2_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,29]],"date-time":"2019-05-29T11:42:37Z","timestamp":1559130157000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-46447-2_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662464465","9783662464472"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-46447-2_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"17 March 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}