Квантовые алгоритмы и угрозы кибербезопасности

Целью написания данной статьи является оценка потенциальных угроз для кибербезопасности, вызванных развитием квантовых алгоритмов. В тексте работы осуществляется анализ существующих квантовых алгоритмов, таких как алгоритм Шора и алгоритм Гровера, и исследуется возможность их потенциального применения в контексте взлома существующих криптографических систем. Методология проводимого исследования заключается в анализе литературы, а также рассмотрении основных принципов функционирования квантовых вычислителей и потенциала реализации квантовых алгоритмов, способных влиять на безопасность как симметричных, так и асимметричных криптографических схем. Кроме того, в исследовании анализируются перспективы создания криптографических алгоритмов, способных противостоять атакам с применением квантовых технологий. На основе анализа существующих квантовых алгоритмов и их потенциального воздействия на широко распространенные в настоящее время криптографические системы, авторы исследования приходят к выводу, что на текущий момент отсутствуют убедительные основания для констатации реальной возможности взлома ассиметричных или симметричных криптографических алгоритмов в ближайшее время в контексте квантовых вычислений. Однако, учитывая постоянное развитие квантовых технологий, а также необходимость сохранения конфиденциальности сведений, актуальность которых с течением времени не будет претерпевать значительное снижение, и необходимость обеспечения защиты конфиденциальной информации в будущем, требуется разработка и активное внедрение квантово-устойчивых криптографических методов для обеспечения конфиденциальности информации в долгосрочной перспективе.

1. Bennett Ch.H., Bernstein E., Brassard G., Vazirani U. Strengths and Weaknesses of Quantum Computing. SIAM Journal on Computing. 1997;26(5):1510–1523. https://doi.org/10.1137/s0097539796300933

2. Anand R., Maitra A., Mukhopadhyay S. Grover on SIMON. Quantum Information Processing. 2020;19(9). https://doi.org/10.1007/S11128-020-02844-W

3. Jaques S., Naehrig M., Roetteler M., Virdia F. Implementing Grover Oracles for Quantum Key Search on AES and LowMC. In: Advances in Cryptology – EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques: Proceedings: Part II, 10–14 May 2020, Zagreb, Croatia. Cham: Springer; 2020. P. 280–310. https://doi.org/10.1007/978-3-030-45724-2_10

4. Song G., Jang K., Kim H., Lee W.-K., Seo H. Grover on Caesar and Vigenère Ciphers. Cryptology ePrint Archive. URL: https://eprint.iacr.org/2021/554 [Accessed 30th January 2024].

5. Kochan R., Yevseiev S., Korolyov R., et al. Development of Methods for Improving Crypto Transformations in the Block-Symmetric Code. In: 2020 IEEE 5th International Symposium on Smart and Wireless Systems Within the Conferences on Intelligent Data Acquisition and Advanced Computing Systems (IDAACS-SWS), 17–18 September 2020, Dortmund, Germany. IEEE; 2020. P. 1–9. https://doi.org/10.1109/IDAACS-SWS50031.2020.9297102

6. Jing Z., Gu C., Ge C., Shi P. Cryptanalysis of a Public Key Cryptosystem Based on Data Complexity Under Quantum Environment. In: Security and Privacy in New Computing Environments, Second EAI International Conference, SPNCE 2019: Proceedings, 13–14 April 2019, Tianjin, China. Cham: Springer; 2019. P. 411–420. https://doi.org/10.1007/978-3-030-21373-2_32

7. Grover L.K. A Fast Quantum Mechanical Algorithm for Database Search. In: STOC '96: Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing, 22–24 May 1996, Philadelphia, PA, USA. New York: Association for Computing Machinery; 1996. P. 212–219. https://doi.org/10.1145/237814.237866

8. Regev O. An Efficient Quantum Factoring Algorithm. arXiv. URL: https://arxiv.org/abs/2308.06572 [Accessed 30th January 2024].

