{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T21:45:59Z","timestamp":1794433559336,"version":"4.9.1"},"publisher-location":"Berlin, Heidelberg","reference-count":52,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642349607","type":"print"},{"value":"9783642349614","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34961-4_28","type":"book-chapter","created":{"date-parts":[[2012,11,16]],"date-time":"2012-11-16T04:22:26Z","timestamp":1353039746000},"page":"451-466","source":"Crossref","is-referenced-by-count":37,"title":["On Polynomial Systems Arising from a Weil Descent"],"prefix":"10.1007","author":[{"given":"Christophe","family":"Petit","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jean-Jacques","family":"Quisquater","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"28_CR1","doi-asserted-by":"crossref","unstructured":"Leonard, M.A.: A subexponential algorithm for the discrete logarithm problem with applications to cryptography (abstract). In: FOCS, pp. 55\u201360. IEEE (1979)","DOI":"10.1109\/SFCS.1979.2"},{"key":"28_CR2","unstructured":"Leonard, M.A.: The function field sieve. In: Adleman, Huang [4], pp. 108\u2013121"},{"key":"28_CR3","unstructured":"Leonard, M.A., DeMarrais, J., Huang, M.-D.A.: A subexponential algorithm for discrete logarithms over the rational subgroup of the Jacobians of large genus hyperelliptic curves over finite fields. In: Adleman, Huang, [4] pp. 28\u201340"},{"key":"28_CR4","series-title":"Lecture Notes in Computer Science","volume-title":"Algorithmic Number Theory","year":"1994","unstructured":"Huang, M.-D.A., Adleman, L.M. (eds.): ANTS 1994. LNCS, vol.\u00a0877. Springer, Heidelberg (1994)"},{"issue":"1-2","key":"28_CR5","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1006\/inco.1998.2761","volume":"151","author":"L.M. Adleman","year":"1999","unstructured":"Adleman, L.M., Huang, M.-D.A.: Function field sieve method for discrete logarithms over finite fields. Inf. Comput.\u00a0151(1-2), 5\u201316 (1999)","journal-title":"Inf. Comput."},{"key":"28_CR6","unstructured":"Bardet, M.: Etude des syst\u00e8mes alg\u00e9briques surd\u00e9termin\u00e9s. Applications aux codes correcteurs et \u00e0 la cryptographie. PhD thesis, Universit\u00e9 Paris 6 (2004)"},{"key":"28_CR7","unstructured":"Bardet, M., Faug\u00e8re, J.-C., Salvy, B.: On the complexity of Gr\u00f6bner basis computation of semi-regular overdetermined algebraic equations. In: International Conference on Polynomial System Solving, ICPSS, pp. 71\u201375 (November 2004)"},{"key":"28_CR8","unstructured":"Bardet, M., Faug\u00e8re, J.-C., Salvy, B.: Asymptotic expansion of the degree of regularity for semi-regular systems of equations. In: Gianni, P. (ed.) The Effective Methods in Algebraic Geometry Conference, Mega 2005, pp. 1\u201314 (May 2005)"},{"issue":"3","key":"28_CR9","first-page":"177","volume":"3","author":"L. Bettale","year":"2010","unstructured":"Bettale, L., Faug\u00e8re, J.-C., Perret, L.: Hybrid approach for solving multivariate systems over finite fields. Journal of Mathematical Cryptology\u00a03(3), 177\u2013197 (2010)","journal-title":"Journal of Mathematical Cryptology"},{"key":"28_CR10","doi-asserted-by":"crossref","unstructured":"Bettale, L., Faug\u00e8re, J.-C., Perret, L.: Cryptanalysis of multivariate and odd-characteristic hfe variants. In: Catalano, et al. [14], pp. 441\u2013458","DOI":"10.1007\/978-3-642-19379-8_27"},{"key":"28_CR11","doi-asserted-by":"crossref","unstructured":"Bettale, L., Faug\u00e8re, J.-C., Perret, L.: Cryptanalysis of HFE, Multi-HFE and Variants for Odd and Even Characteristic. Des. Codes Cryptography, 1\u201342 (accepted, 2012)","DOI":"10.1007\/s10623-012-9617-2"},{"key":"28_CR12","doi-asserted-by":"crossref","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, et\u00a0al. [14], pp. 473\u2013493","DOI":"10.1007\/978-3-642-19379-8_29"},{"key":"28_CR13","unstructured":"Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, Universit\u00e4t Innsbruck (1965)"},{"key":"28_CR14","series-title":"Lecture Notes in Computer Science","first-page":"2011","volume-title":"Public Key Cryptography \u2013 PKC 2011","year":"2011","unstructured":"Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.): PKC 2011. LNCS, vol.\u00a06571, pp. 2011\u20132014. Springer, Heidelberg (2011)"},{"key":"28_CR15","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1145\/321662.321666","volume":"18","author":"G. Collins","year":"1971","unstructured":"Collins, G.: The calculation of multivariate polynomial resultants. Journal of the Association for Computing Machinery\u00a018, 515\u2013522 (1971)","journal-title":"Journal of the Association for Computing Machinery"},{"issue":"4","key":"28_CR16","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1109\/TIT.1984.1056941","volume":"30","author":"D. Coppersmith","year":"1984","unstructured":"Coppersmith, D.: Fast evaluation of logarithms in fields of characteristic two. IEEE Transactions on Information Theory\u00a030(4), 587\u2013593 (1984)","journal-title":"IEEE Transactions on Information Theory"},{"key":"28_CR17","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":"28_CR18","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. Courtois","year":"2000","unstructured":"Courtois, N., 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)"},{"key":"28_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2181-2","volume-title":"Ideals, Varieties, and Algorithms","author":"D. Cox","year":"1992","unstructured":"Cox, D., Little, J., O\u2019Shea, D.: Ideals, Varieties, and Algorithms, 1st edn. Springer, Heidelberg (1992)","edition":"1"},{"key":"28_CR20","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1112\/S0010437X10005075","volume":"147","author":"C. Diem","year":"2011","unstructured":"Diem, C.: On the discrete logarithm problem in elliptic curves. Compositio Mathematica\u00a0147, 75\u2013104 (2011)","journal-title":"Compositio Mathematica"},{"key":"28_CR21","doi-asserted-by":"crossref","unstructured":"Diem, C.: On the discrete logarithm problem in elliptic curves II (2011), http:\/\/www.math.uni-leipzig.de\/~diem\/preprints\/dlp-ell-curves-II.pdf","DOI":"10.1112\/S0010437X10005075"},{"key":"28_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"724","DOI":"10.1007\/978-3-642-22792-9_41","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"J. Ding","year":"2011","unstructured":"Ding, J., Hodges, T.J.: Inverting HFE Systems Is Quasi-Polynomial for All Fields. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol.\u00a06841, pp. 724\u2013742. Springer, Heidelberg (2011)"},{"key":"28_CR23","unstructured":"Ding, J., Kleinjung, T.: Degree of regularity for HFE-. IACR Cryptology ePrint Archiv, 2011:570 (2011)"},{"key":"28_CR24","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)"},{"issue":"1","key":"28_CR25","doi-asserted-by":"publisher","first-page":"83","DOI":"10.4064\/aa102-1-6","volume":"102","author":"A. Enge","year":"2002","unstructured":"Enge, A., Gaudry, P.: A general framework for subexponential discrete logarithm algorithms. Acta Arith.\u00a0102(1), 83\u2013103 (2002)","journal-title":"Acta Arith."},{"issue":"1-3","key":"28_CR26","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 (F4). Journal of Pure and Applied Algebra\u00a0139(1-3), 61\u201388 (1999)","journal-title":"Journal of Pure and Applied Algebra"},{"key":"28_CR27","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1145\/780506.780516","volume-title":"Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC 2002","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 (F5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC 2002, pp. 75\u201383. ACM, New York (2002)"},{"key":"28_CR28","doi-asserted-by":"crossref","unstructured":"Faug\u00e8re, J.-C., Din, M.S.E., Spaenlehauer, P.-J.: Computing loci of rank defects of linear matrices using gr\u00f6bner bases and applications to cryptology. In: ISSAC, pp. 257\u2013264 (2010)","DOI":"10.1145\/1837934.1837984"},{"issue":"4","key":"28_CR29","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1016\/j.jsc.2010.10.014","volume":"46","author":"J.-C. 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.\u00a046(4), 406\u2013437 (2011)","journal-title":"J. Symb. Comput."},{"key":"28_CR30","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":"28_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"279","DOI":"10.1007\/978-3-642-13190-5_14","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"J.-C. Faug\u00e8re","year":"2010","unstructured":"Faug\u00e8re, J.-C., Otmani, A., Perret, L., Tillich, J.-P.: Algebraic Cryptanalysis of McEliece Variants with Compact Keys. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol.\u00a06110, pp. 279\u2013298. Springer, Heidelberg (2010)"},{"key":"28_CR32","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":"28_CR33","unstructured":"Faug\u00e8re, J.-C., Perret, L., Petit, C., Renault, G.: New subexponential algorithms for factoring in $SL(2,{\\mathbb F}_{2^n})$ . Cryptology ePrint Archive, Report 2011\/598 (2011), http:\/\/eprint.iacr.org\/"},{"key":"28_CR34","doi-asserted-by":"crossref","unstructured":"Faug\u00e8re, J.-C., Perret, L., Petit, C., Renault, G.: Improving the complexity of index calculus algorithms in elliptic curves over binary fields. In: Pointcheval, Johansson [50], pp. 27\u201344","DOI":"10.1007\/978-3-642-29011-4_4"},{"issue":"257","key":"28_CR35","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1090\/S0025-5718-06-01900-4","volume":"76","author":"P. Gaudry","year":"2007","unstructured":"Gaudry, P., Thom\u00e9, E., Th\u00e9riault, N., Diem, C.: A double large prime variation for small genus hyperelliptic index calculus. Math. Comp.\u00a076(257), 475\u2013492 (electronic) (2007)","journal-title":"Math. Comp."},{"key":"28_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/3-540-45539-6_2","volume-title":"Advances in Cryptology - EUROCRYPT 2000","author":"P. Gaudry","year":"2000","unstructured":"Gaudry, P.: An Algorithm for Solving the Discrete Log Problem on Hyperelliptic Curves. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol.\u00a01807, pp. 19\u201334. Springer, Heidelberg (2000)"},{"issue":"12","key":"28_CR37","doi-asserted-by":"publisher","first-page":"1690","DOI":"10.1016\/j.jsc.2008.08.005","volume":"44","author":"P. Gaudry","year":"2009","unstructured":"Gaudry, P.: Index calculus for abelian varieties of small dimension and the elliptic curve discrete logarithm problem. J. Symb. Comput.\u00a044(12), 1690\u20131702 (2009)","journal-title":"J. Symb. Comput."},{"key":"28_CR38","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":"28_CR39","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1007\/11761679_16","volume-title":"Advances in Cryptology - EUROCRYPT 2006","author":"A. Joux","year":"2006","unstructured":"Joux, A., Lercier, R.: The Function Field Sieve in the Medium Prime Case. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol.\u00a04004, pp. 254\u2013270. Springer, Heidelberg (2006)"},{"key":"28_CR40","unstructured":"Joux, A., Vitse, V.: Elliptic Curve Discrete Logarithm Problem over Small Degree Extension Fields. Application to the static Diffie-Hellman problem on $E(\\mathbb{F}_{q^5})$ . Cryptology ePrint Archive, Report 2010\/157. Journal of Cryptology (2010), http:\/\/eprint.iacr.org\/"},{"key":"28_CR41","doi-asserted-by":"crossref","unstructured":"Joux, A., Vitse, V.: Cover and decomposition index calculus on elliptic curves made practical - application to a previously unreachable curve over $\\mathbb{F}_{p^6}$ . In: Pointcheval, Johansson [50], pp. 9\u201326","DOI":"10.1007\/978-3-642-29011-4_3"},{"key":"28_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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)"},{"key":"28_CR43","unstructured":"Kraitchik, M.: Th\u00e9orie des nombres. Gauthier-Villars (1922)"},{"key":"28_CR44","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":"28_CR45","doi-asserted-by":"crossref","unstructured":"Macaulay, F.S.: The algebraic theory of modular systems. Cambridge Mathematical Library, vol. XXXI. Cambridge University Press (1916)","DOI":"10.3792\/chmm\/1263317740"},{"key":"28_CR46","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1112\/plms\/s2-26.1.531","volume":"26","author":"F.S. Macaulay","year":"1927","unstructured":"Macaulay, F.S.: Some properties of enumeration in the theory of modular systems. Proc. London Math. Soc.\u00a026, 531\u2013555 (1927)","journal-title":"Proc. London Math. Soc."},{"key":"28_CR47","unstructured":"National Institute of Standards and Technology. Digital Signature Standard (DSS). Federal Information Processing Standards Publication 186-3 (2009)"},{"key":"28_CR48","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)"},{"key":"28_CR49","doi-asserted-by":"crossref","unstructured":"Petit, C., Quisquater, J.-J.: On polynomial systems arising from a weil descent. Cryptology ePrint Archive, Report 2012\/146 (2012), http:\/\/eprint.iacr.org\/","DOI":"10.1007\/978-3-642-34961-4_28"},{"key":"28_CR50","series-title":"Lecture Notes in Computer Science","first-page":"2012","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2012","year":"2012","unstructured":"Pointcheval, D., Johansson, T. (eds.): EUROCRYPT 2012. LNCS, vol.\u00a07237, pp. 2012\u20132031. Springer, Heidelberg (2012)"},{"key":"28_CR51","unstructured":"Semaev, I.: Summation polynomials and the discrete logarithm problem on elliptic curves (2004), http:\/\/www.isg.rhul.ac.uk\/~ppai034\/_pub\/papers\/Semaev%20%28Feb%29.pdf"},{"key":"28_CR52","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/978-3-540-30191-2_31","volume-title":"Information and Communications Security","author":"B.-Y. Yang","year":"2004","unstructured":"Yang, B.-Y., Chen, J.-M., Courtois, N.T.: On Asymptotic Security Estimates in XL and Gr\u00f6bner Bases-Related Algebraic Cryptanalysis. In: L\u00f3pez, J., Qing, S., Okamoto, E. (eds.) ICICS 2004. LNCS, vol.\u00a03269, pp. 401\u2013413. Springer, Heidelberg (2004)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 ASIACRYPT 2012"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34961-4_28.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,20]],"date-time":"2025-04-20T21:08:43Z","timestamp":1745183323000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34961-4_28"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642349607","9783642349614"],"references-count":52,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34961-4_28","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-642-34961-4","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}