Новая модель квантового оракула для гибридной квантово-классической атаки на постквантовые криптосистемы, основанные на решётках

Новая модель квантового оракула для гибридной квантово-классической атаки на постквантовые криптосистемы, основанные на решётках

Бахарев А. О.
Дискретный анализ и исследование операций, 31, 3, 24–53 (2024)
Скачать статью

УДК 519.7 
DOI: 10.33048/daio.2024.31.777

Аннотация:

Криптосистемы на основе решёток являются одними из основных постквантовых альтернатив асимметричной криптографии, используемой в настоящее время. Большинство атак на такие криптосистемы можно свести к задаче нахождения кратчайшего вектора в решётке (SVP). Ранее авторами была предложена модель квантового оракула из алгоритма Гровера для реализации гибридного квантово-классического алгоритма, основанного на алгоритме GaussSieve и решающего SVP. В настоящей работе предложена и проанализирована новая модель квантового оракула. Предложены и оценены две реализации новой модели квантового оракула. Проанализирована сложность реализации новой модели квантового оракула для атаки на постквантовые криптосистемы, основанные на решётках и являющиеся финалистами конкурса постквантовой криптографии NIST. Приведено сравнение полученных результатов для новой и уже существующей моделей квантового оракула. 
Табл. 4, ил. 10, библиогр. 48.

