Оценки сложности реализации квантового криптоанализа постквантовых криптосистем, основанных на решётках

Оценки сложности реализации квантового криптоанализа постквантовых криптосистем, основанных на решётках

Бахарев А. О.
Дискретный анализ и исследование операций, 30, 3, 5-42 (2023)
Скачать статью

УДК 519.7 
DOI: 10.33048/daio.2023.30.756

Аннотация:

В силу развития квантовых вычислений возникает необходимость в разработке и анализе криптосистем, устойчивых к атакам с использованием квантового компьютера — алгоритмов постквантовой криптографии. Стойкость многих известных постквантовых криптосистем, основанных на теории решёток, базируется на сложности решения проблемы нахождения кратчайшего вектора в решетке (SVP). В настоящей статье разработана и описана модель квантового оракула из алгоритма Гровера для реализации гибридного квантово-классического алгоритма на основе GaussSieve, который может быть использован для атак на криптосистемы, стойкость которых зависит от решения задачи SVP. Получены выражения для верхних оценок числа кубитов и глубины схемы двух реализаций предложенной модели квантового оракула: минимизирующей число кубитов и минимизирующей глубину схемы. Проанализирована сложность реализации предложенной модели квантового оракула для атаки на постквантовые криптосистемы, основанные на решётках и являющиеся финалистами конкурса постквантовой криптографии NIST. 
Табл. 6, ил. 12, библиогр. 34.

