{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T04:59:25Z","timestamp":1764997165973,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319790626"},{"type":"electronic","value":"9783319790633"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","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":[[2018]]},"DOI":"10.1007\/978-3-319-79063-3_23","type":"book-chapter","created":{"date-parts":[[2018,3,31]],"date-time":"2018-03-31T14:23:38Z","timestamp":1522506218000},"page":"487-506","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Asymptotically Faster Quantum Algorithms to Solve Multivariate Quadratic Equations"],"prefix":"10.1007","author":[{"given":"Daniel J.","family":"Bernstein","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9362-5282","authenticated-orcid":false,"given":"Bo-Yin","family":"Yang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,4,1]]},"reference":[{"key":"23_CR1","doi-asserted-by":"publisher","first-page":"766","DOI":"10.1137\/0218053","volume":"18","author":"CH Bennett","year":"1989","unstructured":"Bennett, C.H.: Time\/space trade-offs for reversible computation. SIAM J. Comput. 18, 766\u2013776 (1989). Cited in \u00a73.1, \u00a73.2","journal-title":"SIAM J. Comput."},{"key":"23_CR2","unstructured":"Bernstein, D.J.: Circuits for integer factorization: a proposal (2001). https:\/\/cr.yp.to\/papers.html#nfscircuit. Cited in \u00a72.6"},{"key":"23_CR3","doi-asserted-by":"crossref","unstructured":"Brent, R.P., Kung, H.T.: The area-time complexity of binary multiplication. J. ACM 28, 521\u2013534 (1981). http:\/\/wwwmaths.anu.edu.au\/~brent\/pub\/pub055.html. Cited in \u00a72.6","DOI":"10.1145\/322261.322269"},{"key":"23_CR4","doi-asserted-by":"crossref","unstructured":"Cheng, C.-M., Chou, T., Niederhagen, R., Yang, B.-Y.: Solving quadratic equations with XL on parallel architectures. In: CHES 2012 [21], pp. 356\u2013373 (2012). https:\/\/eprint.iacr.org\/2016\/412. Cited in \u00a72.5","DOI":"10.1007\/978-3-642-33027-8_21"},{"key":"23_CR5","doi-asserted-by":"crossref","unstructured":"Chester, C.R., Friedman, B., Ursell, F.: An extension of the method of steepest descents. In: Proceedings of Cambridge Philosophical Society, vol. 53, pp. 599\u2013611 (1957). Cited in \u00a74.5","DOI":"10.1017\/S0305004100032655"},{"key":"23_CR6","doi-asserted-by":"crossref","unstructured":"Courtois, N., Klimov, A., Patarin, J., Shamir, A.: Efficient algorithms for solving overdefined systems of multivariate polynomial equations. In: Eurocrypt 2000 [20], pp. 392\u2013407 (2000). http:\/\/minrank.org\/xlfull.pdf. Cited in \u00a72.1, \u00a72.7","DOI":"10.1007\/3-540-45539-6_27"},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"Diem, C.: The XL-algorithm and a conjecture from commutative algebra. In: Asiacrypt 2004 [14], pp. 323\u2013337 (2004). Cited \u00a74.5","DOI":"10.1007\/978-3-540-30539-2_23"},{"key":"23_CR8","doi-asserted-by":"crossref","unstructured":"Faug\u00e8re, J.-C., Otmani, A., Perret, L., Tillich, J.-P.: Algebraic cryptanalysis of McEliece variants with compact keys. In: Eurocrypt 2010 [10], pp. 279\u2013298 (2010). https:\/\/www.iacr.org\/archive\/eurocrypt2010\/66320290\/66320290.pdf. Cited in \u00a71.1","DOI":"10.1007\/978-3-642-13190-5_14"},{"key":"23_CR9","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic Combinatorics","author":"P Flajolet","year":"2009","unstructured":"Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009). ISBN 978-0-521-89806-5. http:\/\/ac.cs.princeton.edu\/home\/. Cited in \u00a72.4, \u00a72.4, \u00a72.4"},{"key":"23_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13190-5","volume-title":"Advances in Cryptology-EUROCRYPT 2010","year":"2010","unstructured":"Gilbert, H. (ed.): Advances in Cryptology-EUROCRYPT 2010. LNCS, vol. 6110. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-13190-5. ISBN 978-3-642-13189-9. See [8]"},{"key":"23_CR11","doi-asserted-by":"crossref","unstructured":"Klein, P.N. (ed.): Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, 16\u201319 January. SIAM (2017). See [15]","DOI":"10.1137\/1.9781611974782"},{"key":"23_CR12","unstructured":"Knill, E.: An analysis of Bennett\u2019s pebble game (1995). http:\/\/arxiv.org\/abs\/math\/9508218. Cited in \u00a73.2, \u00a73.3"},{"key":"23_CR13","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0304-3975(81)90064-5","volume":"15","author":"D Lazard","year":"1981","unstructured":"Lazard, D.: R\u00e9solution des syst\u00e8mes d\u2019\u00e9quations alg\u00e9briques. Theoret. Comput. Sci. 15, 77\u2013110 (1981). https:\/\/www.sciencedirect.com\/science\/article\/pii\/0304397581900645. Cited in \u00a72.1","journal-title":"Theoret. Comput. Sci."},{"key":"23_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/b104116","volume-title":"Advances in Cryptology-ASIACRYPT 2004","year":"2004","unstructured":"Lee, P.J. (ed.): Advances in Cryptology-ASIACRYPT 2004. LNCS, vol. 3329. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/b104116. See [7]"},{"key":"23_CR15","unstructured":"Lokshtanov, D., Paturi, R., Tamaki, S., Williams, R.R., Yu, H.: Beating brute force for systems of polynomial equations over finite fields. In: SODA 2017 [11], pp. 2190\u20132202 (2017). http:\/\/theory.stanford.edu\/~yuhch123\/files\/polyEq.pdf. Cited in \u00a71.2, \u00a71.2"},{"key":"23_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/b101042","volume-title":"Information and Communications Security, ICICS 2004","year":"2004","unstructured":"Lopez, J., Qing, S., Okamoto, E. (eds.): Information and Communications Security, ICICS 2004. LNCS, vol. 3269. Springer, Cham (2004). https:\/\/doi.org\/10.1007\/b101042. ISBN 3-540-23563-9. See [26]"},{"key":"23_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-68339-9","volume-title":"Advances in Cryptology-EUROCRYPT 1996","year":"1996","unstructured":"Maurer, U.M. (ed.): Advances in Cryptology-EUROCRYPT 1996. LNCS, vol. 1070. Springer, Heidelberg (1996). https:\/\/doi.org\/10.1007\/3-540-68339-9. ISBN 3-540-61186-X. MR 97g:94002. See [18]"},{"key":"23_CR18","doi-asserted-by":"crossref","unstructured":"Patarin, J.: Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms. In: Eurocrypt 1996 [17], pp. 33\u201348 (1996). See also newer version [19]","DOI":"10.1007\/3-540-68339-9_4"},{"key":"23_CR19","unstructured":"Patarin, J.: Hidden fields equations (HFE) and isomorphisms of polynomials (IP): two new families of asymmetric algorithms, extended version (1998). See also older version [18]. http:\/\/minrank.org\/hfe.pdf. Cited in \u00a71.1"},{"key":"23_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45539-6","volume-title":"Advances in Cryptology-EUROCRYPT 2000","year":"2000","unstructured":"Preneel, B. (ed.): Advances in Cryptology-EUROCRYPT 2000. LNCS, vol. 1807. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/3-540-45539-6. See [6]"},{"key":"23_CR21","series-title":"Lecture Notes in Computer Science","volume-title":"Cryptographic Hardware and Embedded Systems-CHES 2012","year":"2012","unstructured":"Prouff, E., Schaumont, P. (eds.): Cryptographic Hardware and Embedded Systems-CHES 2012. LNCS, vol. 7428. Springer, Heidelberg (2012). ISBN 978-3-642-33026-1. See [4]"},{"key":"23_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/b98755","volume-title":"Information Security and Privacy","year":"2004","unstructured":"Wang, H., Pieprzyk, J., Varadharajan, V. (eds.): Information Security and Privacy. LNCS, vol. 3108. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/b98755. ISBN 3-540-22379-7. See [25]"},{"key":"23_CR23","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1109\/TIT.1986.1057137","volume":"32","author":"DH Wiedemann","year":"1986","unstructured":"Wiedemann, D.H.: Solving sparse linear equations over finite fields. IEEE Trans. Inf. Theory 32, 54\u201362 (1986). MR 87g:11166. Cited in \u00a72.5, \u00a72.5","journal-title":"IEEE Trans. Inf. Theory"},{"key":"23_CR24","volume-title":"Asymptotic Approximations of Integrals","author":"R Wong","year":"1989","unstructured":"Wong, R.: Asymptotic Approximations of Integrals. Academic Press, Cambridge (1989). ISBN 0-12-762535-6. Cited in \u00a72.4"},{"key":"23_CR25","doi-asserted-by":"crossref","unstructured":"Yang, B.-Y., Chen, J.-M.: Theoretical analysis of XL over small fields. In: ACISP 2004 [22], pp. 277\u2013288 (2004). http:\/\/precision.moscito.org\/by-publ\/recent\/xxl2-update.pdf. Cited in \u00a72.5, \u00a74.5","DOI":"10.1007\/978-3-540-27800-9_24"},{"key":"23_CR26","unstructured":"Yang, B.-Y., Chen, J.-M., Courtois, N.: On asymptotic security estimates in XL and Gr\u00f6bner bases-related algebraic cryptanalysis. In: ICICS 2004 [16], pp. 401\u2013413 (2004). http:\/\/www.iis.sinica.edu.tw\/papers\/byyang\/2384-F.pdf. Cited in \u00a71.2, \u00a72.5, \u00a74.5, \u00a74.5, \u00a74.7"}],"container-title":["Lecture Notes in Computer Science","Post-Quantum Cryptography"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-79063-3_23","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T14:33:56Z","timestamp":1710340436000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-79063-3_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319790626","9783319790633"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-79063-3_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"1 April 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"PQCrypto","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Post-Quantum Cryptography","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Fort Lauderdale","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"pqcrypto2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.math.fau.edu\/pqcrypto2018\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}