Литература:
  1. Bernstein D. J. Introduction to post-quantum cryptography // Post-quantum cryptography. Heidelberg: Springer, 2009. P. 1–14.
     
  2. Малыгина Е. С., Куценко А. В., Новосёлов С. А. [и др.]. Постквантовые криптосистемы: открытые вопросы и существующие решения. Криптосистемы на решётках // Дискрет. анализ и исслед. операций. 2023. Т. 30, № 4. C. 46–90.
     
  3. Малыгина Е. С., Куценко А. В., Новосёлов С. А. [и др.]. Постквантовые криптосистемы: открытые вопросы и существующие решения. Криптосистемы на изогениях и кодах, исправляющих ошибки // Дискрет. анализ и исслед. операций. 2024. Т. 31, № 1. C. 52–84.
     
  4. Daemen J., Rijmen V. The design of Rijndael. Heidelberg: Springer, 2002. 238 p. DOI: 10.1007/978-3-662-04722-4
     
  5. Dworkin M. J. SHA-3 standard: Permutation-based hash and extendableoutput functions. Gaithersburg, MD: Nat. Inst. Stand. Technol., 2015. 37 p. (Fed. Inf. Process. Stand. Publ.; V. 202). DOI: 10.6028/NIST.FIPS.202.
     
  6. Rivest R. L., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems // Commun. ACM. 1978. V. 21, No. 2. P. 120–126.
     
  7. Barker E. Digital signature standard (DSS). Gaithersburg, MD: Nat. Inst. Stand. Technol., 2013. 131 p. (Fed. Inf. Process. Stand. Publ.; V. 186-4). DOI: 10.6028/NIST.FIPS.186-4.
     
  8. Shor P. W. Algorithms for quantum computation: Discrete logarithms and factoring // Proc. 35th Annu. Symp. Foundations of Computer Science (Santa Fe, USA, Nov. 20–22, 1994). Los Alamitos, CA: IEEE Comput. Soc., 1994. P. 124–134.
     
  9. Alagic G., Apon D., Cooper D. [et al.]. Status report on the third round of the NIST post-quantum cryptography standardization process. Nat. Inst. Stand. Technol. Interagency Internal Rep. NIST IR 8413-upd1. Gaithersburg, MD: NIST, 2022. 102 p. DOI: 10.6028/NIST.IR.8413-upd1.
     
  10. Korean Post-Quantum Cryptography Competition. Seoul: Natl. Intell. Serv., 2023. URL: kpqc.or.kr/competition.html (accessed: 9.10.2023).
     
  11. Micciancio D. Inapproximability of the shortest vector problem: Toward a deterministic reduction // Theory Comput. 2012. V. 8, No. 1. P. 487–512.
     
  12. Kannan R. Improved algorithms for integer programming and related lattice problems // Proc. 15th Annu. ACM Symp. Theory of Computing (Boston, USA, Apr. 25–27, 1983). New York: ACM, 1983. P. 193–206.
     
  13. Fincke U., Pohst M. Improved methods for calculating vectors of short length in a lattice, including a complexity analysis // Math. Comput. 1985. V. 44, No. 170. P. 463–471.
     
  14. Gama N., Nguyen P. Q., Regev O. Lattice enumeration using extreme pruning // Advances in cryptology — EUROCRYPT 2010. Proc. 29th Annu. Int. Conf. Theory and Application of Cryptographic Techniques (French Riviera, May 30 – June 3, 2010). Heidelberg: Springer, 2010. P. 257–278. (Lect. Notes Comput. Sci.; V. 6110).
     
  15. Lenstra A. K., Lenstra H. W., Lovász L. Factoring polynomials with rational coefficients // Math. Ann. 1982. V. 261, No. 4. P. 515–534. DOI: 10.1007/BF01457454.
     
  16. Chen Y., Nguyen P. Q. BKZ 2.0: Better lattice security estimates // Advances in cryptology — ASIACRYPT 2011. Proc. 17th Int. Conf. Theory and Application of Cryptology and Information Security (Seoul, South Korea, Dec. 4–8, 2011). Heidelberg: Springer, 2011. P. 1–20. (Lect. Notes Comput. Sci.; V. 7073).
     
  17. Schnorr C. P. A hierarchy of polynomial time lattice basis reduction algorithms // Theor. Comput. Sci. 1987. V. 53, No. 2–3. P. 201–224. DOI: 10.1016/0304-3975(87)90064-8.
     
  18. Schnorr C. P., Euchner M. Lattice basis reduction: Improved practical algorithms and solving subset sum problems // Math. Program. 1994. V. 66. P. 181–199. DOI: 10.1007/BF01581144.
     
  19. Becker A., Ducas L., Gama G., Laarhoven T. New directions in nearest neighbor searching with applications to lattice sieving // Proc. 27th Annu. ACM-SIAM Symp. Discrete Algorithms (Arlington, VA, USA, Jan. 10–12, 2016). Philadelphia, PA: SIAM, 2016. P. 10–24.
     
  20. Herold G., Kirshanova E., Laarhoven T. Speed-ups and time–memory trade-offs for tuple lattice sieving // Public-key cryptography — PKC 2018. Proc. 21st IACR Int. Conf. Practice and Theory of Public-Key Cryptography (Rio de Janeiro, Brazil, Mar. 25–29, 2018). Pt. I. Cham: Springer, 2018. P. 407–436. (Lect. Notes Comput. Sci.; V. 10769).
     
  21. Micciancio D., Voulgaris P. Faster exponential time algorithms for the shortest vector problem // Proc. 21st Annu. ACM-SIAM Symp. Discrete Algorithms (Austin, TX, USA, Jan. 17–19, 2010). Philadelphia, PA: SIAM, 2010. P. 1468–1480.
     
  22. Nguyen P. Q., Vidick T. Sieve algorithms for the shortest vector problem are practical // J. Math. Cryptol. 2008. V. 2, No. 2. P. 181–207. DOI: 10. 1515/JMC.2008.009.
     
  23. Pujol X., Stehlé D. Solving the shortest lattice vector problem in time $2^{2.465n}$. San Diego: Univ. California, 2009. (Cryptol. ePrint Archive; ID 2009/605). URL: eprint.iacr.org/2009/605 (accessed: 9.10.2023).
     
  24. Aggarwal D., Dadush D., Regev O., Stephens-Davidowitz N. Solving the shortest vector problem in $2^n$ time using discrete Gaussian sampling // Proc. 47th ACM Symp. Theory of Computing (Portland, OR, USA, June 14–17, 2015). New York: ACM, 2015. P. 733–742.
     
  25. Doulgerakis E., Laarhoven T., de Weger B. Finding closest lattice vectors using approximate Voronoi cells // Post-quantum cryptography. Rev. Sel. Pap. 10th Int. Conf. (Chongqing, China, May 8–10, 2019). Cham: Springer, 2019. P. 3–22. (Lect. Notes Comput. Sci.; V. 11505).
     
  26. Micciancio D., Voulgaris P. A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations // Proc. 42nd ACM Symp. Theory of Computing (Cambridge, MA, USA, June 5–8, 2010). New York: ACM, 2010. P. 351–358.
     
  27. Денисенко Д. В., Никитенкова М. В. Применение квантового алгоритма Гровера в задаче поиска ключа блочного шифра SDES // Журн. эксперим. и теор. физики. 2019. Т. 155, вып. 1. С. 32–53.
     
  28. Денисенко Д. В, Маршалко Г. Б., Никитенкова М. В., Рудской В. И., Шишкин В. А. Оценка сложности реализации алгоритма Гровера для перебора ключей алгоритмов блочного шифрования ГОСТ Р 34.12-2015 // Журн. эксперим. и теор. физики. 2019. Т. 155, вып. 4. С. 645–653.
     
  29. Almazrooie M., Samsudin A., Abdullah R., Mutter K. N. Quantum exhaustive key search with simplified-DES as a case study // SpringerPlus. 2016. V. 5, No. 1. P. 1–19.
     
  30. Dong X., Dong B., Wang X. Quantum attacks on some Feistel block ciphers // Des. Codes Cryptogr. 2020. V. 88, No. 6. P. 1179–1203. DOI: 10.1007/s10623-020-00741-y.
     
  31. Frixons P., Naya-Plasencia M., Schrottenloher A. Quantum boomerang attacks and some applications // Selected areas in cryptography. Proc. 28th Int. Conf. (Virtual Event, Sept. 29 – Oct. 1, 2021). Cham: Springer, 2021. P. 332–352. (Lect. Notes Comput. Sci.; V. 13203).
     
  32. Jaques S., Naehrig M., Roetteler M., Virdia F. Implementing Grover oracles for quantum key search on AES and LowMC // Advances in cryptology — EUROCRYPT 2020. Proc. 39th Annu. Int. Conf. Theory and Application of Cryptographic Techniques (Zagreb, Croatia, May 10–14, 2020). Pt. II. Cham: Springer, 2020. P. 280–310. (Lect. Notes Comput. Sci.; V. 12106).
     
  33. Grassl M., Langenberg B., Roetteler M., Steinwandt R. Applying Grover’s algorithm to AES: quantum resource estimates // Post-quantum cryptography. Proc. 7th Int. Workshop (Fukuoka, Japan, Feb. 24–26, 2016). Cham: Springer, 2016. P. 29–43. (Lect. Notes Comput. Sci.; V. 9606).
     
  34. Langenberg B., Pham H., Steinwandt R. Reducing the cost of implementing the advanced encryption standard as a quantum circuit // IEEE Trans. Quantum Eng. 2020. V. 1. P. 1–12.
     
  35. Zou J., Wei Z., Sun S., Liu X., Wu W. Quantum circuit implementations of AES with fewer qubits // Advances in cryptology — ASIACRYPT 2020. Proc. 26th Int. Conf. Theory and Application of Cryptology and Information Security (Daejeon, South Korea, Dec. 7–11, 2020). Pt. II. Cham: Springer, 2020. P. 697–726. (Lect. Notes Comput. Sci.; V. 12492).
     
  36. Albrecht M. R., Gheorghiu V., Postlethwaite E. W., Schanck J. M. Estimating quantum speedups for lattice sieves // Advances in cryptology — ASIACRYPT 2020. Proc. 26th Int. Conf. Theory and Application of Cryptology and Information Security (Daejeon, South Korea, Dec. 7–11, 2020). Pt. II. Cham: Springer, 2020. P. 583–613. (Lect. Notes Comput. Sci.; V. 12492).
     
  37. Gidney C., Ekerå M. How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits // Quantum. 2021. V. 5. P. 433. DOI: 10.22331/q-2021-04-15-433.
     
  38. Laarhoven T., Mosca M., van de Pol J. Finding shortest lattice vectors faster using quantum search // Des. Codes Cryptogr. 2015. V. 77, No. 2–3. P. 375–400.
     
  39. Perriello S., Barenghi A., Pelosi G. A complete quantum circuit to solve the information set decoding problem // Proc. 2021 IEEE Int. Conf. Quantum Computing and Engineering (Broomfield, CO, USA, Oct. 17–22, 2021). Los Alamitos, CA: IEEE Comput. Soc., 2021. P. 366–377.
     
  40. Бахарев A. О. Оценки сложности реализации квантового криптоанализа постквантовых криптосистем, основанных на решётках // Дискрет. анализ и исслед. операций. 2023. T. 30, № 3. С. 5–42.
     
  41. Grover L. K. A fast quantum mechanical algorithm for database search // Proc. 28th ACM Symp. Theory of Computing (Philadelphia, PA, USA, May 22–24, 1996). New York: ACM, 1996. P. 212–219. DOI: 10.1145/237814. 237866.
     
  42. Nielsen M. A., Chuang I. L. Quantum computation and quantum information. Cambridge: Camb. Univ. Press, 2010. 676 p.
     
  43. Китаев A. Ю., Шень А. Х., Вялый М. Н. Классические и квантовые вычисления. М.: МЦНМО; ЧеРо, 1999. 192 с.
     
  44. Boyer M., Brassard G., Høyer P., Tapp A. Tight bounds on quantum searching // Fortschr. Phys. 1998. V. 46, No. 4–5. P. 493–505.
     
  45. Moore C., Nilsson M. Parallel quantum computation and quantum codes // SIAM J. Comput. 2001. V. 31, No. 3. P. 799–815.
     
  46. Chen C., Danba O., Hoffstein J. [et al.]. NTRU algorithm specifications and supporting documentation. Eindhoven: Eindh. Univ. Technol., 2019. URL: https://ntru.org/f/ntru-20190330.pdf (accessed: 9.10.2023).
     
  47. D’Anvers J.-P., Karmakar A., Roy S. S., Vercauteren F. SABER: Mod-LWR based KEM. Leuven: KU Leuven, 2017. URL: https://www. esat.kuleuven.be/cosic/pqcrypto/saber/files/saberspecround1.pdf (accessed: 9.10.2023).
     
  48.  Avanzi R., Bos J., Ducas L. [et al.]. CRYSTALS-Kyber algorithm specifications and supporting documentation. Amsterdam: Cent. Wiskd. Inform., 2021. URL: https://cryptojedi.org/papers/kybernist-20171130. pdf (accessed: 9.10.2023).

