{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,14]],"date-time":"2026-04-14T00:47:23Z","timestamp":1776127643657,"version":"3.50.1"},"reference-count":37,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2022,2,1]],"date-time":"2022-02-01T00:00:00Z","timestamp":1643673600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/journals\/pages\/open_access\/funder_policies\/chorus\/standard_publication_model"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61972048"],"award-info":[{"award-number":["61972048"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61976024"],"award-info":[{"award-number":["61976024"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"BUPT Excellent Ph.D. Students Foundation","award":["CX2019207"],"award-info":[{"award-number":["CX2019207"]}]},{"DOI":"10.13039\/501100004543","name":"China Scholarship Council","doi-asserted-by":"publisher","award":["202006470082"],"award-info":[{"award-number":["202006470082"]}],"id":[{"id":"10.13039\/501100004543","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012226","name":"Fundamental Research Funds for the Central Universities","doi-asserted-by":"publisher","award":["2019XD-A01"],"award-info":[{"award-number":["2019XD-A01"]}],"id":[{"id":"10.13039\/501100012226","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100013314","name":"111 Project","doi-asserted-by":"publisher","award":["B21049"],"award-info":[{"award-number":["B21049"]}],"id":[{"id":"10.13039\/501100013314","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023,5,19]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>By introducing the BHT algorithm into the slide attack on 1K-AES and the related-key attack on PRINCE, we present the corresponding quantum attacks in this paper. In the proposed quantum attacks, we generalize the BHT algorithm to the situation where the number of marked items is unknown ahead of time. Moreover, we give an implementation scheme of classifier oracle based on Quantum Phase Estimation algorithm in presented quantum attacks. The complexity analysis shows that the query complexity, time complexity and memory complexity of the presented quantum attacks are all $\\mathcal{O}(2^{n\/3})$ when the success probability is about $63\\%$, where $n$ is the block size. Compared with the corresponding classical attacks, the proposed quantum attacks can achieve subquadratic speed-up under the same success probability no matter on query complexity, time complexity or memory complexity. Furthermore, the query complexity of the proposed quantum slide attack on 1K-AES is less than Grover search on 1K-AES by a factor of $2^{n\/6}.$ When compared with the Grover search on PRINCE, the query complexity of the presented quantum attack on PRINCE is reduced from $\\mathcal{O}(2^{n})$ to $\\mathcal{O}(2^{n\/2}).$ When compared with the combination of Grover and Simon\u2019s algorithms on PRINCE, the query complexity of our quantum attack on PRINCE is reduced from $\\mathcal{O}(n\\cdot 2^{n\/2})$ to $\\mathcal{O}(2^{n\/2}).$ Besides, the proposed quantum slide attack on 1K-AES indicates that the quantum slide attack could also be applied on Substitution-Permutation Network construction, apart from the iterated Even-Mansour cipher and Feistel constructions.<\/jats:p>","DOI":"10.1093\/comjnl\/bxab216","type":"journal-article","created":{"date-parts":[[2021,12,24]],"date-time":"2021-12-24T12:07:08Z","timestamp":1640347628000},"page":"1102-1110","source":"Crossref","is-referenced-by-count":13,"title":["Quantum Attacks on 1K-AES and PRINCE"],"prefix":"10.1093","volume":"66","author":[{"given":"Bin-Bin","family":"Cai","sequence":"first","affiliation":[{"name":"State Key Laboratory of Networking and Switching Technology , Beijing University of Posts and Telecommunications, Beijing, 100876, China"},{"name":"State Key Laboratory of Cryptology , P.O. Box 5159, Beijing, 100878, China"}]},{"given":"Yusen","family":"Wu","sequence":"additional","affiliation":[{"name":"Department of Physics , The University of Western Australia, Perth, WA 6009, Australia"}]},{"given":"Jing","family":"Dong","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Networking and Switching Technology , Beijing University of Posts and Telecommunications, Beijing, 100876, China"}]},{"given":"Su-Juan","family":"Qin","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Networking and Switching Technology , Beijing University of Posts and Telecommunications, Beijing, 100876, China"}]},{"given":"Fei","family":"Gao","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Networking and Switching Technology , Beijing University of Posts and Telecommunications, Beijing, 100876, China"}]},{"given":"Qiao-Yan","family":"Wen","sequence":"additional","affiliation":[{"name":"State Key Laboratory of Networking and Switching Technology , Beijing University of Posts and Telecommunications, Beijing, 100876, China"}]}],"member":"286","published-online":{"date-parts":[[2022,2,1]]},"reference":[{"key":"2023052000433825700_ref1","volume-title":"Quantum computation and quantum information","author":"Nielsen","year":"2010"},{"key":"2023052000433825700_ref2","doi-asserted-by":"crossref","first-page":"15023:1","DOI":"10.1038\/npjqi.2015.23","article-title":"Quantum algorithms: an overview","volume":"2","author":"Montanaro","year":"2016","journal-title":"NPJ Quantum Inf."},{"key":"2023052000433825700_ref3","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevLett.118.010501","article-title":"Optimal Hamiltonian simulation by quantum signal processing","volume":"118","author":"Low","year":"2017","journal-title":"Phys. Rev. Lett."},{"key":"2023052000433825700_ref4","doi-asserted-by":"crossref","first-page":"1484","DOI":"10.1137\/S0097539795293172","article-title":"Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer","volume":"26","author":"Shor","year":"1997","journal-title":"SIAM J. Comput."},{"key":"2023052000433825700_ref5","first-page":"212","volume-title":"A fast quantum mechanical algorithm for database search","author":"Grover","year":"1996"},{"key":"2023052000433825700_ref6","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1090\/conm\/305\/05215","article-title":"Quantum amplitude amplification and estimation","volume":"305","author":"Brassard","year":"2002","journal-title":"Contemp. Math."},{"key":"2023052000433825700_ref7","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevLett.103.150502","article-title":"Quantum algorithm for linear systems of equations","volume":"103","author":"Harrow","year":"2009","journal-title":"Phys. Rev. Lett."},{"key":"2023052000433825700_ref8","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevA.97.062322","article-title":"Asymptotic quantum algorithm for the Toeplitz systems","volume":"97","author":"Wan","year":"2018","journal-title":"Phys. Rev. A"},{"key":"2023052000433825700_ref9","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevA.94.042311","article-title":"Quantum algorithm for association rules mining","volume":"94","author":"Yu","year":"2016","journal-title":"Phys. Rev. A"},{"key":"2023052000433825700_ref10","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevA.99.022301","article-title":"Quantum algorithm for visual tracking","volume":"99","author":"Yu","year":"2019","journal-title":"Phys. Rev. A"},{"key":"2023052000433825700_ref11","doi-asserted-by":"crossref","DOI":"10.1007\/s11128-019-2364-9","article-title":"Quantum data compression by principal component analysis","volume":"18","author":"Yu","year":"2019","journal-title":"Quantum Inf. Process"},{"key":"2023052000433825700_ref12","first-page":"858","article-title":"An improved quantum algorithm for ridge regression","volume":"33","author":"Yu","year":"2021","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"2023052000433825700_ref13","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevA.102.052402","article-title":"Improved quantum algorithm for A-optimal projection","volume":"102","author":"Pan","year":"2020","journal-title":"Phys. Rev. A"},{"key":"2023052000433825700_ref14","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevA.104.022418","article-title":"Variational quantum algorithm for the Poisson equation","volume":"104","author":"Liu","year":"2021","journal-title":"Phys. Rev. A"},{"key":"2023052000433825700_ref15","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1109\/MSP.2018.3761719","article-title":"Quantum cryptanalysis: shor, grover, and beyond","volume":"16","author":"Jordan","year":"2018","journal-title":"IEEE Secur. Privacy"},{"key":"2023052000433825700_ref16","doi-asserted-by":"crossref","first-page":"1474","DOI":"10.1137\/S0097539796298637","article-title":"On the power of quantum computation","volume":"26","author":"Simon","year":"1997","journal-title":"SIAM J. Comput."},{"key":"2023052000433825700_ref17","first-page":"2682","volume-title":"Quantum distinguisher between the 3-round Feistel cipher and the random permutation","author":"Kuwakado","year":"2010"},{"key":"2023052000433825700_ref18","first-page":"312","volume-title":"International Symposium on Information Theory and its Applications","author":"Kuwakado","year":"2012"},{"key":"2023052000433825700_ref19","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/978-3-662-53008-5_8","volume-title":"Advances in Cryptology - CRYPTO 2016","author":"Kaplan","year":"2016"},{"key":"2023052000433825700_ref20","doi-asserted-by":"crossref","first-page":"1179","DOI":"10.1007\/s10623-020-00741-y","article-title":"Quantum attacks on some feistel block ciphers","volume":"88","author":"Dong","year":"2020","journal-title":"Designs Codes Cryptograph."},{"key":"2023052000433825700_ref21","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/978-3-319-70697-9_6","volume-title":"Advances in Cryptology - ASIACRYPT 2017","author":"Leander","year":"2017"},{"key":"2023052000433825700_ref22","doi-asserted-by":"crossref","first-page":"102501:1\u2013102501:7","DOI":"10.1007\/s11432-017-9468-y","article-title":"Quantum key-recovery attack on Feistel structures","volume":"61","author":"Dong","year":"2018","journal-title":"SCIENCE CHINA Inf. Sci."},{"key":"2023052000433825700_ref23","doi-asserted-by":"crossref","first-page":"22501:1-22501:12","DOI":"10.1007\/s11432-017-9436-7","article-title":"Quantum cryptanalysis on some generalized Feistel schemes","volume":"62","author":"Dong","year":"2019","journal-title":"SCIENCE CHINA Inf. Sci."},{"key":"2023052000433825700_ref24","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/978-3-030-35423-7_22","volume-title":"Progress in Cryptology - INDOCRYPT 2019","author":"Ni","year":"2019"},{"key":"2023052000433825700_ref25","first-page":"295","article-title":"Improved quantum attack on type-1 generalized Feistel schemes and its application to CAST-256","volume":"42","author":"Ni","year":"2020","journal-title":"J. Electron. Inf. Technol."},{"key":"2023052000433825700_ref26","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1007\/978-3-030-03326-2_19","volume-title":"Advances in Cryptology - ASIACRYPT 2018","author":"Bonnetain","year":"2018"},{"key":"2023052000433825700_ref27","doi-asserted-by":"crossref","first-page":"170","DOI":"10.1137\/S0097539703436345","article-title":"A subexponential-time quantum algorithm for the dihedral hidden subgroup problem","volume":"35","author":"Kuperberg","year":"2005","journal-title":"SIAM J. Comput."},{"key":"2023052000433825700_ref28","first-page":"65","article-title":"Quantum period finding based on the Bernstein-Vazirani algorithm","volume":"20","author":"Hao","year":"2020","journal-title":"Quantum Inf. Comput."},{"key":"2023052000433825700_ref29","doi-asserted-by":"crossref","first-page":"1411","DOI":"10.1137\/S0097539796300921","article-title":"Quantum complexity theory","volume":"26","author":"Bernstein","year":"1997","journal-title":"SIAM J. Comput."},{"key":"2023052000433825700_ref30","first-page":"163","volume-title":"Theoretical Informatics","author":"Brassard","year":"1998"},{"key":"2023052000433825700_ref31","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1007\/s00145-017-9266-8","article-title":"Efficient slide attacks","volume":"31","author":"Bar-On","year":"2018","journal-title":"J. Cryptol."},{"key":"2023052000433825700_ref32","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1002\/(SICI)1521-3978(199806)46:4\/5<493::AID-PROP493>3.0.CO;2-P","article-title":"Tight bounds on quantum searching","volume":"46","author":"Boyer","year":"1996","journal-title":"Fortschritte Der Physik (Prog. Phy.)"},{"key":"2023052000433825700_ref33","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-04722-4","volume-title":"The Design of Rijndael: AES - The Advanced Encryption Standard","author":"Daemen","year":"2002"},{"key":"2023052000433825700_ref34","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1007\/978-3-642-34961-4_14","volume-title":"Advances in Cryptology - ASIACRYPT 2012","author":"Borghoff","year":"2012"},{"key":"2023052000433825700_ref35","first-page":"92","volume-title":"Fast Software Encryption 2013","author":"Jean","year":"2013"},{"key":"2023052000433825700_ref36","doi-asserted-by":"crossref","DOI":"10.1007\/s11128-017-1515-0","article-title":"Quantum Fourier transform in computational basis","volume":"16","author":"Zhou","year":"2017","journal-title":"Quantum Inf. Process"},{"key":"2023052000433825700_ref37","doi-asserted-by":"crossref","DOI":"10.1103\/PhysRevLett.100.160501","article-title":"Quantum random access memory","volume":"100","author":"Giovannetti","year":"2008","journal-title":"Phys. Rev. Lett."}],"container-title":["The Computer Journal"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/5\/1102\/50397382\/bxab216.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/comjnl\/article-pdf\/66\/5\/1102\/50397382\/bxab216.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,20]],"date-time":"2023-05-20T00:44:17Z","timestamp":1684543457000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/comjnl\/article\/66\/5\/1102\/6518264"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,1]]},"references-count":37,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2022,2,1]]},"published-print":{"date-parts":[[2023,5,19]]}},"URL":"https:\/\/doi.org\/10.1093\/comjnl\/bxab216","relation":{},"ISSN":["0010-4620","1460-2067"],"issn-type":[{"value":"0010-4620","type":"print"},{"value":"1460-2067","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023,5]]},"published":{"date-parts":[[2022,2,1]]}}}