Литература:
  1. ГОСТ Р 34.12—2015. Информационная технология. Криптографическая защита информации. Блочные шифры. Введ. 1.01.2016. М.: Стандартинформ, 2015. 25 с.
     
  2. Денисенко Д. В., Маршалко Г. Б., Никитенкова М. В., Рудской В. И., Шишкин В. А. Оценка сложности реализации алгоритма Гровера для перебора ключей алгоритмов блочного шифрования ГОСТ Р 34.12—2015 // Журн. эксперим. и теор. физики. 2019. Т. 155, № 4. С. 645–653.
     
  3. 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).
     
  4. 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 Appl. Cryptogr. Techn. (Zagreb, Croatia, May 10–14, 2020). Pt. II. Cham: Springer, 2020. P. 280–310. (Lect. Notes Comput. Sci.; V. 12106).
     
  5. 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.
     
  6. 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 Appl. Cryptol. Inf. Secur. (Daejeon, South Korea, Dec. 7–11, 2020). Pt. II. Cham: Springer, 2020. P. 697–726. (Lect. Notes Comput. Sci.; V. 12492).
     
  7. 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.
     
  8. Денисенко Д. В., Никитенкова М. В. Применение квантового алгоритма Гровера в задаче поиска ключа блочного шифра SDES // Журн. эксперим. и теор. физики. 2019. Т. 155, № 1. С. 32–53.
     
  9. Bernstein D. J. Introduction to post-quantum cryptography // Post-quantum cryptography. Heidelberg: Springer, 2009. P. 1–14.
     
  10. Alagic G., Alperin-Sheriff J., Apon D. [et al.]. Status report on the second round of the NIST post-quantum cryptography standardization process. Nat. Inst. Stand. Technol. interag. intern. rep. 8309. Gaithersburg, MD: NIST, 2020. 39 p. Available at doi.org/10.6028/NIST.IR.8309 (accessed Apr. 26, 2023).
     
  11. 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 Appl. Cryptol. Inf. Secur. (Daejeon, South Korea, Dec. 7–11, 2020). Pt. II. Cham: Springer, 2020. P. 583–613. (Lect. Notes Comput. Sci.; V. 12492).
     
  12.  Perriello S., Barenghi A., Pelosi G. A complete quantum circuit to solve the information set decoding problem // Proc. 2021 IEEE Int. Conf. Quantum Comput. Eng. (Broomfield, CO, USA, Oct. 17–22, 2021). Los Alamitos, CA: IEEE Comput. Soc., 2021. P. 366–377.
     
  13. Micciancio D. Inapproximability of the shortest vector problem: Toward a deterministic reduction // Theory Comput. 2012. V. 8, No. 1. P. 487–512.
     
  14. 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.
     
  15. Pujol X., Stehl´e D. Solving the shortest lattice vector problem in time 2 2,465n. San Diego: Univ. California, 2009. (Cryptol. ePrint Archive; Pap. 2009/605). Available at eprint.iacr.org/2009/605 (accessed Apr. 26, 2023). 
     
  16. 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.
     
  17. Laarhoven T. Sieving for shortest vectors in lattices using angular locality-sensitive hashing // Advances in cryptology — CRYPTO 2015. Proc. 35th Annu. Cryptol. Conf. (Santa Barbara, CA, USA, Aug. 16–20, 2015). Pt. I. Heidelberg: Springer, 2015. P. 3–22. (Lect. Notes Comput. Sci.; V. 9215).
     
  18. Micciancio D., Voulgaris P. A deterministic single exponential time algorithm for most lattice problems based on Voronoi cell computations // Proc. 42nd ACM Symp. Theory Comput. (Cambridge, MA, USA, June 5–8, 2010). New York: ACM, 2010. P. 351–358.
     
  19. 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 Comput. (Portland, OR, USA, June 14–17, 2015). New York: ACM, 2015. P. 733-742.
     
  20. Bai S., Laarhoven T., Stehlé D. Tuple lattice sieving // LMS J. Comput. Math. 2016. V. 19, No. A. P. 146–162.
     
  21. 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. 2016. P. 10–24.
     
  22. Laarhoven T., Mosca M., van de Pol J. Finding shortest lattice vectors faster using quantum search // Des. Codes Cryptogr. 2015. V. 77, No. 2. P. 375–400.
     
  23. Grover L. K. A fast quantum mechanical algorithm for database search // Proc. 28th ACM Symp. Theory Comput. (Philadelphia, PA, USA, May 22–24, 1996). New York: ACM, 1996. P. 212–219.
     
  24. Nielsen M. A., Chuang I. L. Quantum computation and quantum information. Cambridge: Camb. Univ. Press, 2010.
     
  25. Boyer M., Brassard G., Hoyer P., Tapp A. Tight bounds on quantum searching // Fortschr. Phys. 1998. V. 46, No. 4–5. P. 493–505.
     
  26. Moore C., Nilsson M. Parallel quantum computation and quantum codes // SIAM J. Comput. 2001. V. 31, No. 3. P. 799–815.
     
  27. Diffie W., Hellman M. E. New directions in cryptography // IEEE Trans. Inf. Theory. 1976. V. 22, No. 6. P. 644–654.
     
  28. 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.
     
  29. Shor P. W. Algorithms for quantum computation: Discrete logarithms and factoring // Proc. 35th Annu. Symp. Found. Comput. Sci. (Santa Fe, USA, Nov. 20–22, 1994). Los Alamitos, CA: IEEE Comput. Soc., 1994. P. 124–134. 
     
  30. 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.
     
  31. Chen C., Danba O., Hoffstein J. [et al.]. NTRU. Algorithm specifications and supporting documentation. Eindhoven: Eindh. Univ. Technol., 2019. Available at ntru.org/f/ntru-20190330.pdf (accessed Apr. 26, 2023).
     
  32.  D’Anvers J.-P., Karmakar A., Roy S. S., Vercauteren F. SABER: ModLWR based KEM. Leuven: KU Leuven, 2017. Available at esat.kuleuven.be/cosic/pqcrypto/saber/files/saberspecround1.pdf (accessed Apr. 26, 2023).
     
  33. Avanzi R., Bos J., Ducas L. [et al.]. CRYSTALS-Kyber. Algorithm specifications and supporting documentation. Amsterdam: Cent. Wiskd. Inform., 2021. Available at pq-crystals.org/kyber/data/kyber-specificationround3-20210131.pdf (accessed Apr. 26, 2023).
     
  34. 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. interag. intern. rep. NIST IR 8413-upd1. Gaithersburg, MD: NIST, 2022. 102 p. Available at doi.org/10.6028/NIST.IR.8413-upd1 (accessed Apr. 26, 2023).

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

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

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

