{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,27]],"date-time":"2025-05-27T22:24:50Z","timestamp":1748384690289},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642420009"},{"type":"electronic","value":"9783642420016"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-42001-6_3","type":"book-chapter","created":{"date-parts":[[2013,11,20]],"date-time":"2013-11-20T23:25:02Z","timestamp":1384989902000},"page":"19-33","source":"Crossref","is-referenced-by-count":6,"title":["Operating Degrees for XL vs. F4\/F5 for Generic $\\mathcal{M}Q$ with Number of Equations Linear in That of Variables"],"prefix":"10.1007","author":[{"given":"Jenny Yuan-Chun","family":"Yeh","sequence":"first","affiliation":[]},{"given":"Chen-Mou","family":"Cheng","sequence":"additional","affiliation":[]},{"given":"Bo-Yin","family":"Yang","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"3_CR1","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 INRIA report RR-5049"},{"key":"3_CR2","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)"},{"issue":"1","key":"3_CR3","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.jco.2012.07.001","volume":"29","author":"M. Bardet","year":"2013","unstructured":"Bardet, M., Faug\u00e8re, J.-C., Salvy, B., Spaenlehauer, P.-J.: On the complexity of solving quadratic boolean systems. Journal of Complexity\u00a029(1), 53\u201375 (2013) ISSN 0885-064X","journal-title":"Journal of Complexity"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Berbain, C., Gilbert, H., Patarin, J.: QUAD: A practical stream cipher with provable security. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol.\u00a04004, pp. 109\u2013128. Springer, Heidelberg (2006)","DOI":"10.1007\/11761679_8"},{"key":"3_CR5","unstructured":"Bernstein, D.J., Buchmann, J., Dahmen, E. (eds.): Post Quantum Cryptography, 1st edn. Springer (2008) ISBN 3-540-88701-6"},{"issue":"3","key":"3_CR6","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":"3_CR7","doi-asserted-by":"crossref","unstructured":"Bouillaguet, C., Chen, H.-C., Cheng, C.-M., Chou, T., Niederhagen, R., Shamir, A., Yang, B.-Y.: Fast exhaustive search for polynomial systems in F\n                  2. In: Mangard, S., Standaert, F.-X. (eds.) CHES 2010. LNCS, vol.\u00a06225, pp. 203\u2013218. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-15031-9_14"},{"key":"3_CR8","unstructured":"Buchberger, B.: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. PhD thesis, Innsbruck (1965)"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Cheng, C.-M., Chou, T., Niederhagen, R., Yang, B.-Y.: Solving quadratic equations with xl on parallel architectures. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol.\u00a07428, pp. 356\u2013373. Springer, Heidelberg (2012)","DOI":"10.1007\/978-3-642-33027-8_21"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"Chester, C., Friedman, B., Ursell, F.: An extension of the method of steepest descents. Proceedings of Cambridge Philosophical Society\u00a053, 599\u2013611 (1957)","DOI":"10.1017\/S0305004100032655"},{"issue":"205","key":"3_CR11","first-page":"333","volume":"62","author":"D. Coppersmith","year":"1994","unstructured":"Coppersmith, D.: Solving homogeneous linear equations over GF(2) via block wiedemann algorithm. Mathematics of Computation\u00a062(205), 333\u2013350 (1994)","journal-title":"Mathematics of Computation"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Courtois, N.T., Klimov, A.B., 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), \n                    \n                      http:\/\/www.minrank.org\/xlfull.pdf","DOI":"10.1007\/3-540-45539-6_27"},{"key":"3_CR13","doi-asserted-by":"crossref","unstructured":"Diem, C.: The XL-algorithm and a conjecture from commutative algebra. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol.\u00a03329, pp. 323\u2013337. Springer, Heidelberg (2004)","DOI":"10.1007\/978-3-540-30539-2_23"},{"key":"3_CR14","unstructured":"Ding, J., Buchmann, J., Mohamed, M.S.E., Mohamed, W.S.A.E., Weinmann, R.-P.: Mutant XL. In: talk at the First International Conference on Symbolic Computation and Cryptography (SCC 2008), Beijing (2008)"},{"key":"3_CR15","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.\u00a05037, pp. 242\u2013257. Springer, Heidelberg (2008), \n                    \n                      http:\/\/eprint.iacr.org\/2008\/108"},{"key":"3_CR16","unstructured":"Faug\u00e8re, J.-C.: Solving efficiently structured polynomial systems and applications in cryptology (September 2011), \n                    \n                      http:\/\/ecc2011.loria.fr\/slides\/faugere.pdf\n                    \n                    \n                  ; Talk at ECC 2011, 9:30 AM (September 20, 2011)"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Gao, S., Guan, Y., Volny, F.: A new incremental algorithm for computing groebner bases. In: Koepf, W. (ed.) ISSAC, pp. 13\u201319. ACM (2010)","DOI":"10.1145\/1837934.1837944"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Joux, A., Vitse, V.: A variant of the F4 algorithm. In: Kiayias, A. (ed.) CT-RSA 2011. LNCS, vol.\u00a06558, pp. 356\u2013375. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-19074-2_23"},{"key":"3_CR19","doi-asserted-by":"crossref","unstructured":"Lazard, D.: Gr\u00f6bner-bases, Gaussian elimination and resolution of systems of algebraic equations. In: EUROCAL 1983. LNCS, vol.\u00a0162, pp. 146\u2013156. Springer, Heidelberg (March 1983)","DOI":"10.1007\/3-540-12868-9_99"},{"key":"3_CR20","first-page":"1171","volume":"111","author":"O.B. Lupanov","year":"1956","unstructured":"Lupanov, O.B.: On rectifier and contact-rectifier circuits. Akademii Nauk SSSR\u00a0111, 1171\u20131174 (1956) ISSN 0002\u0105V3264","journal-title":"Akademii Nauk SSSR"},{"key":"3_CR21","unstructured":"MAGMA project, Computational Algebra Group, University of Sydney. The MAGMA computational algebra system for algebra, number theory and geometry, \n                    \n                      http:\/\/magma.maths.usyd.edu.au\/magma\/"},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"Mohamed, M.S.E., Cabarcas, D., Ding, J., Buchmann, J., Bulygin, S.: MXL3: An efficient algorithm for computing Gr\u00f6bner bases of zero-dimensional ideals. In: Lee, D., Hong, S. (eds.) ICISC 2009. LNCS, vol.\u00a05984, pp. 87\u2013100. Springer, Heidelberg (2010)","DOI":"10.1007\/978-3-642-14423-3_7"},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"Mohamed, M.S.E., Mohamed, W.S.A.E., Ding, J., Buchmann, J.: MXL2: Solving Polynomial Equations over GF(2) using an improved mutant strategy. In: Buchmann, J., Ding, J. (eds.) PQCrypto 2008. LNCS, vol.\u00a05299, pp. 203\u2013215. Springer, Heidelberg (2008)","DOI":"10.1007\/978-3-540-88403-3_14"},{"key":"3_CR24","unstructured":"Mohamed, W.S.A., Ding, J., Kleinjung, T., Bulygin, S., Buchmann, J.: PWXL: A parallel Wiedemann-XL algorithm for solving polynomial equations over GF(2). In: Cid, C., Faug\u00e8re, J.-C. (eds.) Proceedings of the 2nd International Conference on Symbolic Computation and Cryptography, pp. 89\u2013100 (June 2010)"},{"issue":"1","key":"3_CR25","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1109\/TIT.1986.1057137","volume":"-32","author":"D. Wiedemann","year":"1976","unstructured":"Wiedemann, D.: Solving sparse linear equations over finite fields. IEEE Transactions on Information Theory, IT-32(1), 54\u201362 (1976)","journal-title":"IEEE Transactions on Information Theory, IT"},{"key":"3_CR26","unstructured":"Williams, V.V.: Breaking the Coppersmith-Winograd barrier (2011), \n                    \n                      www.cs.berkeley.edu\/~virgi\/matrixmult.pdf"},{"key":"3_CR27","doi-asserted-by":"crossref","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)","DOI":"10.1007\/11496618_7"},{"key":"3_CR28","doi-asserted-by":"crossref","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)","DOI":"10.1007\/978-3-540-27800-9_24"},{"key":"3_CR29","doi-asserted-by":"crossref","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)","DOI":"10.1007\/978-3-540-30191-2_31"},{"key":"3_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/978-3-540-74619-5_19","volume-title":"Fast Software Encryption","author":"B.-Y. Yang","year":"2007","unstructured":"Yang, B.-Y., Chen, O.C.-H., Bernstein, D.J., Chen, J.-M.: Analysis of QUAD. In: Biryukov, A. (ed.) FSE 2007. LNCS, vol.\u00a04593, pp. 290\u2013308. Springer, Heidelberg (2007)"},{"key":"3_CR31","unstructured":"Yang, B.-Y., Chen, O.C.-H., Chen, J.-M.: The limit of XL implemented with sparse matrices. In: Workshop Record, PQCrypto Workshop, Leuven (2006), \n                    \n                      http:\/\/postquantum.cr.yp.to\/pqcrypto2006record.pdf"}],"container-title":["Lecture Notes in Computer Science","\u2018"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-42001-6_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,24]],"date-time":"2019-05-24T08:39:26Z","timestamp":1558687166000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-42001-6_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642420009","9783642420016"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-42001-6_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}