Geodesic
A new quantum oracle model for a hybrid quantum-classical attack on post-quantum lattice-based cryptosystems
Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 3, pp. 24-53 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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 quantum-classical 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.
Keywords: quantum search, public-key cryptography, lattice-based cryptography, post-quantum cryptography, Grover's algorithm, quantum computation. 
@article{DA_2024_31_3_a1,
     author = {A. O. Bakharev},
     title = {A new quantum oracle model for~a~hybrid~quantum-classical~attack on~post-quantum lattice-based cryptosystems},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {24--53},
     year = {2024},
     volume = {31},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2024_31_3_a1/}
}
TY  - JOUR
AU  - A. O. Bakharev
TI  - A new quantum oracle model for a hybrid quantum-classical attack on post-quantum lattice-based cryptosystems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2024
SP  - 24
EP  - 53
VL  - 31
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/DA_2024_31_3_a1/
LA  - ru
ID  - DA_2024_31_3_a1
ER  - 
%0 Journal Article
%A A. O. Bakharev
%T A new quantum oracle model for a hybrid quantum-classical attack on post-quantum lattice-based cryptosystems
%J Diskretnyj analiz i issledovanie operacij
%D 2024
%P 24-53
%V 31
%N 3
%U http://geodesic.mathdoc.fr/item/DA_2024_31_3_a1/
%G ru
%F DA_2024_31_3_a1
A. O. Bakharev. A new quantum oracle model for a hybrid quantum-classical attack on post-quantum lattice-based cryptosystems. Diskretnyj analiz i issledovanie operacij, Tome 31 (2024) no. 3, pp. 24-53. http://geodesic.mathdoc.fr/item/DA_2024_31_3_a1/

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

[2] E. S. Malygina, A. V. Kutsenko, S. A. Novoselov, et al., “Post-quantum cryptosystems: Open problems and solutions. Lattice-based cryptosystems”, J. Appl. Ind. Math., 17:4 (2023), 767–790 | DOI

[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”, J. Appl. Ind. Math., 18:1 (2024), 103–121 | DOI

[4] J. Daemen, V. Rijmen, The design of Rijndael, Springer, Heidelberg, 2002, 238 pp. | DOI

[5] M. J. Dworkin, SHA-3 standard: Permutation-based hash and extendable output functions, Fed. Inf. Process. Stand. Publ., 202, Nat. Inst. Stand. Technol., Gaithersburg, MD, 2015, 37 pp. | DOI

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

[7] E. Barker, Digital signature standard (DSS), Fed. Inf. Process. Stand. Publ., 186-4, Nat. Inst. Stand. Technol., Gaithersburg, MD, 2013, 131 pp. | DOI

[8] P. W. Shor, “Algorithms for quantum computation: Discrete logarithms and factoring”, Proc. 35th Annu. Symp. Foundations of Computer Science (Santa Fe, USA, Nov. 20-22, 1994), IEEE Comput. Soc., Los Alamitos, CA, 1994, 124–134 | DOI

[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, 102 pp. | DOI

[10] Korean Post-Quantum Cryptography Competition, Natl. Intell. Serv., Seoul, 2023 (accessed: 9.10.2023) kpqc.or.kr/competition.html

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

[12] R. Kannan, “Improved algorithms for integer programming and related lattice problems”, Proc. 15th Annu. ACM Symp. Theory of Computing (Boston, USA, Apr. 25-27, 1983), ACM, New York, 1983, 193–206

[13] U. Fincke, M. Pohst, “Improved methods for calculating vectors of short length in a lattice, including a complexity analysis”, Math. Comput., 44:170 (1985), 463–471 | DOI

[14] N. Gama, P. Q. Nguyen, O. Regev, “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), Lect. Notes Comput. Sci., 6110, Springer, Heidelberg, 2010, 257–278 | DOI

[15] A. K. Lenstra, H. W. Lenstra, L. Lovasz, “Factoring polynomials with rational coefficients”, Math. Ann., 261:4 (1982), 515–534 | DOI

[16] Y. Chen, P. Q. Nguyen, “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), Lect. Notes Comput. Sci., 7073, Springer, Heidelberg, 2011, 1–20 | DOI

[17] C. P. Schnorr, “A hierarchy of polynomial time lattice basis reduction algorithms”, Theor. Comput. Sci., 53:2-3 (1987), 201–224 | DOI

[18] C. P. Schnorr, M. Euchner, “Lattice basis reduction: Improved practical algorithms and solving subset sum problems”, Math. Program, 66 (1994), 181–199 | DOI

[19] A. Becker, L. Ducas, G. Gama, T. Laarhoven, “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

