{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,26]],"date-time":"2025-10-26T15:07:53Z","timestamp":1761491273012},"reference-count":44,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2021,8,2]],"date-time":"2021-08-02T00:00:00Z","timestamp":1627862400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,8,2]],"date-time":"2021-08-02T00:00:00Z","timestamp":1627862400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cybersecur"],"published-print":{"date-parts":[[2021,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The quantum security of lightweight block ciphers is receiving more and more attention. However, the existing quantum attacks on lightweight block ciphers only focused on the quantum exhaustive search, while the quantum attacks combined with classical cryptanalysis methods haven\u2019t been well studied. In this paper, we study quantum key recovery attack on SIMON32\/64 using Quantum Amplitude Amplification algorithm in Q1 model. At first, we reanalyze the quantum circuit complexity of quantum exhaustive search on SIMON32\/64. We estimate the Clifford gates count more accurately and reduce the T gate count. Also, the T-depth and full depth is reduced due to our minor modifications. Then, using four differentials given by Biryukov in FSE 2014 as our distinguisher, we give our quantum key recovery attack on 19-round SIMON32\/64. We treat the two phases of key recovery attack as two QAA instances separately, and the first QAA instance consists of four sub-QAA instances. Then, we design the quantum circuit of these two QAA instances and estimate their corresponding quantum circuit complexity. We conclude that the quantum circuit of our quantum key recovery attack is lower than quantum exhaustive search. Our work firstly studies the quantum dedicated attack on SIMON32\/64. And this is the first work to study the complexity of quantum dedicated attacks from the perspective of quantum circuit complexity, which is a more fine-grained analysis of quantum dedicated attacks\u2019 complexity.<\/jats:p>","DOI":"10.1186\/s42400-021-00089-3","type":"journal-article","created":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T23:03:25Z","timestamp":1627859005000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Quantum key recovery attack on SIMON32\/64"],"prefix":"10.1186","volume":"4","author":[{"given":"Hui","family":"Liu","sequence":"first","affiliation":[]},{"given":"Li","family":"Yang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,8,2]]},"reference":[{"key":"89_CR1","doi-asserted-by":"publisher","unstructured":"Abed, F, List E, Lucks S, Wenzel J (2014). International Workshop on Fast Software Encryption. https:\/\/doi.org\/10.1109\/access.2019.2894337.","DOI":"10.1109\/access.2019.2894337"},{"key":"89_CR2","doi-asserted-by":"crossref","first-page":"112","DOI":"10.1007\/s11128-018-1864-3","volume":"17","author":"M Almazrooie","year":"2018","unstructured":"Almazrooie, M, Samsudin A, Abdullah R, Mutter KN (2018) Quantum reversible circuit of aes-128. Quantum Inform Process 17:112.","journal-title":"Quantum Inform Process"},{"key":"89_CR3","doi-asserted-by":"crossref","first-page":"818","DOI":"10.1109\/TCAD.2013.2244643","volume":"32","author":"M Amy","year":"2013","unstructured":"Amy, M, Maslov D, Mosca M, Roetteler M (2013) A meet-in-the-middle algorithm for fast synthesis of depth-optimal quantum circuits. IEEE Trans Comput-Aided Des Integr Circ Syst 32:818\u2013830.","journal-title":"IEEE Trans Comput-Aided Des Integr Circ Syst"},{"key":"89_CR4","unstructured":"Anand, R, Maitra A, Mukhopadhyay S (2020a). https:\/\/github.com\/raviro\/quantsimon. Accessed 05 March 2021."},{"key":"89_CR5","doi-asserted-by":"publisher","unstructured":"Anand, R, Maitra A, Mukhopadhyay S (2020b) Evaluation of quantum cryptanalysis on speck. International Conference on Cryptology in India. https:\/\/doi.org\/10.1007\/978-3-030-65277-7_18.","DOI":"10.1007\/978-3-030-65277-7_18"},{"key":"89_CR6","unstructured":"Anand, R, Maitra A, Mukhopadhyay S (2020c) Grover on simon. arXiv preprint arXiv:200410686."},{"key":"89_CR7","first-page":"585","volume":"2015","author":"R Beaulieu","year":"2015","unstructured":"Beaulieu, R, Shors D, Smith J, Treatman-Clark S, Weeks B, Wingers L (2015) Simon and speck: Block ciphers for the internet of things. IACR Cryptol ePrint Arch 2015:585.","journal-title":"IACR Cryptol ePrint Arch"},{"key":"89_CR8","doi-asserted-by":"publisher","unstructured":"Beierle, C, Jean J, K\u00f6lbl S, Leander G, Moradi A, Peyrin T, Sasaki Y, Sasdrich P, Sim SM (2016) The skinny family of block ciphers and its low-latency variant mantis In: Annual International Cryptology Conference, 123\u2013153. https:\/\/doi.org\/10.1007\/978-3-662-53008-5_5.","DOI":"10.1007\/978-3-662-53008-5_5"},{"issue":"5","key":"89_CR9","doi-asserted-by":"crossref","first-page":"1411","DOI":"10.1137\/S0097539796300921","volume":"26","author":"E Bernstein","year":"1997","unstructured":"Bernstein, E, Vazirani U (1997) Quantum complexity theory. SIAM J Comput 26(5):1411\u20131473.","journal-title":"SIAM J Comput"},{"key":"89_CR10","doi-asserted-by":"publisher","unstructured":"Biryukov, A, Roy A, Velichkov V (2014) Differential analysis of block ciphers simon and speck, 546\u2013570.. International Workshop on Fast Software Encryption. https:\/\/doi.org\/10.1007\/978-3-662-46706-0_28.","DOI":"10.1007\/978-3-662-46706-0_28"},{"key":"89_CR11","doi-asserted-by":"crossref","unstructured":"Bogdanov, A, Knudsen LR, Leander G, Paar C, Poschmann A, Robshaw MJ, Seurin Y, Vikkelsoe C (2007) Present: An ultra-lightweight block cipher, 450\u2013466.. Springer, Berlin.","DOI":"10.1007\/978-3-540-74735-2_31"},{"key":"89_CR12","doi-asserted-by":"publisher","unstructured":"Bonnetain, X, Naya-Plasencia M, Schrottenloher A (2019) Quantum security analysis of AES. IACR Trans Symmetric Cryptol:55\u201393. https:\/\/doi.org\/10.46586\/tosc.v2019.i2.55-93.","DOI":"10.46586\/tosc.v2019.i2.55-93"},{"key":"89_CR13","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1090\/conm\/305\/05215","volume":"305","author":"G Brassard","year":"2002","unstructured":"Brassard, G, Hoyer P, Mosca M, Tapp A (2002) Quantum amplitude amplification and estimation. Contemp Math 305:53\u201374.","journal-title":"Contemp Math"},{"key":"89_CR14","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1007\/978-3-662-52993-5_22","volume-title":"International Conference on Fast Software Encryption","author":"H Chen","year":"2016","unstructured":"Chen, H, Wang X (2016) Improved linear hull attack on round-reduced simon with dynamic key-guessing techniques In: International Conference on Fast Software Encryption, 428\u2013449.. Springer, Berlin."},{"key":"89_CR15","doi-asserted-by":"publisher","unstructured":"Chu, Z, Chen H, Wang X, Dong X, Li L (2018) Improved integral attacks on simon32 and simon48 with dynamic key-guessing techniques. Secur Commun Netw:2018. https:\/\/doi.org\/10.1155\/2018\/5160237.","DOI":"10.1155\/2018\/5160237"},{"key":"89_CR16","doi-asserted-by":"crossref","unstructured":"Dong, X, Dong B, Wang X (2020a) Quantum attacks on some feistel block ciphers. Designs. Codes Crypt 88:1\u201325.","DOI":"10.1007\/s10623-020-00741-y"},{"key":"89_CR17","doi-asserted-by":"publisher","unstructured":"Dong, X, Sun S, Shi D, Gao F, Wang X, Hu L (2020b) Quantum collision attacks on aes-like hashing with low quantum random access memories In: International Conference on the Theory and Application of Cryptology and Information Security, 727\u2013757.. Springer. https:\/\/doi.org\/10.1007\/978-3-030-64834-3_25.","DOI":"10.1007\/978-3-030-64834-3_25"},{"key":"89_CR18","doi-asserted-by":"publisher","unstructured":"Grassl, M, Langenberg B, Roetteler M, Steinwandt R (2016) Applying grover\u2019s algorithm to AES: quantum resource estimates. Post-Quantum Cryptography. https:\/\/doi.org\/10.1007\/978-3-319-29360-8_3.","DOI":"10.1007\/978-3-319-29360-8_3"},{"key":"89_CR19","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1103\/PhysRevLett.79.325","volume":"79","author":"LK Grover","year":"1997","unstructured":"Grover, LK (1997) Quantum mechanics helps in searching for a needle in a haystack. Phys Rev Lett 79:325.","journal-title":"Phys Rev Lett"},{"key":"89_CR20","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1007\/978-3-319-98113-0_21","volume-title":"International Conference on Security and Cryptography for Networks","author":"A Hosoyamada","year":"2018","unstructured":"Hosoyamada, A, Sasaki Y (2018) Quantum demiric-sel\u00e7uk meet-in-the-middle attacks: applications to 6-round generic feistel constructions In: International Conference on Security and Cryptography for Networks, 386\u2013403.. Springer, Cham."},{"key":"89_CR21","doi-asserted-by":"crossref","unstructured":"Hosoyamada, A, Sasaki Y (2020) Finding hash collisions with quantum computers by using differential trails with smaller probability than birthday bound In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, 249\u2013279.. Springer.","DOI":"10.1007\/978-3-030-45724-2_9"},{"key":"89_CR22","doi-asserted-by":"crossref","first-page":"6407","DOI":"10.3390\/app10186407","volume":"10","author":"K Jang","year":"2020","unstructured":"Jang, K, Choi S, Kwon H, Kim H, Park J, Seo H (2020) Grover on korean block ciphers. Appl Sci 10:6407.","journal-title":"Appl Sci"},{"key":"89_CR23","doi-asserted-by":"publisher","unstructured":"Jaques, S, Naehrig M, Roetteler M, Virdia F (2020) Implementing grover oracles for quantum key search on AES and lowmc In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, 280\u2013310. https:\/\/doi.org\/10.1007\/978-3-030-45724-2_10.","DOI":"10.1007\/978-3-030-45724-2_10"},{"key":"89_CR24","doi-asserted-by":"publisher","unstructured":"Kaplan, M, Leurent G, Leverrier A, Naya-Plasencia M (2016a) Breaking symmetric cryptosystems using quantum period finding In: Annual International Cryptology Conference, 207\u2013237. https:\/\/doi.org\/10.1007\/978-3-662-53008-5_8.","DOI":"10.1007\/978-3-662-53008-5_8"},{"key":"89_CR25","doi-asserted-by":"publisher","unstructured":"Kaplan, M, Leurent G, Leverrier A, Naya-Plasencia M (2016b) Quantum differential and linear cryptanalysis. IACR Trans Symmetric Cryptol:71\u201394. https:\/\/doi.org\/10.46586\/tosc.v2016.i1.71-94.","DOI":"10.46586\/tosc.v2016.i1.71-94"},{"key":"89_CR26","unstructured":"Koch, D, Wessing L, Alsing PM (2019) Introduction to coding quantum algorithms: A tutorial series using pyquil. arXiv preprint arXiv:190305195."},{"key":"89_CR27","doi-asserted-by":"publisher","unstructured":"Kuwakado, H, Morii M (2010) Quantum distinguisher between the 3-round feistel cipher and the random permutation In: 2010 IEEE International Symposium on Information Theory, 2682\u20132685. https:\/\/doi.org\/10.1109\/isit.2010.5513654.","DOI":"10.1109\/isit.2010.5513654"},{"key":"89_CR28","first-page":"312","volume-title":"2012 International Symposium on Information Theory and its Applications","author":"H Kuwakado","year":"2012","unstructured":"Kuwakado, H, Morii M (2012) Security on the quantum-type even-mansour cipher In: 2012 International Symposium on Information Theory and its Applications, 312\u2013316.. IEEE, New York."},{"key":"89_CR29","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/TQE.2020.2965697","volume":"1","author":"B Langenberg","year":"2020","unstructured":"Langenberg, B, Pham H, Steinwandt R (2020) Reducing the cost of implementing the advanced encryption standard as a quantum circuit. IEEE Trans Quantum Eng 1:1\u201312.","journal-title":"IEEE Trans Quantum Eng"},{"key":"89_CR30","unstructured":"Lau I (2021). https:\/\/github.com\/aliceQuantum\/SIMONQ. Accessed 05 March 2021."},{"key":"89_CR31","first-page":"161","volume-title":"International Conference on the Theory and Application of Cryptology and Information Security","author":"G Leander","year":"2017","unstructured":"Leander, G, May A (2017) Grover meets simon\u2013quantumly attacking the fx-construction In: International Conference on the Theory and Application of Cryptology and Information Security, 161\u2013178.. Springer, Cham."},{"key":"89_CR32","doi-asserted-by":"publisher","unstructured":"Li, H, Yang L (2015) Quantum differential cryptanalysis to the block ciphers In: International Conference on Applications and Techniques in Information Security, 44\u201351. https:\/\/doi.org\/10.1007\/978-3-662-48683-2_5.","DOI":"10.1007\/978-3-662-48683-2_5"},{"issue":"2","key":"89_CR33","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1063\/1.1359716","volume":"54","author":"MA Nielsen","year":"2001","unstructured":"Nielsen, MA, Chuang IL (2001) Quantum computation and quantum information. Phys Today 54(2):60.","journal-title":"Phys Today"},{"key":"89_CR34","first-page":"134","volume":"16","author":"M Roetteler","year":"2016","unstructured":"Roetteler, M, Wiebe N (2016) Quantum arithmetic and numerical analysis using repeat-until-success circuits. Quantum Inform Comput 16:134\u2013178.","journal-title":"Quantum Inform Comput"},{"issue":"4","key":"89_CR35","doi-asserted-by":"crossref","first-page":"042,302","DOI":"10.1103\/PhysRevA.87.042302","volume":"87","author":"P Selinger","year":"2013","unstructured":"Selinger, P (2013) Quantum circuits of t-depth one. Phys Rev A 87(4):042,302.","journal-title":"Phys Rev A"},{"issue":"3","key":"89_CR36","first-page":"1","volume":"60","author":"D Shi","year":"2017","unstructured":"Shi, D, Hu L, Sun S, Song L, Qiao K, Ma X (2017). Improved linear (hull) cryptanalysis of round-reduced versions of simon. ence China(Information ences) 60(3):1\u20133.","journal-title":"Improved linear (hull) cryptanalysis of round-reduced versions of simon. ence China(Information ences)"},{"key":"89_CR37","doi-asserted-by":"publisher","unstructured":"Shor, PW (1994) Algorithms for quantum computation: discrete logarithms and factoring In: Proceedings 35th annual symposium on foundations of computer science, 124\u2013134. https:\/\/doi.org\/10.1109\/sfcs.1994.365700.","DOI":"10.1109\/sfcs.1994.365700"},{"key":"89_CR38","doi-asserted-by":"crossref","first-page":"1474","DOI":"10.1137\/S0097539796298637","volume":"26","author":"DR Simon","year":"1997","unstructured":"Simon, DR (1997) On the power of quantum computation. SIAM J Comput 26:1474\u20131483.","journal-title":"SIAM J Comput"},{"key":"89_CR39","doi-asserted-by":"publisher","unstructured":"Sun, L, Fu K, Wang M (2015) Improved zero-correlation cryptanalysis on simon In: International Conference on Information Security and Cryptology, 125\u2013143.. Springer. https:\/\/doi.org\/10.1007\/978-3-319-38898-4_8.","DOI":"10.1007\/978-3-319-38898-4_8"},{"key":"89_CR40","doi-asserted-by":"crossref","first-page":"098,103","DOI":"10.1007\/s11432-017-9231-5","volume":"61","author":"N Wang","year":"2018","unstructured":"Wang, N, Wang X, Jia K, Zhao J (2018) Differential attacks on reduced simon versions with dynamic key-guessing techniques. Sci China Inform Sci 61:098,103.","journal-title":"Sci China Inform Sci"},{"key":"89_CR41","doi-asserted-by":"publisher","unstructured":"Wang, Q, Liu Z, Var\u0131c\u0131 K, Sasaki Y, Rijmen V, Todo Y (2014) Cryptanalysis of reduced-round simon32 and simon48 In: International Conference on Cryptology in India, 143\u2013160. https:\/\/doi.org\/10.1007\/978-3-319-13039-2_9.","DOI":"10.1007\/978-3-319-13039-2_9"},{"key":"89_CR42","doi-asserted-by":"crossref","first-page":"1161","DOI":"10.1007\/s10623-018-0510-5","volume":"87","author":"H Xie","year":"2019","unstructured":"Xie, H, Yang L (2019) Using bernstein\u2013vazirani algorithm to attack block ciphers. Designs. Codes Crypt 87:1161\u20131182.","journal-title":"Codes Crypt"},{"key":"89_CR43","doi-asserted-by":"publisher","unstructured":"Zhandry, M (2012) How to construct quantum random functions In: 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, 679\u2013687. https:\/\/doi.org\/10.1109\/focs.2012.37.","DOI":"10.1109\/focs.2012.37"},{"key":"89_CR44","doi-asserted-by":"publisher","unstructured":"Zou, J, Wei Z, Sun S, Liu X, Wu W (2020) Quantum circuit implementations of AES with fewer qubits In: International Conference on the Theory and Application of Cryptology and Information Security, 697\u2013726.. Springer. https:\/\/doi.org\/10.1007\/978-3-030-64834-3_24.","DOI":"10.1007\/978-3-030-64834-3_24"}],"container-title":["Cybersecurity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-021-00089-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s42400-021-00089-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-021-00089-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,1]],"date-time":"2021-08-01T23:18:17Z","timestamp":1627859897000},"score":1,"resource":{"primary":{"URL":"https:\/\/cybersecurity.springeropen.com\/articles\/10.1186\/s42400-021-00089-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,2]]},"references-count":44,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["89"],"URL":"https:\/\/doi.org\/10.1186\/s42400-021-00089-3","relation":{},"ISSN":["2523-3246"],"issn-type":[{"value":"2523-3246","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,2]]},"assertion":[{"value":"27 December 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 April 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 August 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Not applicable.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"23"}}