9. Kuwakado H., Morii M. Quantum Distinguisher Between the 3-Round Feistel Cipher and the Random Permutation. In: 2010 IEEE International Symposium on Information Theory (ISIT 2010), 13–18 June 2010, Austin, TX, USA. IEEE; 2010. P. 2682–2685. https://doi.org/10.1109/ISIT.2010.5513654

10. Beals R., Brierley S., Gray O., et al. Efficient Distributed Quantum Computing. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 2013;469(2153). https://doi.org/10.1098/rspa.2012.0686

11. Kaplan M., Leurent G., Leverrier A., Naya-Plasencia M. Breaking Symmetric Cryptosystems Using Quantum Period Finding. In: Advances in Cryptology – CRYPTO 2016: 36th Annual International Cryptology Conference: Proceedings: Part II, 14–18 August 2016, Santa Barbara, CA, USA. Berlin, Heidelberg: Springer; 2016. P. 207–237. https://doi.org/10.1007/978-3-662-53008-5_8

12. Simon D.R. On the Power of Quantum Computation. SIAM Journal on Computing. 1997;26(5):1474–1483. https://doi.org/10.1137/S0097539796298637

13. Alagic G., Russell A. Quantum-Secure Symmetric-Key Cryptography Based on Hidden Shifts. In: Advances in Cryptology – EUROCRYPT 2017: 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques: Proceedings: Part III, 30 April – 04 May 2017, Paris, France. Cham: Springer; 2017. P. 65–93. https://doi.org/10.1007/978-3-319-56617-7_3

14. Kaplan M., Leurent G., Leverrier A., Naya-Plasencia M. Quantum Differential and Linear Cryptanalysis. IACR Transactions on Symmetric Cryptology. 2016;2016(1):71–94. https://doi.org/10.13154/tosc.v2016.i1.71-94

15. Hosoyamada A., Aoki K. On Quantum Related-Key Attacks on Iterated Even-Mansour Ciphers. In: Advances in Information and Computer Security: 12th International Workshop on Security, IWSEC 2017: Proceedings, 30 August – 01 September 2017, Hiroshima, Japan. Cham: Springer; 2017. P. 3–18. https://doi.org/10.1007/978-3-319-64200-0_1

16. Dong X., Dong B., Wang X. Quantum Attacks on Some Feistel Block Ciphers. Designs, Codes and Cryptography. 2020;88(6):1179–1203. https://doi.org/10.1007/s10623-020-00741-y

17. Xu Yi., Yuan Zh. Quantum Meet-in-the-Middle Attack on Feistel Construction. arXiv. URL: https://arxiv.org/abs/2107.12724 [Accessed 30th January 2024].

18. Bonnetain X., Schrottenloher A., Sibleyras F. Beyond Quadratic Speedups in Quantum Attacks on Symmetric Schemes. In: Advances in Cryptology – EUROCRYPT 2022: 41st Annual International Conference on the Theory and Applications of Cryptographic Techniques: Proceedings: Part III, 30 May – 03 June 2022, Trondheim, Norway. Cham: Springer; 2022. P. 315–344. https://doi.org/10.1007/978-3-031-07082-2_12

19. Xie H., Xia Q., Wang K., Li Ya., Yang L. Quantum Automated Tools for Finding Impossible Differentials. Mathematics. 2024;12(16). https://doi.org/10.3390/math12162598

20. S H., Mishra N., D V. QHopNN: Investigating Quantum Advantage in Cryptanalysis Using a Quantum Hopfield Neural Network. Physica Scripta. 2024;99(8). https://doi.org/10.1088/1402-4896/ad5ed1

21. Kuwakado H., Morii M. Security on the Quantum-Type Even-Mansour Cipher. In: 2012 International Symposium on Information Theory and its Applications, 28–31 October 2012, Honolulu, HI, USA. IEEE; 2012. P. 312–316.

22. Dunkelman O., Keller N., Shamir A. Slidex Attacks on the Even-Mansour Encryption Scheme. Journal of Cryptology. 2015;28(1):1–28. https://doi.org/10.1007/s00145-013-9164-7

