对称密码体制的量子攻击

doi:10.3969/j.issn.0255-8297.2024.01.004

Abstract

Abstract: This paper undertakes an investigation of recent research trends in quantum attacks on symmetric encryption schemes, offering an analysis of the connections between mainstream attack methods and various literature sources. Mainstream attack methods are systematically categorized into three types: quantum period attacks, Grover algorithmrelated attacks, and quantum differential attacks. For each category, representative attack methods are introduced, accompanied by an elucidation of the core concepts underlying each approach. Furthermore, we contemplate future research directions within this domain, considering potential advancements in light of existing attack schemes.

Key words: cryptanalysis, quantum algorithm, symmetric cryptosystem, quantum attack

CLC Number:

TP309

FENG Xiaoning, WU Hongyu. Quantum Attacks on Symmetric Cryptosystems[J]. Journal of Applied Sciences, 2024, 42(1): 39-52.

References

[1] Feynman R P. Simulating physics with computers [J]. International Journal of Theoretical Physics, 2018: 6-7.
[2] Shor P W. Algorithms for quantum computation: discrete logarithms and factoring [C]//The 35th Annual Symposium on Foundations of Computer Science, 1994: 124-134.
[3] Grover L K. A fast quantum mechanical algorithm for database search [C]//The Twenty- Eighth Annual ACM Symposium on Theory of Computing, 1996: 212-219.
[4] Rivest R L, Shamir, A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems [J]. Communications of the ACM, 1978, 21(2): 120-126.
[5] Fowler A G, Mariantoni M, Martinis J M, et al. Surface codes: towards practical largescale quantum computation [J]. Physical Review A, 2012, 86(3): 032324.
[6] Martin-Lopez E, Nigg D, Lanyon B P, et al. Experimental realization of Shor's quantum factoring algorithm using qubit recycling [J]. Nature Photonics, 2012, 6(11): 773-776.
[7] Brassard G, Hoyer P, Mosca M, et al. Quantum amplitude amplification and estimation [J]. Contemporary Mathematics. 2002, 305: 53-74.
[8] Malviya A K, Namita T, Meenu C. Quantum cryptanalytic attacks of symmetric ciphers: a review [J]. Computers and Electrical Engineering, 2022, 101: 108122.
[9] Carstens T V, Ebrahimi E, Tabia G N, et al. Relationships between quantum IND-CPA notions [C]//The 19th Theory of Cryptography Conference, 2021: 240-272.
[10] 眭晗, 吴文玲. 后量子对称密码的研究现状与发展趋势[J]. 电子与信息学报, 2020, 42(2): 287-294. Sui H, Wu W L. Research status and development trend of post-quantum symmetric cryptography [J]. Journal of Electronics & Information Technology, 2020, 42(2): 287-294. (in Chinese)
[11] Simon D R. On the power of quantum computation [J]. SIAM Journal on Computing. 1997, 26(5): 1474-1483.
[12] Shi T R, Jin C H, Hu B, et al. Complete analysis of Simon's quantum algorithm with additional collisions [J]. Quantum Information Processing, 2019, 18(11): 1-18.
[13] Cui J Y, Guo J S, Ding S Z. Applications of Simon's algorithm in quantum attacks on feistel variants [J]. Quantum Information Processing, 2021, 20(3): 1-50.
[14] 罗宜元, 闫海伦, 王磊, 等. 分组密码结构抗Simon量子算法攻击研究[J]. 密码学报, 2019, 6(5): 561-573. Luo Y Y, Yan H L, Wang L, et al. Study on block cipher structures against Simon's quantum algorithm [J]. Journal of Cryptologic Research, 2019, 6(5): 561-573. (in Chinese)
[15] Santoli T, Schaffner C. Using Simon's algorithm to attack symmetric-key cryptographic primitives [J]. Quantum Information and Computation, 2017, 17(1&2): 65-78.
[16] Kuwakado H, Morii M. Quantum distinguisher between the 3-round feistel cipher and the random permutation [C]//2010 IEEE International Symposium on Information Theory, 2010: 2682-2685.
[17] Kuwakado H, Morii M. Security on the quantum-type Even-Mansour cipher [C]//The 6th International Symposium on Information Theory and Its Applications, 2012: 312-316.
[18] Roetteler M, Steinwandt R. A note on quantum related-key attacks [J]. Information Processing Letters, 2015, 115(1): 40-44.
[19] Bonnetain X, Naya-Plasencia M, Schrottenloher A. On quantum slide attacks [C]//The 26th International Conference on Selected Areas in Cryptography, 2020: 492-519.
[20] Dong X Y, Dong B Y, Wang X Y. Quantum attacks on some Feistel block ciphers [J]. Designs, Codes and Cryptography, 2020, 88(6): 1179-1203.
[21] Kaplan M, Leurent G, Leverrier A, et al. Breaking symmetric cryptosystems using quantum period finding [C]//The 36th Annual International Cryptology Conference, 2016: 207-237.
[22] Canale F, Leander G, Stennes L. Simon's algorithm and symmetric crypto: generalizations and automatized applications [C]//Annual International Cryptology Conference, 2022: 779-808.
[23] Alagic G, Russell A. Quantum-secure symmetric-key cryptography based on hidden shifts [C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2017: 65-93.
[24] Bonnetain X, Nayaplasencia M. Hidden shift quantum cryptanalysis and implications [C]//The 24th International Conference on the Theory and Application of Cryptology and Information Security, 2018: 560-592.
[25] Bonnetain X, Hosoyamada A, Nayaplasencia M, et al. Quantum attacks without superposition queries: the offline Simon's algorithm [C]//The 25th International Conference on the Theory and Application of Cryptology and Information Security, 2019: 552-583.
[26] Bonnetain X. Tight bounds for Simon's algorithm [C]//The 7th International Conference on Cryptology and Information Security in Latin America, 2021: 3-23.
[27] Rahman M, Paul G. Quantum attacks on HCTR and its variants [J]. IEEE Symposium Actions on Quantum Engineering, 2020, 1(1): 1-8.
[28] Bonnetain X, Jaques S. Quantum period finding against symmetric primitives in practice [J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021: 1-27.
[29] Ulitzsch V Q, Seifert J P. Breaking the quadratic barrier: quantum cryptanalysis of milenage, telecommunications' cryptographic backbone [C]//International Conference on Post- Quantum Cryptography, 2023: 476-504.
[30] Leander G, May A. Grover meets Simon-quantumly attacking the FX-construction [C]//The 25th International Conference on the Theory and Application of Cryptology and Information Security, 2017: 161-178.
[31] Gurevich Y, Blass A. Quantum circuits with classical channels and the principle of deferred measurements [J]. Theoretical Computer Science, 2022, 920(6): 21-32.
[32] Shinagawa K, Iwata T. Quantum attacks on sum of Even-Mansour pseudorandom functions [J]. Information Processing Letters, 2022, 173(1): 106172.
[33] Zhang P. Quantum attacks on sum of even-mansour construction with linear key schedules [J]. Entropy, 2022, 24(2): 153.
[34] 倪博煜, 董晓阳. 改进的Type-1型广义Feistel结构的量子攻击及其在分组密码CAST-256上的应用[J]. 电子与信息学报, 2020, 42(2): 295-306. Ni B Y, Dong X Y. Improved quantum attack on type-1 generalized feistel schemes and its application to CAST-256[J].Journal of Electronics & Information Technology 2020, 42(2): 295-306.(in Chinese)
[35] Dong X Y, Wang X Y. Quantum key-recovery attack on Feistel structures [J]. Science China Information Sciences, 2018, 61(10): 1-7.
[36] Zhou B M, Yuan Z. Quantum key-recovery attack on Feistel constructions: Bernstein-Vazirani meet Grover algorithm [J]. Quantum Information Processing, 2021, 20(10): 1-14.
[37] NIST. Submission requirements and evaluation criteria for the post-quantum cryptography [DB/OL]. 2016[2023-06-29]. https://csrc.nist.gov/csrc/media/Projects/pqc-digsig/documents/call-for-proposals-dig-sig-sept-2022.pdf.
[38] Grassl M, Langenberg B, Roetteler M, et al. Applying grover's algorithm to AES: quantum resource estimates [C]//The 7th International Conference on Post-Quantum Cryptography, 2017: 161-178.
[39] Almazrooie M, Samsudin A, Abdullah R, et al. Quantum reversible circuit of AES-128[J]. Quantum Information Processing, 2018, 17(5): 1-30.
[40] Langenberg B, Pham H, Steinwandt R. Reducing the cost of implementing the advanced encryption standard as a quantum circuit [J]. IEEE Transactions on Quantum Engineering, 2020, 1: 1-12.
[41] Zou J, Wei Z H, Sun S W, et al. Quantum circuit implementations of AES with fewer qubits [C]//The 26th International Conference on the Theory and Application of Cryptology and Information Security, 2020: 697-726.
[42] Anand R, Maitra A, Mukhopadhyay S. Grover on SIMON [J]. Quantum Information Processing. 2020, 19(9): 1-17.
[43] Liu H, Yang L. Quantum key recovery attack on Simon32/64[J]. Cybersecurity, 2021, 4(1): 1-15.
[44] Hosoyamada A, Sasaki Y. Quantum demiric-selcuk meet-in-the-middle attacks: applications to 6-round generic feistel constructions [C]//The 11th International Conference on Security and Cryptography for Networks, 2018: 386-403.
[45] Xu Y S, Yuan Z. Quantum meet-in-the-middle attack on Feistel construction [J]. Quantum Information Processing, 2023, 22(3): 155.
[46] Wang P, Chen X M, Jiang G H. Quantum demiric-selcuk meet-in-the-middle attacks on reduced-round AES [J]. International Journal of Theoretical Physics, 2022, 61(1): 1-12.
[47] Dunkelman O, Keller N, Ronen E, et al. Quantum time/memory/data tradeoff attacks [J]. Designs, Codes and Cryptography, 2023: 1-19.
[48] Frixons P, Naya-Plasencia M, Schrottenloher A. Quantum boomerang attacks and some applications [C]//The 26th International Conference on Selected Areas in Cryptography, 2022: 332-352.
[49] Dong X Y, Qin L Y, Sun S W, et al. Key guessing strategies for linear key-schedule algorithms in rectangle attacks [C]//Annual International Conference on the Theory and Applications of Cryptographic Techniques, 2022: 3-33.
[50] David N, Naya-Plasencia M, Schrottenloher A. Quantum impossible differential attacks: applications to AES and SKINNY [J]. Designs, Codes and Cryptography, 2023: 1-29.
[51] Hosoyamada A, Sasaki Y. Finding hash collisions with quantum computers by using differential trails with smaller probability than birthday bound [C]//The 39th International Conference on the Theory and Applications of Cryptographic Techniques, 2020: 249-279.
[52] Dong X Y, Sun S W, Shi D P, et al. Quantum collision attacks on AES-like hashing with low quantum random access memories [C]//The 26th International Conference on the Theory and Application of Cryptology and Information Security, 2020: 727-757.
[53] Hosoyamada A, Sasaki Y. Cryptanalysis against symmetric-key schemes with online classical queries and offline quantum computations [C]//The 18th Cryptographers Track at the RSA Conference, 2018: 198-218.
[54] Schrottenloher A, Stevens M. Simplified MITM modeling for permutations: new (quantum) attacks [C]//The 42nd Annual International Cryptology Conference, 2022: 717-747.
[55] Kaplan M. Quantum attacks against iterated block ciphers [DB/OL]. 2014[2023-06-29]. https://arxiv.org/abs/1410.1434.
[56] Bernstein E, Vazirani U. Quantum complexity theory [C]//The 25th Annual ACM Symposium on Theory of Computing, 1993: 11-20.
[57] Cui J Y, Guo J S. Quantum cryptographic property testing of multi-output Boolean functions [J]. Quantum Information Processing, 2019, 18(6): 1-56.
[58] Li H W. Quantum algorithms for the resiliency of vectorial boolean functions [J]. International Journal of Theoretical Physics, 2021, 60(4): 1565-1573.
[59] Xie H Q, Yang L. Quantum miss-in-the-middle attack [DB/OL]. 2018[2023-06-29]. https://arxiv.org/abs/1812.08499.
[60] Biham E, Shamir A. Differential cryptanalysis of DES -like cryptosystems [J]. Journal of Cryptology, 1991, 4(1): 3-72.
[61] Li H W, Li Y. Quantum differential cryptanalysis to the block ciphers [C]//International Conference on Applications and Techniques in Information Security, 2015: 44-51.
[62] Xie H Q, Yang L. Using Bernstein-Vazirani algorithm to attack block ciphers [J]. Designs, Codes and Cryptography, 2019, 87(5): 1161-1182.
[63] Xie H Q, Yang L. Quantum impossible differential and truncated differential cryptanalysis [DB/OL].2017[2023-06-29]. https://arxiv.org/abs/1712.06997.
[64] Xie H Q, Yang L. A quantum related-key attack based on the Bernstein-Vazirani algorithm [J]. Quantum Information Processing, 2020, 19(8): 1-20.
[65] Kaplan M, Leurent G, Leverrier A, et al. Quantum differential and linear cryptanalysis [J]. IACR Transactions on Symmetric Cryptology, 2016, 1: 71-94.
[66] Zhou Q, Lu S F, Zhang Z G, et al. Quantum differential cryptanalysis [J]. Quantum Information Processing, 2015, 14(6): 2101-2109.
[67] Jojan P, Soni K K, Rasool A. Classical and quantum based differential cryptanalysis methods [C]//The 12th International Conference on Computing Communication and Networking Technologies, 2021: 1-7.
[68] Denisenko D V. Quantum differential cryptanalysis [J]. Journal of Computer Virology and Hacking Techniques, 2022, 18: 1-8.
[69] Li H W, Yang L. A quantum algorithm to approximate the linear structures of Boolean functions [J]. Mathematical Structures in Computer Science, 2018, 28(1): 1-13.
[70] Aronson S, Rall P. Quantum approximate counting, simplified [C]//Symposium on Simplicity in Algorithms, 2020: 24-32.
[71] Chen Y H, Wei S J, Gao X, et al. A low failure rate quantum algorithm for searching maximum or minimum [J]. Quantum Information Processing, 2020, 19(8): 1-28.

Quantum Attacks on Symmetric Cryptosystems

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics

Comments

[1]	LI Yun-fei1,2,3 , LIU Qing1, LI Tong1, HAO Lin3. Cryptanalysis against an Improved RSA Algorithm [J]. Journal of Applied Sciences, 2013, 31(6): 655-660.
[2]	ZHOU Yue;LI Rui-lin;LI Chao. XOR Approximation of Modulo Addition for Cryptanalysis [J]. Journal of Applied Sciences, 2008, 26(2): 132-132 .
[3]	LI Chao, HUANG Jian-zhong, XIANG Pan-pan. The Applications of Differential Cryptanalysis in Sequence Cipher Attack [J]. Journal of Applied Sciences, 2004, 22(2): 127-131.