对称密码体制的量子攻击

doi:10.3969/j.issn.0255-8297.2024.01.004

摘要/Abstract

摘要： 该文梳理了近年来量子攻击在对称密码体制的研究脉络，分析了主流攻击方法的研究趋势与各文献之间的关系，并将主流攻击方法分为量子周期攻击、Grover算法相关攻击、量子差分攻击3类，分别介绍了具有代表性的攻击方法，呈现了各攻击方法的核心思想。立足于现有的攻击方案，展望了这一领域可能会出现的热门研究方向。

关键词: 密码分析, 量子算法, 对称密码体制, 量子攻击

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

中图分类号:

TP309

冯晓宁, 吴洪宇. 对称密码体制的量子攻击[J]. 应用科学学报, 2024, 42(1): 39-52.

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

参考文献

[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.