23. Bonnetain X. Quantum Key-Recovery on Full AEZ. In: Selected Areas in Cryptography – SAC 2017: 24th International Conference: Revised Selected Papers, 16–18 August 2017, Ottawa, ON, Canada. Cham: Springer; 2018. P. 394–406. https://doi.org/10.1007/978-3-319-72565-9_20

24. Kuperberg G. A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem. SIAM Journal on Computing. 2005;35(1):170–188. https://doi.org/10.1137/S0097539703436345

25. Chailloux A., Naya-Plasencia M., Schrottenloher A. An Efficient Quantum Collision Search Algorithm and Implications on Symmetric Cryptography. In: Advances in Cryptology – ASIACRYPT 2017: 23rd International Conference on the Theory and Application of Cryptology and Information Security: Proceedings: Part II, 03–07 December 2017, Hong Kong, China. Cham: Springer; 2017. P. 211–240. https://doi.org/10.1007/978-3-319-70697-9_8

26. Gidney C., Ekerå M. How to Factor 2048 Bit RSA Integers in 8 Hours Using 20 Million Noisy Qubits. arXiv. URL: https://arxiv.org/abs/1905.09749 [Accessed 30th January 2024].

27. Gouzien E., Sangouard N. Factoring 2048-bit RSA Integers in 177 Days with 13436 Qubits and a Multimode Memory. arXiv. URL: https://arxiv.org/abs/2103.06159 [Accessed 30th January 2024].

28. Deutsch D., Jozsa R. Rapid Solution of Problems by Quantum Computation. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 1992;439(1907):553–558. https://doi.org/10.1098/rspa.1992.0167

29. Cleve R., Ekert A., Macchiavello C., Mosca M. Quantum Algorithms Revisited. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 1998;454(1969):339–354. https://doi.org/10.1098/rspa.1998.0164

30. Childs A.M., Liu J.-P. Quantum Spectral Methods for Differential Equations. Communications in Mathematical Physics. 2019;375(2):1427–1457. https://doi.org/10.1007/s00220-020-03699-z

31. Nielsen M.A., Chuang I.L. Quantum Computation and Quantum Information: 10th Anniversary Edition. Cambridge: Cambridge University Press; 2010. 702 p. https://doi.org/10.1017/cbo9780511976667

32. Ozhigov Yu. Quantum Computers Speed Up Classical with Probability Zero. Chaos Solitons Fractals. 1999;10(10):1707–1714. https://doi.org/10.1016/S0960-0779(98)00226-4

33. Петренко А.С., Петренко С.А. Основные алгоритмы квантового криптоанализа. Вопросы кибербезопасности. 2023;(1):100–115. (На англ.).

34. Buchmann J., García L.C.C., Dahmen E., Döring M., Klintsevich E. CMSS – An Improved Merkle Signature Scheme. In: Progress in Cryptology – INDOCRYPT 2006: 7th International Conference on Cryptology in India: Proceedings, 11–13 December 2006, Kolkata, India. Berlin, Heidelberg: Springer; 2006. P. 349–363. https://doi.org/10.1007/11941378_25

35. Dinh H., Moore C., Russell A. McEliece and Niederreiter Cryptosystems That Resist Quantum Fourier Sampling Attacks. In: Advances in Cryptology – CRYPTO 2011: 31st Annual Cryptology Conference: Proceedings, 14–18 August 2011, Santa Barbara, CA, USA. Berlin, Heidelberg: Springer; 2011. P. 761–779. https://doi.org/10.1007/978-3-642-22792-9_43

36. Овчинников А.А. Вариант постквантовой системы на основе кодов, исправляющих пакеты ошибок, и задачи полного декодирования. Информационно-управляющие системы. 2022;(3):45–54. (На англ.). https://doi.org/10.31799/1684-8853-2022-3-45-54

