{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T12:51:07Z","timestamp":1768913467027,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":42,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642383472","type":"print"},{"value":"9783642383489","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38348-9_13","type":"book-chapter","created":{"date-parts":[[2013,5,9]],"date-time":"2013-05-09T00:46:38Z","timestamp":1368060398000},"page":"211-227","source":"Crossref","is-referenced-by-count":26,"title":["Graph-Theoretic Algorithms for the \u201cIsomorphism of Polynomials\u201d Problem"],"prefix":"10.1007","author":[{"given":"Charles","family":"Bouillaguet","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pierre-Alain","family":"Fouque","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Amandine","family":"V\u00e9ber","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"13_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, M., Saxena, N.: Equivalence of f-algebras and cubic forms. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol.\u00a03884, pp. 115\u2013126. Springer, Heidelberg (2006)","DOI":"10.1007\/11672142_8"},{"key":"13_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"394","DOI":"10.1007\/978-3-642-15369-3_30","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"N. Alon","year":"2010","unstructured":"Alon, N., Blais, E.: Testing boolean function isomorphism. In: Serna, M.J., Shaltiel, R., Jansen, K., Rolim, J.D.P. (eds.) APPROX 2010. LNCS, vol.\u00a06302, pp. 394\u2013405. Springer, Heidelberg (2010)"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Babai, L., Kucera, L.: Canonical labelling of graphs in linear average time. In: FOCS, pp. 39\u201346. IEEE Computer Society (1979)","DOI":"10.1109\/SFCS.1979.8"},{"key":"13_CR4","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. International Conference on Polynomial System Solving (ICPSS), pp. 71\u201375 (2004)"},{"key":"13_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/978-3-540-68164-9_10","volume-title":"Progress in Cryptology \u2013 AFRICACRYPT 2008","author":"L. Bettale","year":"2008","unstructured":"Bettale, L., Faug\u00e8re, J.-C., Perret, L.: Cryptanalysis of the trms signature scheme of pkc\u201905. In: Vaudenay, S. (ed.) AFRICACRYPT 2008. LNCS, vol.\u00a05023, pp. 143\u2013155. Springer, Heidelberg (2008)"},{"key":"13_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/978-3-540-40061-5_21","volume-title":"Advances in Cryptology - ASIACRYPT 2003","author":"O. Billet","year":"2003","unstructured":"Billet, O., Gilbert, H.: A traceable block cipher. In: Laih, C.-S. (ed.) ASIACRYPT 2003. LNCS, vol.\u00a02894, pp. 331\u2013346. Springer, Heidelberg (2003)"},{"key":"13_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/3-540-39200-9_3","volume-title":"Advances in Cryptology \u2013 EUROCRPYT 2003","author":"A. Biryukov","year":"2003","unstructured":"Biryukov, A., Canni\u00e8re, C.D., Braeken, A., Preneel, B.: A toolbox for cryptanalysis: Linear and affine equivalence algorithms. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol.\u00a02656, pp. 33\u201350. Springer, Heidelberg (2003)"},{"issue":"3\/4","key":"13_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.J., Playoust, C.: The Magma Algebra System I: The User Language. J. Symb. Comput.\u00a024(3\/4), 235\u2013265 (1997)","journal-title":"J. Symb. Comput."},{"key":"13_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1007\/978-3-642-19379-8_29","volume-title":"Public Key Cryptography \u2013 PKC 2011","author":"C. Bouillaguet","year":"2011","unstructured":"Bouillaguet, C., Faug\u00e8re, J.-C., Fouque, P.-A., Perret, L.: Practical cryptanalysis of the identification scheme based on the isomorphism of polynomial with one secret problem. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol.\u00a06571, pp. 473\u2013493. Springer, Heidelberg (2011)"},{"key":"13_CR10","doi-asserted-by":"crossref","unstructured":"Bouillaguet, C., Fouque, P.A., V\u00e9ber, A.: Graph-theoretic algorithms for the \u201cisomorphism of polynomials\u201d problem. Cryptology ePrint Archive, Report 2012\/607 (2012), http:\/\/eprint.iacr.org\/","DOI":"10.1007\/978-3-642-38348-9_13"},{"key":"13_CR11","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","year":"2005","unstructured":"Cramer, R. (ed.): EUROCRYPT 2005. LNCS, vol.\u00a03494. Springer, Heidelberg (2005)"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Daemen, J.: Limitations of the even-mansour construction. In: [25], pp. 495\u2013498","DOI":"10.1007\/3-540-57332-1_46"},{"key":"13_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1007\/978-3-540-71677-8_18","volume-title":"Public Key Cryptography \u2013 PKC 2007","author":"J. Ding","year":"2007","unstructured":"Ding, J., Wolf, C., Yang, B.-Y.: \u2113-Invertible cycles for multivariate quadratic public key cryptography. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol.\u00a04450, pp. 266\u2013281. Springer, Heidelberg (2007)"},{"key":"13_CR14","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.\u00a04622, pp. 1\u201312. Springer, Heidelberg (2007)"},{"key":"13_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1007\/11787006_14","volume-title":"Automata, Languages and Programming","author":"V. Dubois","year":"2006","unstructured":"Dubois, V., Granboulan, L., Stern, J.: An efficient provable distinguisher for hfe. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol.\u00a04052, pp. 156\u2013167. Springer, Heidelberg (2006)"},{"key":"13_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/978-3-642-29011-4_21","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","author":"O. Dunkelman","year":"2012","unstructured":"Dunkelman, O., Keller, N., Shamir, A.: Minimalism in cryptography: The even-mansour scheme revisited. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol.\u00a07237, pp. 336\u2013354. Springer, Heidelberg (2012)"},{"key":"13_CR17","doi-asserted-by":"crossref","unstructured":"Even, S., Mansour, Y.: A construction of a cioher from a single pseudorandom permutation. In: [25], pp. 210\u2013224","DOI":"10.1007\/3-540-57332-1_17"},{"key":"13_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/978-3-642-14712-8_15","volume-title":"Progress in Cryptology \u2013 LATINCRYPT 2010","author":"J.-C. Faug\u00e8re","year":"2010","unstructured":"Faug\u00e8re, J.-C., Joux, A., Perret, L., Treger, J.: Cryptanalysis of the hidden matrix cryptosystem. In: Abdalla, M., Barreto, P.S.L.M. (eds.) LATINCRYPT 2010. LNCS, vol.\u00a06212, pp. 241\u2013254. Springer, Heidelberg (2010)"},{"key":"13_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1007\/11761679_3","volume-title":"Advances in Cryptology - EUROCRYPT 2006","author":"J.-C. Faug\u00e8re","year":"2006","unstructured":"Faug\u00e8re, J.-C., Perret, L.: Polynomial Equivalence Problems: Algorithmic and Theoretical Aspects. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol.\u00a04004, pp. 30\u201347. Springer, Heidelberg (2006)"},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"Fouque, P.A., Granboulan, L., Stern, J.: Differential cryptanalysis for multivariate schemes. In: [11], pp. 341\u2013353","DOI":"10.1007\/11426639_20"},{"key":"13_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-78440-1_1","volume-title":"Public Key Cryptography \u2013 PKC 2008","author":"P.-A. Fouque","year":"2008","unstructured":"Fouque, P.-A., Macario-Rat, G., Perret, L., Stern, J.: Total break of the \u2113-ic signature scheme. In: Cramer, R. (ed.) PKC 2008. LNCS, vol.\u00a04939, pp. 1\u201317. Springer, Heidelberg (2008)"},{"key":"13_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/978-3-540-78967-3_2","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2008","author":"P.-A. Fouque","year":"2008","unstructured":"Fouque, P.-A., Macario-Rat, G., Stern, J.: Key Recovery on Hidden Monomial Multivariate Schemes. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol.\u00a04965, pp. 19\u201330. Springer, Heidelberg (2008)"},{"issue":"1","key":"13_CR23","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/s10207-003-0025-5","volume":"2","author":"W. Geiselmann","year":"2003","unstructured":"Geiselmann, W., Meier, W., Steinwandt, R.: An Attack on the Isomorphisms of Polynomials Problem with One Secret. Int. J. Inf. Sec.\u00a02(1), 59\u201364 (2003)","journal-title":"Int. J. Inf. Sec."},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity and a methodology of cryptographic protocol design (extended abstract). In: FOCS, pp. 174\u2013187. IEEE (1986)","DOI":"10.1109\/SFCS.1986.47"},{"key":"13_CR25","series-title":"Lecture Notes in Computer Science","volume-title":"Advances in Cryptology - ASIACRYPT \u201991","year":"1993","unstructured":"Matsumoto, T., Imai, H., Rivest, R.L. (eds.): ASIACRYPT 1991. LNCS, vol.\u00a0739. Springer, Heidelberg (1993)"},{"key":"13_CR26","doi-asserted-by":"crossref","unstructured":"Joux, A., Kunz-Jacques, S., Muller, F., Ricordel, P.M.: Cryptanalysis of the tractable rational map cryptosystem. In: [40], pp. 258\u2013274","DOI":"10.1007\/978-3-540-30580-4_18"},{"key":"13_CR27","doi-asserted-by":"crossref","unstructured":"Kayal, N.: Efficient algorithms for some special cases of the polynomial equivalence problem. In: Randall, D. (ed.) SODA, pp. 1409\u20131421. SIAM (2011)","DOI":"10.1137\/1.9781611973082.108"},{"key":"13_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)"},{"key":"13_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1007\/3-540-49649-1_4","volume-title":"Advances in Cryptology - ASIACRYPT\u201998","author":"J. Patarin","year":"1998","unstructured":"Patarin, J., Goubin, L., Courtois, N.T.: C\u2009\u2212\u2009+\u2009* and HM: Variations around two schemes of T. Matsumoto and H. Imai. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol.\u00a01514, pp. 35\u201350. Springer, Heidelberg (1998)"},{"key":"13_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"184","DOI":"10.1007\/BFb0054126","volume-title":"Advances in Cryptology - EUROCRYPT \u201998","author":"J. Patarin","year":"1998","unstructured":"Patarin, J., Goubin, L., Courtois, N.T.: Improved Algorithms for Isomorphisms of Polynomials. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol.\u00a01403, pp. 184\u2013200. Springer, Heidelberg (1998)"},{"key":"13_CR31","doi-asserted-by":"crossref","unstructured":"Patarin, J., Goubin, L., Courtois, N.: Improved Algorithms for Isomorphisms of Polynomials \u2013 Extended Version (1998), http:\/\/minrank.org\/ip6long.pdf","DOI":"10.1007\/BFb0054126"},{"key":"13_CR32","doi-asserted-by":"crossref","unstructured":"Perret, L.: A Fast Cryptanalysis of the Isomorphism of Polynomials with One Secret Problem. In: [11], pp. 354\u2013370","DOI":"10.1007\/11426639_21"},{"key":"13_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/3-540-49264-X_26","volume-title":"Advances in Cryptology - EUROCRYPT \u201995","author":"D. Pointcheval","year":"1995","unstructured":"Pointcheval, D.: A new identification scheme based on the perceptrons problem. In: Guillou, L.C., Quisquater, J.-J. (eds.) EUROCRYPT 1995. LNCS, vol.\u00a0921, pp. 319\u2013328. Springer, Heidelberg (1995)"},{"key":"13_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1007\/978-3-642-30057-8_11","volume-title":"Public Key Cryptography \u2013 PKC 2012","author":"K. Sakumoto","year":"2012","unstructured":"Sakumoto, K.: Public-key identification schemes based on multivariate cubic polynomials. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol.\u00a07293, pp. 172\u2013189. Springer, Heidelberg (2012)"},{"key":"13_CR35","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"706","DOI":"10.1007\/978-3-642-22792-9_40","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"K. Sakumoto","year":"2011","unstructured":"Sakumoto, K., Shirai, T., Hiwatari, H.: Public-key identification schemes based on multivariate quadratic polynomials. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol.\u00a06841, pp. 706\u2013723. Springer, Heidelberg (2011)"},{"key":"13_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1007\/0-387-34805-0_54","volume-title":"Advances in Cryptology - CRYPTO \u201989","author":"A. Shamir","year":"1990","unstructured":"Shamir, A.: An efficient identification scheme based on permuted kernels (extended abstract). In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol.\u00a0435, pp. 606\u2013609. Springer, Heidelberg (1990)"},{"key":"13_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1007\/3-540-48329-2_2","volume-title":"Advances in Cryptology - CRYPTO \u201993","author":"J. Stern","year":"1994","unstructured":"Stern, J.: A new identification scheme based on syndrome decoding. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol.\u00a0773, pp. 13\u201321. Springer, Heidelberg (1994)"},{"key":"13_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1007\/3-540-48658-5_18","volume-title":"Advances in Cryptology - CRYPTO \u201994","author":"J. Stern","year":"1994","unstructured":"Stern, J.: Designing identification schemes with keys of short size. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol.\u00a0839, pp. 164\u2013173. Springer, Heidelberg (1994)"},{"key":"13_CR39","unstructured":"Vaudenay, S.: A Classical Introduction to Cryptography: Applications for Communications Security. Springer-Verlag New York, Inc., Secaucus (2005)"},{"key":"13_CR40","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":"13_CR41","doi-asserted-by":"crossref","unstructured":"Wang, L.C., Hu, Y.H., Lai, F., Yen Chou, C., Yang, B.Y.: Tractable rational map signature. In: [40], pp. 244\u2013257","DOI":"10.1007\/978-3-540-30580-4_17"},{"key":"13_CR42","doi-asserted-by":"crossref","first-page":"575","DOI":"10.1007\/BF02100618","volume":"108","author":"H. Wilf","year":"1992","unstructured":"Wilf, H., Zeilberger, D.: An algorithmic proof theory for hypergeometric (ordinary and \u201cq\u201d) multisum\/integral identities. Inventiones Mathematicae\u00a0108, 575\u2013633 (1992), 10.1007\/BF02100618","journal-title":"Inventiones Mathematicae"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2013"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38348-9_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,30]],"date-time":"2025-04-30T09:17:48Z","timestamp":1746004668000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38348-9_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642383472","9783642383489"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38348-9_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}