[20] G. Herold, E. Kirshanova, T. Laarhoven, “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), v. I, Lect. Notes Comput. Sci., 10769, Springer, Cham, 2018, 407–436 | DOI

[21] D. Micciancio, P. Voulgaris, “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

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

[23] X. Pujol, D. Stehle, Solving the shortest lattice vector problem in time $2^{2.465n}$, Cryptol. ePrint Archive, ID 2009/605, , Univ. California, San Diego, 2009 (accessed: 9.10.2023) eprint.iacr.org/2009/605

[24] Aggarwal D., Dadush D., Regev O., Stephens-Davidowitz N., “Solving the shortest vector problem in 2n time using discrete Gaussian sampling”, Proc. 47th ACMSymp. Theory of Computing (Portland, OR, USA, June 14-17, 2015), ACM, New York, 2015, 733–742

[25] E. Doulgerakis, T. Laarhoven, B. de Weger, “Finding closest lattice vectors using approximate Voronoi cells”, Post-quantum cryptography, Rev. Sel. Pap. 10th Int. Conf. (Chongqing, China, May 8-10, 2019), Lect. Notes Comput. Sci., 11505, Springer, Cham, 2019, 3–22 | DOI

[26] D. Micciancio, P. Voulgaris, “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), ACM, New York, 2010, 351–358

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

[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”, J. Exp. Teor. Phys., 128:4 (2019), 552–559 | DOI | DOI

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

[30] X. Dong, B. Dong, X. Wang, “Quantum attacks on some Feistel block ciphers”, Des. Codes Cryptogr, 88:6 (2020), 1179–1203 | DOI

[31] P. Frixons, M. Naya-Plasencia, A. Schrottenloher, “Quantum boomerang attacks and some applications”, Selected areas in cryptography, Proc. 28th Int. Conf. (Virtual Event, Sept. 29-Oct. 1, 2021), Lect. Notes Comput. Sci., 13203, Springer, Cham, 2021, 332–352 | DOI

[32] S. Jaques, M. Naehrig, M. Roetteler, F. Virdia, “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), v. II, Lect. Notes Comput. Sci., 12106, Springer, Cham, 2020, 280–310 | DOI

[33] M. Grassl, B. Langenberg, M. Roetteler, R. Steinwandt, “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

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

[35] J. Zou, Z. Wei, S. Sun, X. Liu, W. Wu, “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), v. II, Lect. Notes Comput. Sci., 12492, Springer, Cham, 2020, 697–726 | DOI

[36] M. R. Albrecht, V. Gheorghiu, E. W. Postlethwaite, J. M. Schanck, “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), v. II, Lect. Notes Comput. Sci., 12492, Springer, Cham, 2020, 583–613 | DOI

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

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

[39] S. Perriello, A. Barenghi, G. Pelosi, “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), IEEE Comput. Soc., Los Alamitos, CA, 2021, 366–377 | DOI

[40] A. O. Bakharev, “Estimates of implementation complexity for quantum cryptanalysis of post-quantum lattice-based cryptosystems”, J. Appl. Ind. Math., 17:3 (2023), 459–482 | DOI

[41] L. K. Grover, “A fast quantum mechanical algorithm for database search”, Proc. 28th ACM Symp. Theory of Computing (Philadelphia, PA, USA, May 22-24, 1996), ACM, New York, 1996, 212–219 | DOI

[42] M. A. Nielsen, I. L. Chuang, Quantum computation and quantum information, Camb. Univ. Press, Cambridge, 2010, 676 pp.

[43] A. Yu. Kitaev, A. Kh. Shen, and M. N. Vyalyi, Classical and quantum computations, MTsNMO; CheRo, M., 1999

[44] M. Boyer, G. Brassard, P. Hoyer, A. Tapp, “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

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

[46] C. Chen, O. Danba, J. Hoffstein et al., NTRU algorithm specifications and supporting documentation, Eindh. Univ. Technol., Eindhoven, 2019 (accessed: 9.10.2023) https://ntru.org/f/ntru-20190330.pdf

[47] J. P. D'Anvers, A. Karmakar, S. S. Roy, F. Vercauteren, SABER: Mod-LWR based KEM, KU Leuven, Leuven, 2017 (accessed: 9.10.2023) https://www.esat.kuleuven.be/cosic/pqcrypto/saber/files/saberspecround1.pdf

[48] R. Avanzi, J. Bos, L. Ducas et al., CRYSTALS-Kyber algorithm specifications and supporting documentation, Cent. Wiskd. Inform, Amsterdam, 2021 (accessed: 9.10.2023) https://cryptojedi.org/papers/kybernist-20171130.pdf