Статья поступила 18 ноября 2022 г. 
После доработки — 21 марта 2023 г. 
Принята к публикации 3 апреля 2023 г.

Abstract:

Due to the development of quantum computing, there is a need for the development and analysis of cryptosystems resistant to attacks using a quantum computer (post-quantum cryptography algorithms). The security of many well-known post-quantum cryptosystems based on lattice theory depends on the complexity of solving the shortest vector problem (SVP). In this paper, a model of quantum oracle developed from Grover’s algorithm is described to implement a hybrid quantum-classical algorithm based on GaussSieve. This algorithm can be used for attacks on cryptosystems, the security of which depends on solving the SVP problem. Upper bounds for the number of qubits and the depth of the circuit were obtained for two implementations of the proposed quantum oracle model: minimizing the number of qubits and minimizing the circuit depth. The complexity of implementing the proposed quantum oracle model to attack post-quantum lattice-based cryptosystems that are finalists of the NIST post-quantum cryptography competition is analyzed. 
Tab. 6, illustr. 12, bibliogr. 34.

References:
  1. Information technology. Cryptographic data security. Block ciphers, GOST R 34.12—2015 (Standartinform, Moscow, 2015) [Russian].
     
  2. 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. Éksp. Teor. Fiz. 155 (4), 645–653 (2019) [Russian] [J. Exp. Theor. Phys. 128 (4), 552–559 (2019)].
     
  3. 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).
     
  4. 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 Appl. Cryptogr. Techn., Zagreb, Croatia, May 10–14, 2020), Pt. II (Springer, Cham, 2020), pp. 280–310 (Lect. Notes Comput. Sci., Vol. 12106).
     
  5. 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).
     
  6. 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 Appl. Cryptol. Inf. Secur., Daejeon, South Korea, Dec. 7–11, 2020), Pt. II (Springer, Cham, 2020), pp. 697–726 (Lect. Notes Comput. Sci., Vol. 12492). 
     
  7. 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).
     
  8. D. V. Denisenko and M. V. Nikitenkova, Application of Grover’s quantum algorithm for SDES key searching, Zh. Éksp. Teor. Fiz. 155 (1), 32–53 (2019) [Russian] [J. Exp. Theor. Phys. 128 (1), 25–44 (2019)].
     
  9. D. J. Bernstein, Introduction to post-quantum cryptography, in Post-Quantum Cryptography (Springer, Heidelberg, 2009), pp. 1–14.
     
  10. G. Alagic, J. Alperin-Sheriff, D. Apon, [et al.], Status report on the second round of the NIST post-quantum cryptography standardization process, Nat. Inst. Stand. Technol. Interag. Intern. Rep. 8309 (NIST, Gaithersburg, MD, 2020). Available at doi.org/10.6028/NIST.IR.8309 (accessed Apr. 26, 2023).
     
  11. 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 Appl. Cryptol. Inf. Secur., Daejeon, South Korea, Dec. 7–11, 2020), Pt. II (Springer, Cham, 2020), pp. 583–613 (Lect. Notes Comput. Sci., Vol. 12492).
     
  12. 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 Comput. Eng., Broomfield, CO, USA, Oct. 17–22, 2021 (IEEE Comput. Soc., Los Alamitos, CA, 2021), pp. 366–377.
     
  13. D. Micciancio, Inapproximability of the shortest vector problem: Toward a deterministic reduction, Theory Comput. 8 (1), 487–512 (2012).
     
  14. 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.
     
  15. X. Pujol and D. Stehlé, Solving the shortest lattice vector problem in time 2 2,465n (Univ. California, San Diego, 2009) (Cryptol. ePrint Archive, Pap. 2009/605). Available at eprint.iacr.org/2009/605 (accessed Apr. 26, 2023). 
     
  16. P. Q. Nguyen and T. Vidick, Sieve algorithms for the shortest vector problem are practical, J. Math. Cryptol. 2 (2), 181–207 (2008).
     
  17. T. Laarhoven, Sieving for shortest vectors in lattices using angular locality-sensitive hashing, in Advances in Cryptology — CRYPTO 2015 (Proc. 35th Annu. Cryptol. Conf., Santa Barbara, CA, USA, Aug. 16–20, 2015), Pt. I (Springer, Heidelberg, 2015), pp. 3–22 (Lect. Notes Comput. Sci., Vol. 9215).
     
  18. 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 Comput., Cambridge, MA, USA, June 5–8, 2010 (ACM, New York, 2010), pp. 351–358.
     
  19. 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 Comput., Portland, OR, USA, June 14–17, 2015 (ACM, New York, 2015), pp. 733-742.
     
  20. S. Bai, T. Laarhoven, and D. Stehlé, Tuple lattice sieving, LMS J. Comput. Math. 19 (A), 146–162 (2016).
     
  21. 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.
     
  22. T. Laarhoven, M. Mosca, and J. van de Pol, Finding shortest lattice vectors faster using quantum search, Des. Codes Cryptogr. 77 (2), 375–400 (2015).
     
  23. L. K. Grover, A fast quantum mechanical algorithm for database search, in Proc. 28th ACM Symp. Theory Comput., Philadelphia, PA, USA, May 22–24, 1996 (ACM, New York, 1996), pp. 212–219.
     
  24. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Camb. Univ. Press, Cambridge, 2010).
     
  25. M. Boyer, G. Brassard, P. Hoyer, and A. Tapp, Tight bounds on quantum searching, Fortschr. Phys. 46 (4–5), 493–505 (1998).
     
  26. C. Moore and M. Nilsson, Parallel quantum computation and quantum codes, SIAM J. Comput. 31 (3), 799–815 (2001).
     
  27. W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inf. Theory 22 (6), 644–654 (1976).
     
  28. 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).
     
  29. P. W. Shor, Algorithms for quantum computation: Discrete logarithms and factoring, in Proc. 35th Annu. Symp. Found. Comput. Sci., Santa Fe, USA, Nov. 20–22, 1994 (IEEE Comput. Soc., Los Alamitos, CA, 1994), pp. 124–134.
     
  30. C. Gidney and M. Ekerå, How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits, Quantum 5, 433 (2021).
     
  31. C. Chen, O. Danba, J. Hoffstein, [et al.], NTRU. Algorithm specifications and supporting documentation (Eindh. Univ. Technol., Eindhoven, 2019). Available at ntru.org/f/ntru-20190330.pdf (accessed Apr. 26, 2023).
     
  32. J.-P. D’Anvers, A. Karmakar, S. S. Roy, and F. Vercauteren, SABER: Mod-LWR based KEM (KU Leuven, Leuven, 2017). Available at esat.kuleuven.be/cosic/pqcrypto/saber/files/saberspecround1.pdf (accessed Apr. 26, 2023). 
     
  33. R. Avanzi, J. Bos, L. Ducas, [et al.], CRYSTALS-Kyber. Algorithm specifications and supporting documentation (Cent. Wiskd. Inform., Amsterdam, 2021). Available at pq-crystals.org/kyber/data/kyber-specification-round3-20210131.pdf (accessed Apr. 26, 2023).
     
  34. 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. Interag. Intern. Rep. NIST IR 8413-upd1 (NIST, Gaithersburg, MD, 2022). Available at doi.org/10.6028/NIST.IR.8413-upd1 (accessed Apr. 26, 2023).