Исследование выполнено при поддержке Математического центра в Академгородке в рамках соглашения № 075–15–2022–282 с Министерством науки и высшего образования Российской Федерации

Бахарев Александр Олегович
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: a.bakharev@g.nsu.ru

Статья поступила 27 июня 2023 г.
После доработки — 27 ноября 2023 г.
Принята к публикации 22 марта 2024 г.

Abstract:

Lattice-based cryptosystems are one of the main post-quantum alternatives to asymmetric cryptography currently in use. Most attacks on these cryptosystems can be reduced to the shortest vector problem (SVP) in a lattice. Previously, the authors proposed a quantum oracle model from Grover’s algorithm to implement a hybrid quantumclassical algorithm based on the GaussSieve algorithm and solving SVP. In this paper, a new model of a quantum oracle is proposed and analyzed. Two implementations of the new quantum oracle model are proposed and estimated. The complexity of implementing the new quantum oracle model to attack post-quantum lattice-based cryptosystems that are finalists of the NIST post-quantum cryptography competition is analyzed. Comparison of obtained results for new and existing models of quantum oracle is given. 
Tab. 4, illustr. 10, bibliogr. 48.

References:
  1. D. J. Bernstein, Introduction to post-quantum cryptography, in PostQuantum Cryptography (Springer, Heidelberg, 2009), pp. 1–14.
     
  2. E. S. Malygina, A. V. Kutsenko, S. A. Novoselov, [et al.], Post-quantum cryptosystems: Open problems and solutions. Lattice-based cryptosystems, Diskretn. Anal. Issled. Oper. 30 (4), 46–90 (2023) [Russian] [J. Appl. Ind. Math. 17 (4), 767–790 (2023)].
     
  3. E. S. Malygina, A. V. Kutsenko, S. A. Novoselov, [et al.], Post-quantum cryptosystems: Open problems and solutions. Isogeny-based and code-based cryptosystems, Diskretn. Anal. Issled. Oper. 31 (1), 52–84 (2024) [Russian] [J. Appl. Ind. Math. 18 (1), 103–121 (2024)].
     
  4. J. Daemen and V. Rijmen, The Design of Rijndael (Springer, Heidelberg, 2002), DOI: 10.1007/978-3-662-04722-4.
     
  5. M. J. Dworkin, SHA-3 standard: Permutation-based hash and extendableoutput functions (Nat. Inst. Stand. Technol., Gaithersburg, MD, 2015) (Fed. Inf. Process. Stand. Publ., Vol. 202), DOI: 10.6028/NIST.FIPS.202.
     
  6. R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Commun. ACM 21 (2), 120–126 (1978).
     
  7. E. Barker, Digital signature standard (DSS) (Nat. Inst. Stand. Technol., Gaithersburg, MD, 2013) (Fed. Inf. Process. Stand. Publ., Vol. 186-4), DOI: 10.6028/NIST.FIPS.186-4.
     
  8. P. W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, in Proc. 35th Annu. Symp. Foundations of Computer Science, Santa Fe, USA, Nov. 20–22, 1994 (IEEE Comput. Soc., Los Alamitos, CA, 1994), pp. 124–134.
     
  9. G. Alagic, D. Apon, D. Cooper, [et al.], Status report on the third round of the NIST post-quantum cryptography standardization process, Nat. Inst. Stand. Technol. Interagency Internal Rep. NIST IR 8413-upd1 (NIST, Gaithersburg, MD, 2022), DOI: 10.6028/NIST.IR.8413-upd1.
     
  10. Korean Post-Quantum Cryptography Competition (Natl. Intell. Serv., Seoul, 2023), URL: kpqc.or.kr/competition.html (accessed: 9.10.2023).
     
  11. D. Micciancio, Inapproximability of the shortest vector problem: Toward a deterministic reduction, Theory Comput. 8 (1), 487–512 (2012).
     
  12. R. Kannan, Improved algorithms for integer programming and related lattice problems, in Proc. 15th Annu. ACM Symp. Theory of Computing, Boston, USA, Apr. 25–27, 1983 (ACM, New York, 1983), pp. 193–206.
     
  13. U. Fincke and M. Pohst, Improved methods for calculating vectors of short length in a lattice, including a complexity analysis, Math. Comput. 44 (170), 463–471 (1985).
     
  14. N. Gama, P. Q. Nguyen, and O. Regev, Lattice enumeration using extreme pruning, in Advances in Cryptology — EUROCRYPT 2010 (Proc. 29th Annu. Int. Conf. Theory and Application of Cryptographic Techniques, French Riviera, May 30 – June 3, 2010) (Springer, Heidelberg, 2010), pp. 257–278 (Lect. Notes Comput. Sci., Vol. 6110). 
     
  15. A. K. Lenstra, H. W. Lenstra, and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (4), 515–534 (1982), DOI: 10.1007/ BF01457454.
     
  16. Y. Chen and P. Q. Nguyen, BKZ 2.0: Better lattice security estimates, in Advances in Cryptology — ASIACRYPT 2011 (Proc. 17th Int. Conf. Theory and Application of Cryptology and Information Security, Seoul, South Korea, Dec. 4–8, 2011) (Springer, Heidelberg, 2011), pp. 1–20 (Lect. Notes Comput. Sci., Vol. 7073).
     
  17. C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theor. Comput. Sci. 53 (2–3), 201–224 (1987), DOI: 10.1016/ 0304-3975(87)90064-8.
     
  18. C. P. Schnorr and M. Euchner, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Math. Program. 66, 181–199 (1994), DOI: 10.1007/BF01581144.
     
  19. A. Becker, L. Ducas, G. Gama, and T. Laarhoven, New directions in nearest neighbor searching with applications to lattice sieving, in Proc. 27th Annu. ACM-SIAM Symp. Discrete Algorithms, Arlington, VA, USA, Jan. 10–12, 2016 (SIAM, Philadelphia, PA, 2016), pp. 10–24.
     
  20. G. Herold, E. Kirshanova, and T. Laarhoven, Speed-ups and timememory trade-offs for tuple lattice sieving, in Public-Key Cryptography — PKC 2018 (Proc. 21st IACR Int. Conf. Practice and Theory of Public-Key Cryptography, Rio de Janeiro, Brazil, Mar. 25–29, 2018), Pt. I (Springer, Cham, 2018), pp. 407–436 (Lect. Notes Comput. Sci., Vol. 10769).
     
  21. D. Micciancio and P. Voulgaris, Faster exponential time algorithms for the shortest vector problem, in Proc. 21st Annu. ACM-SIAM Symp. Discrete Algorithms, Austin, TX, USA, Jan. 17–19, 2010 (SIAM, Philadelphia, PA, 2010), pp. 1468–1480.
     
  22. P. Q. Nguyen and T. Vidick, Sieve algorithms for the shortest vector problem are practical, J. Math. Cryptol. 2 (2), 181–207 (2008), DOI: 10.1515/JMC. 2008.009.
     
  23. X. Pujol and D. Stehlé, Solving the shortest lattice vector problem in time $2^{2.465n}$ (Univ. California, San Diego, 2009) (Cryptology ePrint Archive, Pap. 2009/605). URL: eprint.iacr.org/2009/605 (accessed: 9.10.2023). 
     
  24. D. Aggarwal, D. Dadush, O. Regev, and N. Stephens-Davidowitz, Solving the shortest vector problem in $2^n$ time using discrete Gaussian sampling, in Proc. 47th ACM Symp. Theory of Computing, Portland, OR, USA, June 14–17, 2015 (ACM, New York, 2015), pp. 733–742.
     
  25. E. Doulgerakis, T. Laarhoven, and B. de Weger, Finding closest lattice vectors using approximate Voronoi cells, in Post-Quantum Cryptography (Rev. Sel. Pap. 10th Int. Conf. Chongqing, China, May 8–10, 2019) (Springer, Cham, 2019), pp. 3–22 (Lect. Notes Comput. Sci., Vol. 11505).
     
  26. D. Micciancio and P. Voulgaris A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations, in Proc. 42nd ACM Symp. Theory of Computing, Cambridge, MA, USA, June 5–8, 2010 (ACM, New York, 2010), pp. 351–358.
     
  27. D. V. Denisenko and M. V. Nikitenkova, Application of Grover’s quantum algorithm for SDES key searching, Zh. Eksp. Teor. Fiz. 155 (1), 32–53 (2019) [Russian] [J. Exp. Teor. Phys. 128 (1), 25–44 (2019)].
     
  28. D. V. Denisenko, G. B. Marshalko, M. V. Nikitenkova, V. I. Rudskoi, and V. A. Shishkin, Estimating the complexity of Grover’s algorithm for key search of block ciphers defined by GOST R 34.12-2015, Zh. Eksp. Teor. Fiz. 155 (4), 645–653 (2019) [Russian] [J. Exp. Teor. Phys. 128 (4), 552–559 (2019)].
     
  29. M. Almazrooie, A. Samsudin, R. Abdullah, and K. N. Mutter, Quantum exhaustive key search with simplified-DES as a case study, SpringerPlus 5 (1), 1–19 (2016).
     
  30. X. Dong, B. Dong, and X. Wang, Quantum attacks on some Feistel block ciphers, Des. Codes Cryptogr. 88 (6), 1179–1203 (2020), DOI: 10.1007/ s10623-020-00741-y.
     
  31. P. Frixons, M. Naya-Plasencia, and A. Schrottenloher, Quantum boomerang attacks and some applications, in Selected Areas in Cryptography (Proc. 28th Int. Conf., Virtual Event, Sept. 29 – Oct. 1, 2021) (Springer, Cham, 2021), pp. 332–352 (Lect. Notes Comput. Sci., Vol. 13203).
     
  32. S. Jaques, M. Naehrig, M. Roetteler, and F. Virdia, Implementing Grover oracles for quantum key search on AES and LowMC, in Advances in Cryptology — EUROCRYPT 2020 (Proc. 39th Annu. Int. Conf. Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020), Pt. II (Springer, Cham, 2020), pp. 280–310 (Lect. Notes Comput. Sci., Vol. 12106).
     
  33. M. Grassl, B. Langenberg, M. Roetteler, and R. Steinwandt, Applying Grover’s algorithm to AES: quantum resource estimates, in Post-Quantum Cryptography (Proc. 7th Int. Workshop, Fukuoka, Japan, Feb. 24–26, 2016) (Springer, Cham, 2016), pp. 29–43 (Lect. Notes Comput. Sci., Vol. 9606).
     
  34. B. Langenberg, H. Pham, and R. Steinwandt, Reducing the cost of implementing the advanced encryption standard as a quantum circuit, IEEE Trans. Quantum Eng. 1, 1–12 (2020).
     
  35. J. Zou, Z. Wei, S. Sun, X. Liu, and W. Wu, Quantum circuit implementations of AES with fewer qubits, in Advances in Cryptology — ASIACRYPT 2020 (Proc. 26th Int. Conf. Theory and Application of Cryptology and Information Security, Daejeon, South Korea, Dec. 7–11, 2020), Pt. II (Springer, Cham, 2020), pp. 697–726 (Lect. Notes Comput. Sci., Vol. 12492).
     
  36. M. R. Albrecht, V. Gheorghiu, E. W. Postlethwaite, and J. M. Schanck, Estimating quantum speedups for lattice sieves, in Advances in Cryptology — ASIACRYPT 2020 (Proc. 26th Int. Conf. Theory and Application of Cryptology and Information Security, Daejeon, South Korea, Dec. 7–11, 2020), Pt. II (Springer, Cham, 2020), pp. 583–613 (Lect. Notes Comput. Sci., Vol. 12492).
     
  37. C. Gidney and M. Ekerå, How to factor 2048 bit RSA integers in 8 shours using 20 million noisy qubits, Quantum 5, 433 (2021), DOI: 10.22331/q-2021-04-15-433.
     
  38. T. Laarhoven, M. Mosca, and J. van de Pol, Finding shortest lattice vectors faster using quantum search, Des. Codes Cryptogr. 77 (2–3), 375–400 (2015).
     
  39. S. Perriello, A. Barenghi, and G. Pelosi, A complete quantum circuit to solve the information set decoding problem, in Proc. 2021 IEEE Int. Conf. Quantum Computing and Engineering, Broomfield, CO, USA, Oct. 17–22, 2021 (IEEE Comput. Soc., Los Alamitos, CA, 2021), pp. 366–377.
     
  40. A. O. Bakharev, Estimates of implementation complexity for quantum cryptanalysis of post-quantum lattice-based cryptosystems, Diskretn. Anal. Issled. Oper. 30 (3), 5–42 (2023) [Russian] [J. Appl. Ind. Math. 17 (3), 459–482 (2023)].
     
  41. L. K. Grover, A fast quantum mechanical algorithm for database search, in Proc. 28th ACM Symp. Theory of Computing, Philadelphia, PA, USA, May 22–24, 1996 (ACM, New York, 1996), pp. 212–219.
     
  42. M. A. Nielsen and I. L. Chuang, Quantum computation and quantum information (Camb. Univ. Press, Cambridge, 2010).
     
  43. A. Yu. Kitaev, A. Kh. Shen, and M. N. Vyalyi, Classical and quantum computations (MTsNMO; CheRo, Moscow, 1999).
     
  44. M. Boyer, G. Brassard, P. Høyer, and A. Tapp, Tight bounds on quantum searching, Fortschr. Phys. 46 (4–5), 493–505 (1998), DOI: 10.1145/ 237814.237866.
     
  45. C. Moore and M. Nilsson, Parallel quantum computation and quantum codes, SIAM J. Comput. 31 (3), 799–815 (2001).
     
  46. C. Chen, O. Danba, J. Hoffstein, [et al.], NTRU Algorithm Specifications and Supporting Documentation (Eindh. Univ. Technol., Eindhoven, 2019), URL: ntru.org/f/ntru-20190330.pdf (accessed: 9.10.2023).
     
  47. J.-P. D’Anvers, A. Karmakar, S. S. Roy, and F. Vercauteren, SABER: Mod-LWR Based KEM (KU Leuven, Leuven, 2017), URL: esat.kuleuven.be/ cosic/pqcrypto/saber/files/saberspecround1.pdf (accessed: 9.10.2023).
     
  48. R. Avanzi, J. Bos, L. Ducas, [et al.], CRYSTALS-Kyber Algorithm Specifications and Supporting Documentation (Cent. Wiskd. Inform., Amsterdam, 2021), URL: cryptojedi.org/papers/kybernist-20171130.pdf (accessed: 9.10.2023).