Quantum algorithms and cybersecurity threats

The purpose of this article is to assess potential threats to cybersecurity arising from the development of quantum algorithms. The text analyzes existing quantum algorithms, such as Shor's algorithm and Grover's algorithm, and explores the possibility of their potential application in the context of compromising existing cryptographic systems. The research approach includes a literature review and examination of core mechanisms underlying quantum computers, along with assessment of their capability to perform algorithms potentially affecting various cryptographic systems, both symmetric and asymmetric. Additionally, the paper discusses the prospects for developing quantum-resistant cryptographic algorithms aimed at protecting against cryptanalysis using quantum computations. Based on the analysis of existing quantum algorithms and their potential impact on widely used cryptographic systems, the authors of the study conclude that, at present, there is no compelling evidence to assert the real possibility of compromising asymmetric or symmetric cryptographic algorithms in the near future within the context of quantum computations. However, considering the ongoing development of quantum technologies and the necessity of maintaining the confidentiality of information, the relevance of which will not significantly diminish over time, as well as the need to ensure the protection of confidential information in the future, there is a requirement for the development and active implementation of quantum-resistant cryptographic methods to ensure information confidentiality in the long term.

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. Petrenko A., Petrenko S. Basic Algorithms Quantum Cryptanalysis. Voprosy kiberbezopasnosti. 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. Ovchinnikov A. The Variant of Post-Quantum Cryptosystem Based on Burst-Correcting Codes and on the Complete Decoding Problem. Information and Control Systems. 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. Tarasenko S.S., Chubutkin I.A. Model' ugroz i narushitelya bezopasnosti informatsii v simmetrichnykh kriptosistemakh. In: Yunost' i Znaniya – Garantiya Uspekha – 2023: sbornik nauchnykh statei 10-i Mezhdunarodnoi molodezhnoi nauchnoi konferentsii: Volume 2, 19–20 September 2023, Kursk, Russia. Kursk: Universitetskaya kniga; 2023. P. 180–184. (In Russ.).

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. Tarasenko S.S. Algorithm of Cryptographic Transformation of Payload and Key Information Based on Vernam Cipher and Composite Cipher. Sovremennaya nauka: aktualnye problemy teorii i praktiki. Seriya estestvennye i tekhnicheskie nauki. 2023;(6/2):147–152. (In Russ.).