Key Recovery Attacks on Block Cipher EM-Like Structures Based on Quantum Simon’s Algorithm

doi:10.3969/j.issn.1671-1122.2024.01.010

Abstract

Abstract:

This paper studied the quantum process of Quantum Simon’s algorithm (one of classical quantum cycle finding algorithms) as well as its applications, and conducts cryptanalysis based on quantum Simon algorithm on EM-like structures, takes the encryption algorithm of EM-like structures as the object of research, applies quantum Simon algorithm, constructs the function applicable to Simon algorithm, and performs the key recovery attack on the 5-round encryption process of the encrypted structure of EM-like structures. The results show that the fifth round of encryption key can be successfully recovered in polynomial time of the key length, and other keys can be analyzed based on this key. The key recovery indicates that the quantum version of the structure is insecure, i.e., one of the keys can be found at polynomial time of the key length. It provides some basis for future research and development of symmetric cryptosystems.

Key words: quantum, block cipher, Simon’s algorithm, key recovery attack

CLC Number:

TP309

ZHANG Xinglan, GUO Yankun, CHEN Fei, ZHANG Feng. Key Recovery Attacks on Block Cipher EM-Like Structures Based on Quantum Simon’s Algorithm[J]. Netinfo Security, 2024, 24(1): 106-112.

Figures/Tables 4

References 22

[1]	SHOR P. Algorithms for Quantum Computation: Discrete Logarithms and Factoring[C]// IEEE. 35th Annual Symposium on the Foundations of Computer Science. New York: IEEE, 1994: 124-134.
[2]	National Institute of Standards and Technology. Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process[EB/OL]. [2023-06-18]. https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf.
[3]	Grover L K. A Fast Quantum Mechanical Algorithm for Database Search[EB/OL]. (1996-11-19) [2023-06-18]. https://doi.org/10.48550/arXiv.quant-ph/9605043.
[4]	XIE Huiqin, YANG Li. A Quantum Related-Key Attack Based on the Bernstein-Vazirani Algorithm[EB/OL]. (2020-07-14) [2023-06-18]. https://link.springer.com/article/10.1007/s11128-020-02741-2.
[5]	KAPLAN M, LEURENT G, LEVERRIER A, et al. Quantum Differential and Linear Cryptanalysis[EB/OL]. (2017-05-07) [2023-06-18]. https://doi.org/10.48550/arXiv.1510.05836.
[6]	XIE Huiqin, YANG Li. Quantum Impossible Differential and Truncated Differential Cryptanalysis[EB/OL]. (2018-07-23) [2023-06-18]. https://doi.org/10.48550/arXiv.1712.06997.
[7]	VAZIRANI U. On the Power of Quantum Computation[J]. Philosophical Transactions Mathematical Physical & Engineering Sciences, 1998, 356(1743): 1759-1768.
[8]	KUWAKADO H, MORII M. Quantum Distinguisher between the 3-Round Feistel Cipher and the Random Permutation[C]// IEEE. IEEE International Symposium on Information Theory. New York: IEEE, 2010: 2682-2685.
[9]	KUWAKADO H, MORII M. Security on the Quantum-Type Even-Mansour Cipher[C]// IEEE. Information Theory and Its Applications (ISITA), 2012 International Symposium on. New York: IEEE, 2012: 312-316.
[10]	SANTOLI T, SCHAFFNER C. Using Simon's Algorithm to Attack Symmetric-Key Cryptographic Primitives[EB/OL]. (2017-01-31) [2023-06-18]. https://doi.org/10.48550/arXiv.1603.07856.
[11]	MALVIYA A K, TIWARI N, CHAWLA M. Quantum Cryptanalytic Attacks of Symmetric Ciphers: A Review[J]. Computers and Electrical Engineering, 2022: 101-109.
[12]	GUO Jian, JEAN J, NIKOLI I, et al. Extended Meet-in-the-Middle Attacks on Some Feistel Constructions[J]. Designs Codes and Cryptography, 2016, 80(3): 587-618. doi: 10.1007/s10623-015-0120-4 URL
[13]	PATARIN J. Generic Attacks on Feistel Schemes[C]// Springer. International Conference on the Theory and Application of Cryptology and Information Security. Heidelberg: Springer, 2001: 222-238.
[14]	KIM P, HAN D, JEONG K C. Time-Space Complexity of Quantum Search Algorithms in Symmetric Cryptanalysis: Applying to AES and SHA-2[J]. Quantum Information Processing, 2018, 17(12): 1-39. doi: 10.1007/s11128-017-1770-0 URL
[15]	DONG Xiaoyang, DONG Bingyou, WANG Xiaoyun. Quantum Attacks on Some Feistel Block Ciphers[J]. Designs, Codes and Cryptography. 2020(88): 1179-1203.
[16]	KAPLAN M, LEURENT G, LEVERRIER A, et al. Breaking Symmetric Cryptosystems Using Quantum Period Finding[C]// Springer. Annual International Cryptology Conference. Heidelberg: Springer, 2016: 207-237.
[17]	LEVERRIER A. Quantum Differential Cryptanalysis[EB/OL]. (2015-02-12) [2023-06-18]. http://www.dagstuhl.de/en/program/calendar/semhp/?semnr=15371.
[18]	BERNSTEIN E, VAZIRANI U. Quantum Complexity Theory[J]. Siam Journal on Computing, 1997, 26(5): 1411-1473. doi: 10.1137/S0097539796300921 URL
[19]	DAEMEN J, RIJMEN V. Probability Distributions of Correlation and Differentials in Block Ciphers[J]. Journal of Mathematical Cryptology, 2007, 1(3): 221-242.
[20]	KAPLAN M. Quantum Attacks Against Iterated Block Ciphers[J]. Matematicheskie Voprosy Kriptografii, 2014, 34: 71-90.
[21]	SHIMON E, YISHAY M. A Construction of a Cipher from a Single Pseudorandom Permutation[J]. Journal of Cryptology, 1997, 10(3): 151-161. doi: 10.1007/s001459900025 URL
[22]	KATZ J, LINDELL Y. Introduction to Modern Cryptography[M]. Boca Raton: Chapman & Hall/CRC, 2007.