{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T11:07:49Z","timestamp":1772795269167,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,1,12]],"date-time":"2021-01-12T00:00:00Z","timestamp":1610409600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,1,12]],"date-time":"2021-01-12T00:00:00Z","timestamp":1610409600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Syst Sci Complex"],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s11424-020-0028-6","type":"journal-article","created":{"date-parts":[[2021,1,13]],"date-time":"2021-01-13T03:31:44Z","timestamp":1610508704000},"page":"373-412","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":18,"title":["Quantum Algorithm for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems"],"prefix":"10.1007","volume":"35","author":[{"given":"Yu-Ao","family":"Chen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiao-Shan","family":"Gao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,1,12]]},"reference":[{"issue":"15","key":"28_CR1","doi-asserted-by":"publisher","first-page":"150502","DOI":"10.1103\/PhysRevLett.103.150502","volume":"103","author":"A W Harrow","year":"2009","unstructured":"Harrow A W, Hassidim A, and Lloyd S, Quantum algorithm for linear systems of equations, Physical Review Letters, 2009, 103(15): 150502.","journal-title":"Physical Review Letters"},{"key":"28_CR2","unstructured":"Ambainis A, Variable time amplitude amplification and a faster quantum algorithm for solving systems of linear equations, Proc. STACS, 2012, 636\u2013647."},{"issue":"6","key":"28_CR3","doi-asserted-by":"publisher","first-page":"1920","DOI":"10.1137\/16M1087072","volume":"46","author":"A M Childs","year":"2017","unstructured":"Childs A M, Kothari R, and Somma R D, Quantum algorithm for systems of linear equations with exponentially improved dependence on precision, SIAM J. Comput., 2017, 46(6): 1920\u20131950.","journal-title":"SIAM J. Comput."},{"key":"28_CR4","volume-title":"Multivariate Public Key Cryptosystems","author":"J Ding","year":"2006","unstructured":"Ding J, Gower J E, and Schmidt D S, Multivariate Public Key Cryptosystems, Springer, New York, 2006."},{"key":"28_CR5","doi-asserted-by":"crossref","unstructured":"Murphy S and Robshaw M, Essential algebraic structure within the AES, CRYPTO\u201902, 2002, 1\u201316.","DOI":"10.1007\/3-540-45708-9_1"},{"key":"28_CR6","unstructured":"Teo S G, Wong K K H, Bartlett H, et al., Algebraic analysis of Trivium-like ciphers, Proceedings of the Twelfth Australasian Information Security Conference-Volume 149 Australian Computer Society, Inc., 2014, 77\u201381."},{"key":"28_CR7","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48865-2","volume-title":"Boolean Functions and Their Applications in Cryptography","author":"C K Wu","year":"2016","unstructured":"Wu C K and Feng D, Boolean Functions and Their Applications in Cryptography, Springer, New York, 2016."},{"issue":"1","key":"28_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1112\/plms\/s1-35.1.3","volume":"35","author":"F S Macaulay","year":"1902","unstructured":"Macaulay F S, Some formulas in elimination, Proc. of the London Mathematical Society, 1902, 35(1): 3\u201338.","journal-title":"Proc. of the London Mathematical Society"},{"key":"28_CR9","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), J. Pure. Appl. Algebra, 1999, 139: 61\u201388.","journal-title":"J. Pure. Appl. Algebra"},{"key":"28_CR10","first-page":"392","volume":"1807","author":"N Courtois","year":"2000","unstructured":"Courtois N, Klimov A, Patarin J, et al., Efficient algorithms for solving overdefined systems of multivariate polynomial equations, Eurocrypt\u201900, LNCS, Springer, Berlin, 2000, 1807: 392\u2013407.","journal-title":"Eurocrypt\u201900, LNCS, Springer, Berlin"},{"key":"28_CR11","first-page":"146","volume":"162","author":"D Lazard","year":"1983","unstructured":"Lazard D, Gr\u00f6bner bases, Gaussian elimination and resolution of systems of algebraic equations, Proc. Eurocal 83, LNCS, Springer, Berlin, 1983, 162: 146\u2013156.","journal-title":"Proc. Eurocal 83, LNCS, Springer, Berlin"},{"key":"28_CR12","unstructured":"Caminata A and Gorla E, Solving multivariate polynomial systems and an invariant from commutative algebra, 2017, arXiv: 1706.06319."},{"key":"28_CR13","first-page":"20","volume-title":"Proc. STOC\u201903","author":"D Aharonov","year":"2003","unstructured":"Aharonov D and Ta-Shma A, Adiabatic quantum state generation and statistical zero knowledge, Proc. STOC\u201903, ACM Press, New York, 2003, 20\u201329."},{"key":"28_CR14","doi-asserted-by":"publisher","first-page":"1675","DOI":"10.1080\/00268976.2012.668289","volume":"110","author":"Y Cao","year":"2012","unstructured":"Cao Y, Daskin A, Frankel S, et al., Quantum circuit design for solving linear systems of equations, Molecular Physics, 2012, 110: 1675\u20131680.","journal-title":"Molecular Physics"},{"key":"28_CR15","doi-asserted-by":"crossref","unstructured":"Grover L K, A fast quantum mechanical algorithm for database search, Proc. STOC\u201996, ACM Press, 1996, 212\u2013219.","DOI":"10.1145\/237814.237866"},{"key":"28_CR16","first-page":"303","volume":"10076","author":"P Schwabe","year":"2016","unstructured":"Schwabe P and Westerbaan B, Solving binary MQ with Grover\u2019s algorithm, SPACE\u201916, LNCS, 2016, 10076: 303\u2013322.","journal-title":"SPACE\u201916, LNCS"},{"key":"28_CR17","unstructured":"Faugere J C, Horan K, Kahrobaei D, et al., Fast quantum algorithm for solving multivariate quadratic equations, 2017, arXiv: 1712.07211."},{"key":"28_CR18","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/978-3-319-29360-8_3","volume-title":"International Workshop on Post-Quantum Cryptography Post-Quantum Cryptography","author":"M Grassl","year":"2016","unstructured":"Grassl M, Langenberg B, Roetteler M, et al., Applying Grover\u2019s algorithm to AES: Quantum resource estimates, International Workshop on Post-Quantum Cryptography Post-Quantum Cryptography, Springer, New York, 2016, 29\u201343."},{"key":"28_CR19","doi-asserted-by":"crossref","unstructured":"Berry D W, Childs A M, and Kothari R, Hamiltonian simulation with nearly optimal dependence on all parameters, Proc. 56th FOCS, 2015, 792\u2013809.","DOI":"10.1109\/FOCS.2015.54"},{"issue":"2","key":"28_CR20","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/s00220-006-0150-x","volume":"270","author":"D W Berry","year":"2007","unstructured":"Berry D W, Ahokas G, Cleve R, et al., Efficient quantum algorithms for simulating sparse Hamiltonians, Communications in Mathematical Physics, 2007, 270(2): 359\u2013371.","journal-title":"Communications in Mathematical Physics"},{"key":"28_CR21","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-6911-1","volume-title":"Using Algebraic Geometry","author":"D Cox","year":"1998","unstructured":"Cox D, Little J, and O\u2019Shea D, Using Algebraic Geometry, Springer, New York, 1998."},{"key":"28_CR22","volume-title":"AES Proposal: Rijndael","author":"J Daemen","year":"1999","unstructured":"Daemen J and Rijmen V, AES Proposal: Rijndael, NIST, Maryland, 1999."},{"key":"28_CR23","unstructured":"Chen Y A and Gao X S, Quantum algorithms for Boolean equation solving and quantum algebraic attack on cryptosystems, 2017, arXiv: 1712.06239."},{"key":"28_CR24","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-540-68351-3_18","volume":"4986","author":"C D Canni\u00e9re","year":"2008","unstructured":"Canni\u00e9re C D and Preneel B, Trivium, New Stream Cipher Designs: The eSTREAM Finalists, LNCS, Springer, 2008, 4986: 244\u2013266.","journal-title":"New Stream Cipher Designs: The eSTREAM Finalists, LNCS, Springer"},{"key":"28_CR25","first-page":"30","volume":"3","author":"G Bertoni","year":"2009","unstructured":"Bertoni G, Daemen J, Peeters M, et al., Keccak sponge function family main document, Submission to NIST (Round 2), 2009, 3: 30.","journal-title":"Submission to NIST (Round 2)"},{"key":"28_CR26","doi-asserted-by":"crossref","unstructured":"Song L, Liao G, and Guo J, Non-full Sbox linearization: Applications to collision attacks on round-reduced Keccak, CRYPTO\u201917, Springer, 2017, 428\u2013451.","DOI":"10.1007\/978-3-319-63715-0_15"},{"key":"28_CR27","doi-asserted-by":"crossref","unstructured":"Huang S, Wang X, Xu G, et al., Conditional cube attack on reduced-round Keccak sponge function, EUROCRYPT 2017, Springer, 2017, 259\u2013288.","DOI":"10.1007\/978-3-319-56614-6_9"},{"key":"28_CR28","unstructured":"Yasuda T, Dahan X, Huang Y J, et al., MQ Challenge: Hardness evaluation of solving multivariate quadratic problems, The NIST Workshop on Cybersecurity in a Post-Quantum World, 2015, https:\/\/www.mqchallenge.org\/."},{"issue":"1","key":"28_CR29","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, et al., On the complexity of solving quadratic Boolean systems, Journal of Complexity, 2013, 29(1): 53\u201375.","journal-title":"Journal of Complexity"},{"key":"28_CR30","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1016\/j.jsc.2011.12.025","volume":"47","author":"X S Gao","year":"2012","unstructured":"Gao X S and Huang Z, Characteristic set algorithms for equation solving in finite fields, Journal of Symbolic Computation, 2012, 47: 655\u2013679.","journal-title":"Journal of Symbolic Computation"},{"key":"28_CR31","unstructured":"Chen Y A, Gao X S, and Yuan C M, Quantum algorithms for optimization and polynomial systems Sslving over finite fields, 2018, arXiv: 1802.03856."},{"key":"28_CR32","volume-title":"Spectral Graph Theory","author":"F R Chung","year":"1997","unstructured":"Chung F R and Graham F C, Spectral Graph Theory, American Mathematical Soc., Providence, 1997."},{"issue":"2","key":"28_CR33","doi-asserted-by":"publisher","first-page":"298","DOI":"10.21136\/CMJ.1973.101168","volume":"23","author":"M Fiedler","year":"1973","unstructured":"Fiedler M, Algebraic connectivity of graphs, Czechoslovak Mathematical Journal, 1973, 23(2): 298\u2013305.","journal-title":"Czechoslovak Mathematical Journal"},{"issue":"1","key":"28_CR34","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.laa.2006.08.017","volume":"423","author":"N M M De Abreu","year":"2007","unstructured":"De Abreu N M M, Old and new results on algebraic connectivity of graphs, Linear Algebra and Its Applications, 2007, 423(1): 53\u201373.","journal-title":"Linear Algebra and Its Applications"},{"issue":"2","key":"28_CR35","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1080\/03081088508817681","volume":"18","author":"W N Anderson","year":"1985","unstructured":"Anderson W N and Morley T D, Eigenvalues of the Laplacian of a graph, Linear and Multilinear Algebra, 1985, 18(2): 141\u2013145.","journal-title":"Linear and Multilinear Algebra"}],"container-title":["Journal of Systems Science and Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11424-020-0028-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11424-020-0028-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11424-020-0028-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,6]],"date-time":"2022-02-06T12:03:44Z","timestamp":1644149024000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11424-020-0028-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1,12]]},"references-count":35,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["28"],"URL":"https:\/\/doi.org\/10.1007\/s11424-020-0028-6","relation":{},"ISSN":["1009-6124","1559-7067"],"issn-type":[{"value":"1009-6124","type":"print"},{"value":"1559-7067","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1,12]]},"assertion":[{"value":"20 February 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 January 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}