{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,5]],"date-time":"2022-04-05T21:34:53Z","timestamp":1649194493282},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,8,17]],"date-time":"2019-08-17T00:00:00Z","timestamp":1566000000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,8,17]],"date-time":"2019-08-17T00:00:00Z","timestamp":1566000000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["AAECC"],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1007\/s00200-019-00399-7","type":"journal-article","created":{"date-parts":[[2019,8,17]],"date-time":"2019-08-17T16:02:26Z","timestamp":1566057746000},"page":"3-47","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Solving non-linear Boolean equation systems by variable elimination"],"prefix":"10.1007","volume":"32","author":[{"given":"Bj\u00f8rn","family":"Greve","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u00d8yvind","family":"Ytrehus","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"H\u00e5vard","family":"Raddum","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gunnar","family":"Fl\u00f8ystad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,8,17]]},"reference":[{"issue":"1\u20132","key":"399_CR1","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s10623-016-0256-x","volume":"82","author":"P Zajac","year":"2017","unstructured":"Zajac, P.: Upper bounds on the complexity of algebraic cryptanalysis of ciphers with a low multiplicative complexity. Des. Codes Cryptogr. 82(1\u20132), 43\u201356 (2017)","journal-title":"Des. Codes Cryptogr."},{"key":"399_CR2","doi-asserted-by":"crossref","unstructured":"Shamir, A., Patarin, J., Courtois, N., Klimov, A.: Efficient Algorithms for Solving Overdefined Systems of Multivariate Polynomial Equations. In: Eurocrypt\u20192000, LNCS 1807, pp. 392\u2013407, Springer (2000)","DOI":"10.1007\/3-540-45539-6_27"},{"key":"399_CR3","doi-asserted-by":"crossref","unstructured":"Courtois, N.T., Pieprzyk, J.: Cryptanalysis of block ciphers with overdefined systems of equations. In: Advances in Cryptology\u2014ASIACRYPT 2002. ASIACRYPT 2002. Lecture Notes in Computer Science, vol. 2501, pp. 267 \u2013 287. Springer, Berlin (2002)","DOI":"10.1007\/3-540-36178-2_17"},{"key":"399_CR4","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1016\/S0022-4049(99)00005-5","volume":"139","author":"J-C Faugere","year":"1999","unstructured":"Faugere, J.-C.: A new efficient algorithm for computing Gr\u00f6bner bases (F4). Effective methods in algebraic geometry (Saint-Malo, 1998). J. Pure Appl. Algebra 139, 61\u201388 (1999)","journal-title":"J. Pure Appl. Algebra"},{"key":"399_CR5","doi-asserted-by":"crossref","unstructured":"Kandri-Rody, A., Kapur, D., Narendran, P., An ideal-theoretic approach to word problems and unification problems over finitely presented commutative algebras. In: Jouannaud J.P. (eds.), Rewriting Techniques and Applications. RTA. Lecture Notes in Computer Science, vol 202. Springer, Berlin (1985)","DOI":"10.1007\/3-540-15976-2_17"},{"key":"399_CR6","unstructured":"Sakai, K., Sato, Y.: Boolean Gr\u00f6bner bases, ICOT Technical Momorandum 488 (1988). http:\/\/www.jipdec.or.jp\/archives\/icot\/ARCHIVE\/Museum\/TRTM\/tm0488.htm. Accessed 15 Sept 2017"},{"key":"399_CR7","unstructured":"Decker, W., Greuel, G.-M., Pfister, G., Sch\u00f6nemann, H.: Singular 3-1-2\u2014a computer algebra system for polynomial computations (2010). http:\/\/www.singular.uni-kl.de\/. Accessed 4 Oct 2017"},{"issue":"9","key":"399_CR8","doi-asserted-by":"publisher","first-page":"1326","DOI":"10.1016\/j.jsc.2008.02.017","volume":"44","author":"M Brickenstein","year":"2009","unstructured":"Brickenstein, M., Dreyer, A.: A framework for Gr\u00f6bner-basis computations with Boolean polynomials. J. Symbol. Comput. 44(9), 1326\u20131345 (2009)","journal-title":"J. Symbol. Comput."},{"key":"399_CR9","doi-asserted-by":"crossref","unstructured":"Hor\u00e1cek, J., Kreuzer, M., Ekossono, A.S.M.: Computing Boolean border bases. In: 2016 18th international symposium on symbolic and numeric algorithms for scientific computing (SYNASC), pp. 465\u2013472. IEEE (2016)","DOI":"10.1109\/SYNASC.2016.076"},{"key":"399_CR10","doi-asserted-by":"crossref","unstructured":"Lokshtanov, D., Paturi, R., Tamaki, S., Williams, R., Yu, H.: Beating brute force for systems of polynomial equations over finite fields. In: The 27th ACM-SIAM Symposium on Discrete Algorithms (SODA) (2017)","DOI":"10.1137\/1.9781611974782.143"},{"key":"399_CR11","doi-asserted-by":"crossref","unstructured":"Smolensky, R.: Algebraic methods in the theory of lower bounds for Boolean circuit complexity. In: Proceedings of the 19th Annual ACM Symposium on Theory of Computing (STOC), pp. 77\u201382 (1987)","DOI":"10.1145\/28395.28404"},{"key":"399_CR12","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Williams, R.: Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov\u2013Smolensky. In: Proceedings of the 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1246\u20131255 (2016)","DOI":"10.1137\/1.9781611974331.ch87"},{"key":"399_CR13","doi-asserted-by":"crossref","unstructured":"Lazard, D.: Gaussian elimination and resolution of systems of algebraic equations. In: Proceedings of EUROCAL 1983, volume 162 of LNCS, pp. 146-157 (1983)","DOI":"10.1007\/3-540-12868-9_99"},{"key":"399_CR14","doi-asserted-by":"crossref","unstructured":"Giusti, M.: Some effectivity problems in polynomial ideal theory. In: Proceedings of International Symposium on Symbolic and Algebraic Computation EUROSAM 84, Cambridge (England), volume 174 of LNCS, pp. 159\u2013171. Springer (1994)","DOI":"10.1007\/BFb0032839"},{"key":"399_CR15","unstructured":"Bardet, M., Faugere, J.-C., Salvy, B.: Complexity of Gr\u00f6bner basis computation for semiregular overdetermined sequences over $$\\mathbb{F}_2$$ with solutions in $$\\mathbb{F}_2$$, rapport de recherche 5049. Institut National de Recherche en Informatique et en Automatique, Lorraine (2003)"},{"key":"399_CR16","unstructured":"Bardet, M., Faugere, J.-C., Salvy, B., Yang, B.-Y.: Asymptotic behaviour of the degree of regularity of semi-regular polynomial systems. Presented at MEGA\u201905, Eighth International Symposium on Effective Methods in Algebraic Geometry (2005)"},{"key":"399_CR17","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 $$\\mathbb{F}_2$$. In: Cryptographic Hardware and Embedded Systems\u2014CHES 2010. 12th International Workshop, Santa Barbara, USA, August 17\u201320, 2010. Proceedings, pp. 203\u2013218. Springer, Berlin (2010)"},{"issue":"1","key":"399_CR18","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.jco.2012.07.001","volume":"29","author":"M Bardet","year":"2013","unstructured":"Bardet, M., Faugere, J.-C., Salvy, B., Spaenlehauer, P.-J.: On the complexity of solving quadratic Boolean systems. J. Compl. 29(1), 53\u201375 (2013)","journal-title":"J. Compl."},{"key":"399_CR19","unstructured":"Joux, A., Vitse, V.: A crossbred algorithm for solving Boolean polynomial systems, Cryptology ePrint Archive, Report 2017\/372 (2017). https:\/\/eprint.iacr.org\/2017\/372. Accessed 23 Mar 2019"},{"key":"399_CR20","series-title":"The Series Discrete Mathematics and Its Applications","doi-asserted-by":"publisher","DOI":"10.1201\/9781439832905","volume-title":"Handbook of Discrete and Combinatorial Mathematics","author":"KH Rosen","year":"1999","unstructured":"Rosen, K.H.: Handbook of Discrete and Combinatorial Mathematics. The Series Discrete Mathematics and Its Applications. Taylor & Francis, London (1999)"},{"key":"399_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-35651-8","volume-title":"Ideals, Varieties and Algorithms","author":"D Cox","year":"2007","unstructured":"Cox, D., Little, J., O\u2019Shea, D.: Ideals, Varieties and Algorithms, 3rd edn. Springer, Berlin (2007)","edition":"3"},{"key":"399_CR22","volume-title":"Using Algebraic Geometry GTM 185","author":"D Cox","year":"2005","unstructured":"Cox, D., Little, J., O\u2019Shea, D.: Using Algebraic Geometry GTM 185. Springer, Berlin (2005)"},{"key":"399_CR23","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-93806-4","volume-title":"Gr\u00f6bner Bases, Coding and Cryptography","author":"M Sala","year":"2009","unstructured":"Sala, M., Mora, T., Perret, L., Sakata, S., Traverso, C.: Gr\u00f6bner Bases, Coding and Cryptography. Springer, New York (2009)"},{"key":"399_CR24","doi-asserted-by":"crossref","unstructured":"Faugere, 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, pp. 75\u201383. ACM, New York (2002)","DOI":"10.1145\/780506.780516"},{"key":"399_CR25","unstructured":"Stegers, T.: Faugere\u2019s F5 Algorithm Revisited, Thesis For The Degree Of Diplom-Mathematiker, Department of Mathematics, Technische Universit\u00e4t Darmstadt, 2005. http:\/\/sciencedocbox.com\/Physics\/68613748-Faugere-s-f5-algorithm-revisited.html"},{"key":"399_CR26","volume-title":"Handbook of Discrete and Combinatorial Mathematics","author":"Kenneth H Rosen","year":"2017","unstructured":"Rosen, Kenneth H.: Handbook of Discrete and Combinatorial Mathematics, 2nd edn. CRC Press, Boca Raton (2017)","edition":"2"},{"key":"399_CR27","doi-asserted-by":"crossref","unstructured":"Raddum, H., R\u00f8njom, S.: On the Number of Linearly Independent Equations Generated by XL, Sequences and Their Applications (SETA) 2008, LNCS 5203. Springer, pp. 239\u2013251 (2008)","DOI":"10.1007\/978-3-540-85912-3_22"},{"key":"399_CR28","doi-asserted-by":"crossref","unstructured":"Yang, B.-Y., Chen, J.-M.: Theoretical analysis of XL over small fields. In: Australasian Conference on Information Security and Privacy (ACISP) 2004, LNCS 3108. Springer, pp. 277\u2013288 (2004)","DOI":"10.1007\/978-3-540-27800-9_24"}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-019-00399-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00200-019-00399-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-019-00399-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,5]],"date-time":"2021-02-05T15:26:14Z","timestamp":1612538774000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00200-019-00399-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,8,17]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["399"],"URL":"https:\/\/doi.org\/10.1007\/s00200-019-00399-7","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"value":"0938-1279","type":"print"},{"value":"1432-0622","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,8,17]]},"assertion":[{"value":"21 October 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 March 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 August 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 August 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}