Geodesic
Estimates of implementation complexity for quantum cryptanalysis of post-quantum lattice-based cryptosystems
Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 3, pp. 5-42.

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: quantum search, public-key cryptography, lattice-based cryptography, post-quantum cryptography, Grover's algorithm, quantum computation. 
@article{DA_2023_30_3_a0,
     author = {A. O. Bakharev},
     title = {Estimates of implementation complexity for quantum cryptanalysis of post-quantum lattice-based cryptosystems},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--42},
     publisher = {mathdoc},
     volume = {30},
     number = {3},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2023_30_3_a0/}
}
TY  - JOUR
AU  - A. O. Bakharev
TI  - Estimates of implementation complexity for quantum cryptanalysis of post-quantum lattice-based cryptosystems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2023
SP  - 5
EP  - 42
VL  - 30
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2023_30_3_a0/
LA  - ru
ID  - DA_2023_30_3_a0
ER  - 
%0 Journal Article
%A A. O. Bakharev
%T Estimates of implementation complexity for quantum cryptanalysis of post-quantum lattice-based cryptosystems
%J Diskretnyj analiz i issledovanie operacij
%D 2023
%P 5-42
%V 30
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2023_30_3_a0/
%G ru
%F DA_2023_30_3_a0
A. O. Bakharev. Estimates of implementation complexity for quantum cryptanalysis of post-quantum lattice-based cryptosystems. Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 3, pp. 5-42. http://geodesic.mathdoc.fr/item/DA_2023_30_3_a0/

[1] Information technology. Cryptographic data security. Block ciphers, GOST R 34.12—2015, Standartinform, M., 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”, J. Exp. Theor. Phys., 128:4 (2019), 552–559 | DOI | DOI

[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), Lect. Notes Comput. Sci., 9606, Springer, Cham, 2016, 29–43 | DOI | MR | Zbl

[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), v. II, Lect. Notes Comput. Sci., 12106, Springer, Cham, 2020, 280–310 | DOI | MR | Zbl

[5] Langenberg B., Pham H., Steinwandt R., “Reducing the cost of implementing the advanced encryption standard as a quantum circuit”, IEEE Trans. Quantum Eng., 1 (2020), 1–12 | DOI | MR

[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), v. II, Lect. Notes Comput. Sci., 12492, Springer, Cham, 2020, 697–726 | DOI | MR | Zbl

[7] Almazrooie M., Samsudin A., Abdullah R., Mutter K. N., “Quantum exhaustive key search with simplified-DES as a case study”, SpringerPlus, 5:1 (2016), 1–19 | DOI

[8] D. V. Denisenko and M. V. Nikitenkova, “Application of Grover's quantum algorithm for SDES key searching”, J. Exp. Theor. Phys., 128:1 (2019), 25–44 | DOI | DOI

[9] Bernstein D. J., “Introduction to post-quantum cryptography”, Post-quantum cryptography, Springer, Heidelberg, 2009, 1–14 | MR | Zbl

[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, NIST, Gaithersburg, MD, 2020, 39 pp. (accessed Apr. 26, 2023) | DOI

[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), v. II, Lect. Notes Comput. Sci., 12492, Springer, Cham, 2020, 583–613 | DOI | MR | Zbl

[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), IEEE Comput. Soc., Los Alamitos, CA, 2021, 366–377 | DOI

[13] Micciancio D., “Inapproximability of the shortest vector problem: Toward a deterministic reduction”, Theory Comput., 8:1 (2012), 487–512 | DOI | MR | Zbl

[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), SIAM, Philadelphia, PA, 2010, 1468–1480 | DOI | MR | Zbl

[15] Pujol X., Stehlé D., Solving the shortest lattice vector problem in time $2^{2{,}465n}$, Cryptol. Archive; Pap. 2009/605 , Univ. California, San Diego, 2009 (accessed Apr. 26, 2023) eprint.iacr.org/2009/605

[16] Nguyen P. Q., Vidick T., “Sieve algorithms for the shortest vector problem are practical”, J. Math. Cryptol., 2:2 (2008), 181–207 | DOI | MR | Zbl

[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), v. I, Lect. Notes Comput. Sci., 9215, Springer, Heidelberg, 2015, 3–22 | DOI | MR | Zbl

[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), ACM, New York, 2010, 351–358 | MR | Zbl

[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), ACM, New York, 2015, 733–742 | MR | Zbl

[20] Bai S., Laarhoven T., Stehlé D., “Tuple lattice sieving”, LMS J. Comput. Math., 19:A (2016), 146–162 | DOI | MR

[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), SIAM, Philadelphia, PA, 2016, 10–24 | DOI | MR | Zbl

[22] Laarhoven T., Mosca M., van de Pol J., “Finding shortest lattice vectors faster using quantum search”, Des. Codes Cryptogr., 77:2 (2015), 375–400 | DOI | MR | Zbl

[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), ACM, New York, 1996, 212–219 | MR | Zbl

[24] Nielsen M. A., Chuang I. L., Quantum computation and quantum information, Camb. Univ. Press, Cambridge, 2010 | MR | Zbl

[25] Boyer M., Brassard G., Hoyer P., Tapp A., “Tight bounds on quantum searching”, Fortschr. Phys., 46:4–5 (1998), 493–505 | 3.0.CO;2-P class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI

[26] Moore C., Nilsson M., “Parallel quantum computation and quantum codes”, SIAM J. Comput., 31:3 (2001), 799–815 | DOI | MR | Zbl

[27] Diffie W., Hellman M. E., “New directions in cryptography”, IEEE Trans. Inf. Theory, 22:6 (1976), 644–654 | DOI | MR | Zbl

[28] Rivest R. L., Shamir A., Adleman L., “A method for obtaining digital signatures and public-key cryptosystems”, Commun. ACM, 21:2 (1978), 120–126 | DOI | MR | Zbl

[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), IEEE Comput. Soc., Los Alamitos, CA, 1994 | MR

[30] Gidney C., Ekerå M., “How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits”, Quantum, 5 (2021), 433 | DOI

[31] Chen C., Danba O., Hoffstein J. et al., NTRU. Algorithm specifications and supporting documentation, Eindh. Univ. Technol., Eindhoven, 2019 (accessed Apr. 26, 2023) ntru.org/f/ntru-20190330.pdf

[32] D'Anvers J.-P., Karmakar A., Roy S. S., Vercauteren F., SABER: Mod-LWR based KEM, KU Leuven, Leuven, 2017 (accessed Apr. 26, 2023) esat.kuleuven.be/cosic/pqcrypto/saber/files/saberspecround1.pdf | MR

[33] Avanzi R., Bos J., Ducas L. et al., CRYSTALS-Kyber. Algorithm specifications and supporting documentation, Cent. Wiskd. Inform., Amsterdam (accessed Apr. 26, 2023) pq-crystals.org/kyber/data/kyber-specification-round3-20210131.pdf

[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, NIST, Gaithersburg, MD, 2022, 102 pp. (accessed Apr. 26, 2023) | DOI