{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,3]],"date-time":"2026-03-03T18:47:49Z","timestamp":1772563669881,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":36,"publisher":"ACM","license":[{"start":{"date-parts":[[2012,7,22]],"date-time":"2012-07-22T00:00:00Z","timestamp":1342915200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["ICT-2007-216676 ECRYPT II"],"award-info":[{"award-number":["ICT-2007-216676 ECRYPT II"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-09-JCJCJ-0064-01"],"award-info":[{"award-number":["ANR-09-JCJCJ-0064-01"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-2011-BS02-013-04"],"award-info":[{"award-number":["ANR-2011-BS02-013-04"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2012,7,22]]},"DOI":"10.1145\/2442829.2442843","type":"proceedings-article","created":{"date-parts":[[2013,2,22]],"date-time":"2013-02-22T19:25:33Z","timestamp":1361561133000},"page":"67-74","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":27,"title":["Solving polynomial systems over finite fields"],"prefix":"10.1145","author":[{"given":"Luk","family":"Bettale","sequence":"first","affiliation":[{"name":"Nanterre Cedex, France"}]},{"given":"Jean-Charles","family":"Faug\u00e8re","sequence":"additional","affiliation":[{"name":"Univ Paris, CNRS, UFR Ing\u00e9nierie, Place Jussieu, Paris"}]},{"given":"Ludovic","family":"Perret","sequence":"additional","affiliation":[{"name":"Univ Paris, UFR Ing\u00e9nierie, Paris"}]}],"member":"320","published-online":{"date-parts":[[2012,7,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25385-0_10"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"crossref","unstructured":"G.\n      Ars J.-C.\n      Faug\u00e8re H.\n      Imai M.\n      Kawazoe and \n      M.\n      Sugita\n  . \n  Comparison between xl and gr\u00f6bner basis algorithms\n  . In P. J. Lee editor ASIACRYPT volume \n  3329\n   of \n  Lecture Notes in Computer Science pages \n  338\n  --\n  353\n  . \n  Springer 2004\n  .  G. Ars J.-C. Faug\u00e8re H. Imai M. Kawazoe and M. Sugita. Comparison between xl and gr\u00f6bner basis algorithms. In P. J. Lee editor ASIACRYPT volume 3329 of Lecture Notes in Computer Science pages 338--353. Springer 2004.","DOI":"10.1007\/978-3-540-30539-2_24"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2008.11.004"},{"key":"e_1_3_2_1_5_1","volume-title":"INRIA","author":"Bardet M.","year":"2002","unstructured":"M. Bardet , J.-C. Faug\u00e8re , and B. Salvy . Complexity study of Gr\u00f6bner basis computation. Technical report , INRIA , 2002 . http:\/\/www.inria.fr\/rrrt\/rr-5049.html. M. Bardet, J.-C. Faug\u00e8re, and B. Salvy. Complexity study of Gr\u00f6bner basis computation. Technical report, INRIA, 2002. http:\/\/www.inria.fr\/rrrt\/rr-5049.html."},{"key":"e_1_3_2_1_6_1","first-page":"71","volume-title":"International Conference on Polynomial System Solving -- ICPSS","author":"Bardet M.","year":"2004","unstructured":"M. Bardet , J.-C. Faug\u00e8re , and B. Salvy . On the complexity of Gr\u00f6bner basis computation of semi-regular overdetermined algebraic equations . In International Conference on Polynomial System Solving -- ICPSS , pages 71 -- 75 , 2004 . M. Bardet, J.-C. Faug\u00e8re, and B. Salvy. On the complexity of Gr\u00f6bner basis computation of semi-regular overdetermined algebraic equations. In International Conference on Polynomial System Solving -- ICPSS, pages 71--75, 2004."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jco.2012.07.001"},{"key":"e_1_3_2_1_8_1","first-page":"1","volume-title":"The Effective Methods in Algebraic Geometry Conference -- MEGA 2005","author":"Bardet M.","year":"2005","unstructured":"M. Bardet , J.-C. Faug\u00e8re , B. Salvy , and B.-Y. Yang . Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems . In The Effective Methods in Algebraic Geometry Conference -- MEGA 2005 , pages 1 -- 14 , 2005 . M. Bardet, J.-C. Faug\u00e8re, B. Salvy, and B.-Y. Yang. Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems. In The Effective Methods in Algebraic Geometry Conference -- MEGA 2005, pages 1--14, 2005."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1515\/JMC.2009.009"},{"key":"e_1_3_2_1_10_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/978-3-642-15031-9_14","volume-title":"S. Mangard and F.-X","author":"Bouillaguet C.","year":"2010","unstructured":"C. Bouillaguet , H.-C. Chen , C.-M. Cheng , T. Chou , R. Niederhagen , A. Shamir , and B.-Y. Yang . Fast exhaustive search for polynomial systems in f<sub>2<\/sub> . In S. Mangard and F.-X . Standaert, editors, CHES, volume 6225 of Lecture Notes in Computer Science , pages 203 -- 218 . Springer , 2010 . C. Bouillaguet, H.-C. Chen, C.-M. Cheng, T. Chou, R. Niederhagen, A. Shamir, and B.-Y. Yang. Fast exhaustive search for polynomial systems in f<sub>2<\/sub>. In S. Mangard and F.-X. Standaert, editors, CHES, volume 6225 of Lecture Notes in Computer Science, pages 203--218. Springer, 2010."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jsc.2005.09.007"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1089310.1089312"},{"key":"e_1_3_2_1_14_1","volume-title":"Algebraic aspects of the advanced encryption standard","author":"Cid C.","year":"2006","unstructured":"C. Cid , S. Murphy , and M. J. B. Robshaw . Algebraic aspects of the advanced encryption standard . Springer , 2006 . C. Cid, S. Murphy, and M. J. B. Robshaw. Algebraic aspects of the advanced encryption standard. Springer, 2006."},{"key":"e_1_3_2_1_15_1","unstructured":"N. Courtois L. Goubin and J. Patarin. SFLASHv3 a fast asymmetric signature scheme. available at http:\/\/eprint.iacr.org\/2003\/211.  N. Courtois L. Goubin and J. Patarin. SFLASHv3 a fast asymmetric signature scheme. available at http:\/\/eprint.iacr.org\/2003\/211."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"N.\n      Courtois\n     and \n      J.\n      Pieprzyk\n  . \n  Cryptanalysis of block ciphers with overdefined systems of equations\n  . In Y. Zheng editor ASIACRYPT volume \n  2501\n   of \n  Lecture Notes in Computer Science pages \n  267\n  --\n  287\n  . \n  Springer 2002\n  .   N. Courtois and J. Pieprzyk. Cryptanalysis of block ciphers with overdefined systems of equations. In Y. Zheng editor ASIACRYPT volume 2501 of Lecture Notes in Computer Science pages 267--287. Springer 2002.","DOI":"10.1007\/3-540-36178-2_17"},{"key":"e_1_3_2_1_17_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"152","DOI":"10.1007\/978-3-540-77272-9_10","volume-title":"Cryptography and Coding '07","author":"Courtois N. T.","year":"2007","unstructured":"N. T. Courtois and G. V. Bard . Algebraic cryptanalysis of the data encryption standard . In Cryptography and Coding '07 , volume 4887 of Lecture Notes in Computer Science , pages 152 -- 169 . Springer , 2007 . N. T. Courtois and G. V. Bard. Algebraic cryptanalysis of the data encryption standard. In Cryptography and Coding '07, volume 4887 of Lecture Notes in Computer Science, pages 152--169. Springer, 2007."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"I.\n      Dinur\n     and \n      A.\n      Shamir\n  . \n  Cube attacks on tweakable black box polynomials\n  . In A. Joux editor EUROCRYPT volume \n  5479\n   of \n  Lecture Notes in Computer Science pages \n  278\n  --\n  299\n  . \n  Springer 2009\n  .  I. Dinur and A. Shamir. Cube attacks on tweakable black box polynomials. In A. Joux editor EUROCRYPT volume 5479 of Lecture Notes in Computer Science pages 278--299. Springer 2009.","DOI":"10.1007\/978-3-642-01001-9_16"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-4049(99)00005-5"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/780506.780516"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-85174-5_16"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jsco.1993.1051"},{"key":"e_1_3_2_1_23_1","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","author":"Faug\u00e8re J.-C.","year":"2003","unstructured":"J.-C. Faug\u00e8re and A. Joux . Algebraic cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gr\u00f6bner bases . In Advances in Cryptology -- CRYPTO 2003 , volume 2729 of Lecture Notes in Computer Science , pages 44 -- 60 . Springer , 2003. J.-C. Faug\u00e8re and A. Joux. Algebraic cryptanalysis of Hidden Field Equation (HFE) cryptosystems using Gr\u00f6bner bases. In Advances in Cryptology -- CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science, pages 44--60. Springer, 2003."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5_14"},{"key":"e_1_3_2_1_25_1","series-title":"Lecture Notes in Computer Science","first-page":"1","volume-title":"Proceedings of Eurocrypt","author":"Faug\u00e8re J.-C.","year":"2012","unstructured":"J.-C. Faug\u00e8re , L. Perret , C. Petit , and G. Renault . Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Field . In Proceedings of Eurocrypt 2012 , Lecture Notes in Computer Science , pages 1 -- 15 . Springer Verlag , 2012. J.-C. Faug\u00e8re, L. Perret, C. Petit, and G. Renault. Improving the Complexity of Index Calculus Algorithms in Elliptic Curves over Binary Field. In Proceedings of Eurocrypt 2012, Lecture Notes in Computer Science, pages 1--15. Springer Verlag, 2012."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-12092"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1837934.1837944"},{"key":"e_1_3_2_1_28_1","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson . Computers and Intractability: A Guide to the Theory of NP-Completeness . W. H. Freeman and Company , 1979 . M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979."},{"key":"e_1_3_2_1_29_1","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 '99","author":"Kipnis A.","year":"1999","unstructured":"A. Kipnis , J. Patarin , and L. Goubin . Unbalanced oil and vinegar signature schemes . In Advances in Cryptology -- EUROCRYPT '99 , volume 1592 of Lecture Notes in Computer Science , pages 206 -- 222 . Springer , 1999 . A. Kipnis, J. Patarin, and L. Goubin. Unbalanced oil and vinegar signature schemes. In Advances in Cryptology -- EUROCRYPT '99, volume 1592 of Lecture Notes in Computer Science, pages 206--222. Springer, 1999."},{"key":"e_1_3_2_1_30_1","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 '99","author":"Kipnis A.","year":"1999","unstructured":"A. Kipnis and A. Shamir . Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization . In Advances in Cryptology -- CRYPTO '99 , volume 1666 of Lecture Notes in Computer Science , pages 19 -- 30 . Springer , 1999 . A. Kipnis and A. Shamir. Cryptanalysis of the HFE Public Key Cryptosystem by Relinearization. In Advances in Cryptology -- CRYPTO '99, volume 1666 of Lecture Notes in Computer Science, pages 19--30. Springer, 1999."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"crossref","unstructured":"A.\n      Kipnis\n     and \n      A.\n      Shamir\n  . \n  Cryptanalysis of the hfe public key cryptosystem by relinearization\n  . In M. J. Wiener editor CRYPTO volume \n  1666\n   of \n  Lecture Notes in Computer Science pages \n  19\n  --\n  30\n  . \n  Springer 1999\n  .   A. Kipnis and A. Shamir. Cryptanalysis of the hfe public key cryptosystem by relinearization. In M. J. Wiener editor CRYPTO volume 1666 of Lecture Notes in Computer Science pages 19--30. Springer 1999.","DOI":"10.1007\/3-540-48405-1_2"},{"key":"e_1_3_2_1_32_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"419","DOI":"10.1007\/3-540-45961-8_39","volume-title":"Advances in Cryptology -- EUROCRYPT '88","author":"Matsumoto T.","year":"1988","unstructured":"T. Matsumoto and H. Imai . Public quadratic polynomial-tuples for efficient signature-verification and message-encryption . In Advances in Cryptology -- EUROCRYPT '88 , volume 330 of Lecture Notes in Computer Science , pages 419 -- 453 . Springer , 1988 . T. Matsumoto and H. Imai. Public quadratic polynomial-tuples for efficient signature-verification and message-encryption. In Advances in Cryptology -- EUROCRYPT '88, volume 330 of Lecture Notes in Computer Science, pages 419--453. Springer, 1988."},{"key":"e_1_3_2_1_33_1","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 '96","author":"Patarin J.","year":"1996","unstructured":"J. Patarin . Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP) : two new families of asymmetric algorithms . In Advances in Cryptology -- EUROCRYPT '96 , volume 1070 of Lecture Notes in Computer Science , pages 33 -- 48 . Springer , 1996 . J. Patarin. Hidden Fields Equations (HFE) and Isomorphisms of Polynomials (IP): two new families of asymmetric algorithms. In Advances in Cryptology -- EUROCRYPT '96, volume 1070 of Lecture Notes in Computer Science, pages 33--48. Springer, 1996."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"K.\n      Sakumoto T.\n      Shirai and \n      H.\n      Hiwatari\n  . \n  Public-key identification schemes based on multivariate quadratic polynomials\n  . In P. Rogaway editor CRYPTO volume \n  6841\n   of \n  Lecture Notes in Computer Science pages \n  706\n  --\n  723\n  . \n  Springer 2011\n  .   K. Sakumoto T. Shirai and H. Hiwatari. Public-key identification schemes based on multivariate quadratic polynomials. In P. Rogaway editor CRYPTO volume 6841 of Lecture Notes in Computer Science pages 706--723. Springer 2011.","DOI":"10.1007\/978-3-642-22792-9_40"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1717969"},{"key":"e_1_3_2_1_36_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"349","DOI":"10.1007\/978-3-540-74619-5_22","volume-title":"Fast Software Encryption","author":"Sugita M.","year":"2007","unstructured":"M. Sugita , M. Kawazoe , L. Perret , and H. Imai . Algebraic cryptanalysis of 58-round SHA-1 . In Fast Software Encryption , volume 4593 of Lecture Notes in Computer Science , pages 349 -- 365 . Springer , 2007 . M. Sugita, M. Kawazoe, L. Perret, and H. Imai. Algebraic cryptanalysis of 58-round SHA-1. In Fast Software Encryption, volume 4593 of Lecture Notes in Computer Science, pages 349--365. Springer, 2007."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"crossref","unstructured":"B.-Y.\n      Yang\n     and \n      J.-M.\n      Chen\n    .\n  Theoretical analysis of xl over small fields\n  . In H. Wang J. Pieprzyk and V. Varadharajan editors ACISP volume \n  3108\n   of \n  Lecture Notes in Computer Science pages \n  277\n  --\n  288\n  . \n  Springer 2004\n  .  B.-Y. Yang and J.-M. Chen. Theoretical analysis of xl over small fields. In H. Wang J. Pieprzyk and V. Varadharajan editors ACISP volume 3108 of Lecture Notes in Computer Science pages 277--288. Springer 2004.","DOI":"10.1007\/978-3-540-27800-9_24"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"crossref","unstructured":"B.-Y.\n      Yang J.-M.\n      Chen and \n      N.\n      Courtois\n  . \n  On asymptotic security estimates in xl and gr\u00f6bner bases-related algebraic cryptanalysis\n  . In J. Lopez S. Qing and E. Okamoto editors ICICS volume \n  3269\n   of \n  Lecture Notes in Computer Science pages \n  401\n  --\n  413\n  . \n  Springer 2004\n  .  B.-Y. Yang J.-M. Chen and N. Courtois. On asymptotic security estimates in xl and gr\u00f6bner bases-related algebraic cryptanalysis. In J. Lopez S. Qing and E. Okamoto editors ICICS volume 3269 of Lecture Notes in Computer Science pages 401--413. Springer 2004.","DOI":"10.1007\/978-3-540-30191-2_31"}],"event":{"name":"ISSAC'12: International Symposium on Symbolic and Algebraic Computation","location":"Grenoble France","acronym":"ISSAC'12","sponsor":["Grenoble University Grenoble University","INRIA Institut Natl de Recherche en Info et en Automatique","SIGSAM ACM Special Interest Group on Symbolic and Algebraic Manipulation"]},"container-title":["Proceedings of the 37th International Symposium on Symbolic and Algebraic Computation"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2442829.2442843","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2442829.2442843","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:39Z","timestamp":1750234719000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2442829.2442843"}},"subtitle":["improved analysis of the hybrid approach"],"short-title":[],"issued":{"date-parts":[[2012,7,22]]},"references-count":36,"alternative-id":["10.1145\/2442829.2442843","10.1145\/2442829"],"URL":"https:\/\/doi.org\/10.1145\/2442829.2442843","relation":{},"subject":[],"published":{"date-parts":[[2012,7,22]]},"assertion":[{"value":"2012-07-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}