37. Goldreich O., Goldwasser Sh., Halevi Sh. Public-Key Cryptosystems from Lattice Reduction Problems. In: Advances in Cryptology – CRYPTO '97: 17th Annual International Cryptology Conference: Proceedings, 17–21 August 1997, Santa Barbara, California, USA. Berlin, Heidelberg: Springer; 1997. P. 112–131. https://doi.org/10.1007/BFb0052231

38. Yu Yu. Preface to Special Topic on Lattice-Based Cryptography. National Science Review. 2021;8(9). https://doi.org/10.1093/nsr/nwab154

39. Courtois N.T. The Security of Hidden Field Equations (HFE). In: Topics in Cryptology – CT-RSA 2001: The Cryptographer's Track at RSA Conference: Proceedings, 08–12 April 2001, San Francisco, CA, USA. Berlin, Heidelberg: Springer; 2001. P. 266–281. https://doi.org/10.1007/3-540-45353-9_20

40. Bogomolec X., Underhill J.G., Kovac S.A. Towards Post-Quantum Secure Symmetric Cryptography: A Mathematical Perspective. Cryptology ePrint Archive. URL: https://eprint.iacr.org/2019/1208 [Accessed 30th January 2024].

41. Jao D., De Feo L. Towards Quantum-Resistant Cryptosystems from Supersingular Elliptic Curve Isogenies. In: Post-Quantum Cryptography: 4th International Workshop, PQCrypto 2011: Proceedings, 29 November – 02 December 2011, Taipei, Taiwan. Berlin, Heidelberg: Springer; 2011. P. 19–34. https://doi.org/10.1007/978-3-642-25405-5_2

42. Stratil Ph., Hasegawa Sh., Shizuya H. Supersingular Isogeny-Based Cryptography: A Survey. Interdisciplinary Information Sciences. 2021;27(1):1–23. https://doi.org/10.4036/iis.2020.r.02

43. Lauter K.E., Petit Ch. Supersingular Isogeny Graphs in Cryptography. In: Surveys in Combinatorics: Chapter 5. Cambridge University Press; 2019. P. 143–166. https://doi.org/10.1017/9781108649094.006

44. Tenorio R.H.V., Sham Ch.W., Vargas D.V. Preliminary Study of Applied Binary Neural Networks for Neural Cryptography. In: GECCO '20: Proceedings of the 2020 Genetic and Evolutionary Computation Conference Companion, 08–12 July 2020, Cancún, Mexico. New York: Association for Computing Machinery; 2020. P. 291–292. https://doi.org/10.1145/3377929.3389933

45. Tarasenko S.S., Andriyanov N.A., Gladkikh A.A. Analysis of the Applicability of Artificial Neural Networks for the Post-Quantum Cryptography Algorithms Development. In: Journal of Physics: Conference Series: Volume 2032: International Conference on IT in Business and Industry (ITBI 2021), 12–14 May 2021, Novosibirsk, Russia. IOP Publishing Ltd; 2021. https://doi.org/10.1088/1742-6596/2032/1/012026

46. Singh A., Nandal A. Neural Cryptography for Secret Key Exchange and Encryption with AES. International Journal of Advanced Research in Computer Science and Software Engineering. 2013;3(5):376–381.

47. Тарасенко С.С., Чубуткин И.А. Модель угроз и нарушителя безопасности информации в симметричных криптосистемах. В сборнике: Юность и Знания – Гарантия Успеха – 2023: сборник научных статей 10-й Международной молодежной научной конференции: Том 2, 19–20 сентября 2023 года, Курск, Россия. Курск: Университетская книга; 2023. С. 180–184.

48. Tarasenko S., Ivanov Yu. Approach to Constructing Symmetric Cryptographic Systems Ensuring Specified Resilience to Cryptoanalysis over the Long-Term Time Horizon. Journal of Science and Technology on Information Security. 2023;3(20):88–94. https://doi.org/10.54654/isj.v3i20.1016

49. Тарасенко С.С. Алгоритм криптографического преобразования полезной нагрузки и ключевой информации на основе шифра Вернама и композиционного шифра. Современная наука: актуальные проблемы теории и практики. Серия Естественные и технические науки. 2023;(6/2):147–152.