Постквантовые криптосистемы: открытые вопросы и существующие решения. Криптосистемы на решётках

Постквантовые криптосистемы: открытые вопросы и существующие решения. Криптосистемы на решётках

Малыгина Е. С., Куценко А. В., Новосёлов С. А., Колесников Н. С., Бахарев А. О., Хильчук И. С., Шапоренко А. С., Токарева Н. Н.
Дискретный анализ и исследование операций, 30, 4, 46–90 (2023)
Скачать статью

УДК 519.7 
DOI: 10.33048/daio.2023.30.771

Аннотация:

Постквантовая криптография является актуальной областью теоретических и прикладных исследований, включающей в себя разработку и анализ методов криптографической защиты информации, применяемых в условиях широкого использования квантовых вычислений. В работе приведён обзор основных подходов к построению постквантовых криптографических систем, используемых в настоящее время. Подробно рассмотрено направление, в рамках которого предлагаются криптосистемы, стойкость которых основывается на вычислительной трудности ряда задач из теории решёток, представлен сложностной статус данных задач. Приведено описание и характеристики некоторых известных криптосистем, стойкость которых основана на сложности таких задач, как задача нахождения кратчайшего вектора, задача обучения с ошибками, а также их вариаций. Разобраны основные подходы к решению задач из теории решёток, лежащие в основе атак на соответствующие криптосистемы. В частности, приведены теоретические оценки времени работы и объёма используемой памяти для известных алгоритмов редукции и просеивания решёток. 
Табл. 6, ил. 1, библогр. 93.

Литература:
  1. Bernstein D. J. Introduction to post-quantum cryptography // Post-quantum cryptography. Heidelberg: Springer, 2009. P. 1–14. 
     
  2. 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. 
     
  3. Bennett C. H., Brassard G. Quantum cryptography: Public key distribution and coin tossing // Theor. Comput. Sci. 2014. V. 560. P. 7–11. 
     
  4. Манин Ю. И. Вычислимое и невычислимое. М.: Сов. радио, 1980. 128 с. 
     
  5. Feynman R. P. Simulating physics with computers // Int. J. Theor. Phys. 1982. V. 21. P. 467–468. 
     
  6. Deutsch D. Quantum theory, the Church — Turing principle and the universal quantum computer // Proc. R. Soc. Lond. Ser. A. Math. Phys. Sci. 1985. V. 400, No. 1818. P. 97–117. 
     
  7. Deutsch D., Jozsa R. Rapid solution of problems by quantum computation // Proc. R. Soc. Lond. Ser. A. Math. Phys. Sci. 1992. V. 439, No. 1907. P. 553–558. 
     
  8. Bernstein E., Vazirani U. Quantum complexity theory // SIAM J. Comput. 1997. V. 26, No. 5. P. 1411–1473. 
     
  9. Simon D. R. On the power of quantum computation // SIAM J. Comput. 1997. V. 26, No. 5. P. 1474–1483. 
     
  10. Nielsen M. A., Chuang I. L. Quantum computation and quantum information. Cambridge: Camb. Univ. Press, 2010. 
     
  11. 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. 
     
  12. Proos J., Zalka C. Shor’s discrete logarithm quantum algorithm for elliptic curves // Quantum Inf. Comput. 2003. V. 3, No. 4. P. 317–344. 
     
  13. 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. 
     
  14. Brassard G., Høyer P., Tapp A. Quantum cryptanalysis of hash and clawfree functions // LATIN’98: Theoretical informatics. Proc. 3rd Lat. Am. Symp. (Campinas, Brazil, Apr. 20–24, 1998). Heidelberg: Springer, 1998. P. 163–169. (Lect. Notes Comput. Sci.; V. 1380). 
     
  15. Brassard G., Høyer P., Tapp A. Quantum counting // Automata, languages and programming. Proc. 25th Int. Colloq. (Aalborg, Denmark, July 13–17, 1998). Heidelberg: Springer, 1998. P. 820–831. (Lect. Notes Comput. Sci.; V. 1443). 
     
  16. Kuwakado H., Morii M. Security on the quantum-type Even — Mansour cipher // Proc. 2012 Int. Symp. Information Theory and Its Applications (Honolulu, HI, USA, Oct. 28–31, 2012). Los Alamitos, CA: IEEE Comput. Soc., 2012. P. 312–316. 
     
  17. Dong X., Dong B., Wang X. Quantum attacks on some Feistel block ciphers // Des. Codes Cryptogr. 2020. V. 88, No. 6. P. 1179–1203. 
     
  18. Xie H., Yang L. Using Bernstein — Vazirani algorithm to attack block ciphers // Des. Codes Cryptogr. 2019. V. 87, No. 5. P. 1161–1182. 
     
  19. Leander G., May A. Grover meets Simon — quantumly attacking the FXconstruction // Advances in cryptology — ASIACRYPT 2017. Proc. 23rd Int. Conf. Theory and Applications of Cryptology and Information Security (Hong Kong, China, Dec. 3–7, 2017). Pt. II. Cham: Springer. 2017. P. 161–178. (Lect. Notes Comput. Sci.; V. 10625). 
     
  20. Kuwakado H., Morii M. Quantum distinguisher between the 3-round Feistel cipher and the random permutation // Proc. 2010 IEEE Int. Symp. Information Theory (Austin, TX, USA, June 13–18, 2010). Los Alamitos, CA: IEEE Comput. Soc., 2010. P. 2682–2685. 
     
  21. Hodžić S., Knudsen L. R. A quantum distinguisher for 7/8-round SMS4 block cipher // Quantum Inf. Process. 2020. V. 19, No. 11. Paper ID 411. 22 p. 
     
  22. Zhou Q., Lu S., Zhang Z., Sun J. Quantum differential cryptanalysis // Quantum Inf. Process. 2015. V. 14, No. 6. P. 2101–2109. 
     
  23. Shi R., Xie H., Feng H., Yuan F., Liu B. Quantum zero correlation linear cryptanalysis // Quantum Inf. Process. 2022. V. 21, No. 8. Paper ID 293. 30 p. 
     
  24. Kaplan M., Leurent G., Leverrier A., Naya-Plasencia M. Quantum differential and linear cryptanalysis // IACR Trans. Symmetric Cryptol. 2016. V. 2016, No. 1. P. 71–94. 
     
  25. Chen L., Jordan S., Liu Y.-K. [et al.]. Report on post-quantum cryptography. Nat. Inst. Stand. Technol. interag. intern. rep. NIST IR 8105. Gaithersburg, MD: NIST, 2016. 15 p. Available at doi.org/10.6028/NIST.IR.8105 (accessed Sept. 13, 2023). 
     
  26. Post-quantum cryptography. Gaithersburg, MD: NIST, 2017. Available at csrc.nist.gov/projects/post-quantum-cryptography (accessed Sept. 13, 2023). 
     
  27. Lenstra A. K., Lenstra H. W., Lovász L. Factoring polynomials with rational coefficients // Math. Ann. 1982. V. 261, No. 4. P. 515–534. 
     
  28. Shamir A. A polynomial-time algorithm for breaking the basic Merkle — Hellman cryptosystem // Advances in cryptology. Proc. Crypto 82 (Santa Barbara, USA, Aug. 23–25, 1982). New York: Plenum Press, 1983. P. 279–288. 
     
  29. Schnor C. P. A hierarchy of polynomial time lattice basis reduction algorithms // Theor. Comput. Sci. 1987. V. 53, No. 2–3. P. 201–224. 
     
  30. Schnor C. P. A more efficient algorithm for lattice basis reduction // J. Algorithms. 1988. V. 9, No. 1. P. 47–62.  
     
  31. Frieze A., Håstad J., Kannan R., Lagarias J., Shamir A. Reconstructing truncated integer variables satisfying linear congruences // SIAM J. Comput. 1988. V. 17, No. 2. 262–280. 
     
  32. Stern J., Toffin P. Cryptanalysis of a public-key cryptosystem based on approximations by rational numbers // Advances in cryptology — EUROCRYPT’90. Proc. Workshop Theory and Application of Cryptographic Techniques (Aarhus, Denmark, May 21–24, 1990). Heidelberg: Springer, 1991. P. 313–317. (Lect. Notes Comput. Sci.; V. 473). 
     
  33. Joux A., Stern J. Cryptanalysis of another knapsack cryptosystem // Advances in cryptology — ASIACRYPT’91. Proc. Int. Conf. Theory and Application of Cryptology (Fujiyoshida, Japan, Nov. 11–14, 1991). Heidelberg: Springer, 1993. P. 470–476. (Lect. Notes Comput. Sci.; V. 739). 
     
  34. Ajtai M. Generating hard instances of lattice problems (extended abstract) // Proc. 28th Annu. ACM Symp. Theory of Computing (Philadelphia, PA, USA, May 22–24, 1996). New York: ACM, 1996. P. 99–108. 
     
  35. Ajtai M., Dwork C. A public-key cryptosystem with worst-case/average-case equivalence // Proc. 29th Annu. ACM Symp. Theory of Computing (El Paso, TX, USA, May 4–6, 1997). New York: ACM, 1997. P. 284–293. 
     
  36. Goldreich O., Goldwasser S., Halevi S. Public-key cryptosystems from lattice reduction problems // Advances in cryptology — CRYPTO’97. Proc. 17th Annu. Int. Cryptology Conf. (Santa Barbara, USA, Aug. 17–21, 1997). Heidelberg: Springer, 1997. P. 112–131. (Lect. Notes Comput. Sci.; V. 1294). 
     
  37. Nguyen P., Stern J. Cryptanalysis of the Ajtai — Dwork cryptosystem // Advances in cryptology — CRYPTO’98. Proc. 18th Annu. Int. Cryptology Conf. (Santa Barbara, USA, Aug. 23–27, 1998). Heidelberg: Springer, 1998. P. 223–242. (Lect. Notes Comput. Sci.; V. 1462). 
     
  38. Nguyen P., Stern J. Cryptanalysis of the Goldreich — Goldwasser — Halevi Cryptosystem from CRYPTO’97 // Advances in cryptology — CRYPTO’99. Proc. 19th Annu. Int. Cryptology Conf. (Santa Barbara, USA, Aug. 15–19, 1999). Heidelberg: Springer, 1999. P. 288–304. (Lect. Notes Comput. Sci.; V. 1666). 
     
  39. Hoffstein J., Pipher J., Silverman J. H. NTRU: A ring-based public key cryptosystem // Algorithmic number theory. Proc. 3rd Int. Symp. (Portland, OR, USA, June 21–25, 1998). Heidelberg: Springer, 1998. P. 267–288. (Lect. Notes Comput. Sci.; V. 1423). 
     
  40. Silverman J. H., Pipher J., Hoffstein J. An introduction to mathematical cryptography. New York: Springer, 2008.  
     
  41. Silverman J. H. An introduction to lattices, lattice reduction, and latticebased cryptography // Lect. Notes 30th Annu. PCMI Graduate Summer School (Princeton, USA, July 5–25, 2020). Princeton: Inst. Adv. Study, 2020. 70 p. Available at https://www.ias.edu/sites/default/files/Silverman_PCMI_Note_DistributionVersion_220705.pdf (accessed Sept. 13, 2023). 
     
  42. Peikert C. A decade of lattice cryptography // Found. Trends Theor. Comput. Sci. 2016. V. 10, No. 4. P. 283–424.  
     
  43. Ajtai M. The shortest vector problem in $L_2$ is NP-hard for randomized reductions (extended abstract) // Proc. 30th Annu. ACM Symp. Theory of Computing (Dallas, USA, May 24–26, 1998). New York: ACM, 1998. P. 10–19. 
     
  44. Micciancio D. The shortest vector in a lattice is hard to approximate to within some constant // SIAM J. Comput. 2001. V. 30, No. 6. P. 2008–2035. 
     
  45. Haviv I., Regev O. Tensor-based hardness of the shortest vector problem to within almost polynomial factors // Proc. 39th Annu. ACM Symp. Theory of Computing (San Diego, CA, USA, June 11–13, 2007). New York: ACM, 2007. P. 469–477. 
     
  46. Aharonov D., Regev O. Lattice problems in NP $\cap$ coNP // J. ACM. 2005. V. 52, No. 5. P. 749–765. 
     
  47. Goldreich O., Micciancio D., Safra S., Seifert J.-P. Approximating shortest lattice vectors is not harder than approximating closest lattice vectors // Inf. Process. Lett. 1999. V. 71, No. 2. P. 55–61. 
     
  48. Micciancio D. Efficient reductions among lattice problems // Proc. 19th Annu. ACM-SIAM Symp. Discrete Algorithms (San Francisco, USA, Jan. 20–22, 2008). Philadelphia, PA: SIAM, 2008. P. 84–93. 
     
  49. Regev O. On lattices, learning with errors, random linear codes, and cryptography // J. ACM. 2009. V. 56, No. 6. P. 1–40. 
     
  50. Banerjee A., Peikert C., Rosen A. Pseudorandom functions and lattices // Advances in cryptology — EUROCRYPT 2012. Proc. 31st Annu. Int. Conf. Theory and Applications of Cryptographic Techniques (Cambridge, UK, Apr. 15–19, 2012). Heidelberg: Springer, 2012. P. 719–737. (Lect. Notes Comput. Sci.; V. 7237).  
     
  51. Alwen J., Krenn S., Pietrzak K., Wichs D. Learning with rounding, revisited // Advances in cryptology — CRYPTO 2013. Proc. 33rd Annu. Cryptology Conf. (Santa Barbara, USA, Aug. 18–22, 2013). Pt. I. Heidelberg: Springer, 2013. P. 57–74. (Lect. Notes Comput. Sci.; V. 8042). 
     
  52. 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. 
     
  53. 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 Sept. 13, 2023). 
     
  54. Submission requirements and evaluation criteria for the post-quantum cryptography standardization process. Gaithersburg, MD: NIST, 2016. Available at csrc.nist.gov/csrc/media/projects/post-quantum-cryptography/documents/call-for-proposals-final-dec-2016.pdf (accessed Sept. 13, 2023). 
     
  55. Avanzi R., Bos J., Ducas L. [et al.]. CRYSTALS-Kyber. Algorithm specifications and supporting documentation. Gaithersburg, MD: NIST, 2021. Available at pq-crystals.org/kyber/data/kyber-specification-round3- 20210131.pdf (accessed Sept. 13, 2023). 
     
  56. Fujisaki E., Okamoto T. Secure integration of asymmetric and symmetric encryption schemes // Advances in cryptology — CRYPTO’99. Proc. 19th Annu. Int. Cryptology Conf. (Santa Barbara, USA, Aug. 15–19, 1999). Heidelberg: Springer, 1999. P. 537–554. (Lect. Notes Comput. Sci.; V. 1666). 
     
  57. Basso A., Mera J. M. B., D’Anvers J.-P. [et al.]. SABER: mod-LWR based KEM (Round 3 Submission). Leuven: KU Leuven, 2020. Available at esat.kuleuven.be/cosic/pqcrypto/saber/files/saberspecround3.pdf (accessed Sept. 13, 2023). 
     
  58. Chen C., Danba O., Hoffstein J. [et al.]. NTRU. Algorithm specifications and supporting documentation. Eindhoven: Eindh. Univ. Technol., 2020. Available at cryptojedi.org/papers/ntrunistr3-20200930.pdf (accessed Sept. 13, 2023). 
     
  59. Targhi E. E., Unruh D. Post-quantum security of the Fujisaki — Okamoto and OAEP transforms // Theory of cryptography. Proc. 14th Int. Conf. (Beijing, China, Oct. 31 — Nov. 3, 2016). Pt. II. Heidelberg: Springer, 2016. P. 192–216. (Lect. Notes Comput. Sci.; V. 9986). 
     
  60. Alkim E., Bos J. W., Ducas L. [et al.]. FrodoKEM. Learning with errors key encapsulation: Algorithm specifications and supporting documentation. Gaithersburg, MD: NIST, 2021. Available at frodokem.org/files/FrodoKEM-specification-20210604.pdf (accessed Sept. 13, 2023). 
     
  61. Fujisaki E., Okamoto T. Secure integration of asymmetric and symmetric encryption schemes // J. Cryptol. 2013. V. 26. P. 80–101. 
     
  62. Bai S., Ducas L., Kiltz E. [et al.]. CRYSTALS-Dilithium. Algorithm specifications and supporting documentation. Gaithersburg, MD: NIST, 2021. Available at pq-crystals.org/dilithium/data/dilithium-specificationround3-20210208.pdf (accessed Sept. 13, 2023). 
     
  63. Fouque P.-A., Hoffstein J., Kirchner P. [et al.]. Falcon: Fast-fourier lattice-based compact signatures over NTRU. Gaithersburg, MD: NIST, 2020. Available at falcon-sign.info/falcon.pdf (accessed Sept. 13, 2023). 
     
  64. Coppersmith D., Shamir A. Lattice attacks on NTRU // Advances in cryptology — EUROCRYPT’97. Proc. Int. Conf. Theory and Applications of Cryptographic Techniques (Konstanz, Germany, May 11–15, 1997). Heidelberg: Springer, 1997. P. 52–61. (Lect. Notes Comput. Sci.; V. 1233). 
     
  65. Schnorr C. P., Euchner M. Lattice basis reduction: Improved practical algorithms and solving subset sum problems // Math. Program. 1994. V. 66. P. 181–199. 
     
  66. Kannan R. Improved algorithms for integer programming and related lattice problems // Proc. 15th Annu. ACM Symp. Theory of Computing (Boston, MA, USA, Apr. 25–27, 1983). New York: ACM, 1983. P. 193–206. 
     
  67. 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. 
     
  68. Gama N., Nguyen P. Q., Regev O. Lattice enumeration using extreme pruning // Advances in cryptology — EUROCRYPT 2010. Proc. 29th Annu. Int. Conf. Theory and Applications of Cryptographic Techniques (French Riviera, France, May 30 — June 3, 2010). Heidelberg: Springer, 2010. P. 257–278. (Lect. Notes Comput. Sci.; V. 6110). 
     
  69. 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). 
     
  70. Ajtai M., Kumar R., Sivakumar D. A sieve algorithm for the shortest lattice vector problem // Proc. 33rd Annu. ACM Symp. Theory of Computing (Hersonissos, Greece, July 6–8, 2001). New York: ACM, 2001. P. 601–610. 
     
  71. Pujol X., Stehlé D. Solving the shortest lattice vector problem in time 2 2,465n. San Diego: Univ. California, 2009. (Cryptology ePrint Archive; Paper ID 2009/605). Available at eprint.iacr.org/2009/605 (accessed Sept. 13, 2023). 
     
  72. 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. 
     
  73. 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. 
     
  74. 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. 
     
  75. 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). 
     
  76. 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. 
     
  77. Laarhoven T. Search problems in cryptography: From fingerprinting to lattice sieving. Eindhoven: Tech. Univ. Eindhoven, 2016. 230 p. 
     
  78. 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). 
     
  79. Kirshanova E., Mårtensson E., Postlethwaite E. W., Moulik S. R. Quantum algorithms for the approximate $k$-list problem and their application to lattice sieving // Advances in cryptology — ASIACRYPT 2019. Proc. 25th Int. Conf. Theory and Application of Cryptology and Information Security (Kobe, Japan, Dec. 8–12, 2019). Pt. I. Cham: Springer, 2019. P. 521–551. (Lect. Notes Comput. Sci.; V. 11921). 
     
  80. 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. 
     
  81. 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). 
     
  82. 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. 
     
  83. Hanrot G., Stehlé D. Improved analysis of Kannan’s shortest lattice vector algorithm // Advances in cryptology — CRYPTO 2007. Proc. 27th Annu. Cryptology Conf. (Santa Barbara, USA, Aug. 19–23, 2007). Heidelberg: Springer, 2007. P. 170–186. (Lect. Notes Comput. Sci.; V. 4622). 
     
  84. Hanrot G., Pujol X., Stehlé D. Algorithms for the shortest and closest lattice vector problems // Coding and cryptology. Proc. 3rd Int. Workshop (Qingdao, China, May 30 — June 3, 2011). Heidelberg: Springer, 2011. P. 159–190. (Lect. Notes Comput. Sci.; V. 6639). 
     
  85. Yang S. Y., Kuo P. C., Yang B. Y., Cheng C. M. Gauss sieve algorithm on GPUs // Topics in cryptology — CT-RSA 2017. Cryptographers’ Track at the RSA Conf. 2017 (San Francisco, USA, Feb. 14–17, 2017). Cham: Springer, 2017. P. 39–57. (Lect. Notes Comput. Sci.; V. 10159). 
     
  86. Bai S., Laarhoven T., Stehlé D. Tuple lattice sieving // LMS J. Comput. Math. 2016. V. 19, No. A. P. 146–162. 
     
  87. Herold G., Kirshanova E. Improved algorithms for the approximate $k$-list problem in Euclidean norm // Public-key cryptography — PKC 2017. Proc. 20th IACR Int. Conf. Practice and Theory of Public-Key Cryptography (Amsterdam, Netherlands, Mar. 28–31, 2017). Pt. I. Heidelberg: Springer, 2017. P. 16–40. (Lect. Notes Comput. Sci.; V. 10174). 
     
  88. Becker A., Gama N., Joux A. A sieve algorithm based on overlattices // LMS J. Comput. Math. 2014. V. 17, No. A. P. 49–70. 
     
  89. Laarhoven T. Sieving for shortest vectors in lattices using angular localitysensitive hashing // Advances in cryptology — CRYPTO 2015. Proc. 35th Annu. Cryptology Conf. (Santa Barbara, USA, Aug. 16–20, 2015). Pt. I. Heidelberg: Springer, 2015. P. 3–22. (Lect. Notes Comput. Sci.; V. 9215). 
     
  90. Laarhoven T., Mariano A. Progressive lattice sieving // Post-quantum cryptography. Proc. 9th Int. Conf. (Fort Lauderdale, FL, USA, Apr. 9–11, 2018). Cham: Springer, 2018. P. 292–311. (Lect. Notes Comput. Sci.; V. 10786).  
     
  91. Andoni A., Indyk P., Nguyen H. L., Razenshteyn I. Beyond localitysensitive hashing // Proc. 25th Annu. ACM-SIAM Symp. Discrete Algorithms (Portland, Oregon, USA, Jan. 5–7, 2014). Philadelphia, PA: SIAM, 2014. P. 1018–1028. 
     
  92. Laarhoven T., de Weger B. Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing // Progress in cryptology — LATINCRYPT 2015. Proc. 4th Int. Conf. Cryptology and Information Security in Latin America (Guadalajara, Mexico, Aug. 23–26, 2015). Cham: Springer, 2015. P. 101–118. (Lect. Notes Comput. Sci.; V. 9230). 
     
  93. Ducas L., Stevens M., van Woerden W. Advanced lattice sieving on GPUs, with tensor cores // Advances in cryptology — EUROCRYPT 2021. Proc. 40th Annu. Int. Conf. Theory and Applications of Cryptographic Techniques (Zagreb, Croatia, Oct. 17–21, 2021). Pt. II. Cham: Springer, 2021. P. 249–279. (Lect. Notes Comput. Sci.; V. 12697).

Работа первого, третьего и четвёртого авторов выполнена при поддержке Северозападного центра математических исследований им. С. Ковалевской (БФУ им. И. Канта) в рамках соглашения с Министерством науки и высшего образования России (соглашение № 075–02–2023–934). Работа второго, пятого, шестого, седьмого и восьмого авторов выполнена при поддержке Математического центра в Академгородке в рамках соглашения с Министерством науки и высшего образования России (соглашение № 075–15–2022–282).

Малыгина Екатерина Сергеевна
  1. Балтийский федеральный университет им. И. Канта, 
    ул. Александра Невского, 14, 236041 Калининград, Россия
  2. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: emalygina@kantiana.ru

Куценко Александр Владимирович
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: alexandrkutsenko@bk.ru

Новосёлов Семён Александрович
  1. Балтийский федеральный университет им. И. Канта, 
    ул. Александра Невского, 14, 236041 Калининград, Россия

E-mail: novsem@gmail.com

Колесников Никита Сергеевич
  1. Балтийский федеральный университет им. И. Канта, 
    ул. Александра Невского, 14, 236041 Калининград, Россия

E-mail: nikolesnikov100@gmail.com

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

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

Хильчук Ирина Сергеевна
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия

E-mail: irina.khilchuk@gmail.com

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

E-mail: shaporenko.alexandr@gmail.com

Токарева Наталья Николаевна
  1. Новосибирский гос. университет, 
    ул. Пирогова, 2, 630090 Новосибирск, Россия
  2. Балтийский федеральный университет им. И. Канта, 
    ул. Александра Невского, 14, 236041 Калининград, Россия

E-mail: crypto1127@mail.ru

Статья поступила 4 мая 2023 г. 
После доработки — 28 июля 2023 г. 
Принята к публикации 20 августа 2023 г.

Abstract:

The paper provides an overview of the main approaches to the construction of post-quantum cryptographic systems that are currently used. The area of lattice-based cryptography is analyzed in detail. We give the description and characteristics of some known lattice-based cryptosystems whose security is based on the complexity of the shortest vector problem, learning with errors problem, and their variations. The main approaches to solving the problems from lattice theory, on which attacks on the corresponding cryptosystems are based, are analyzed. In particular, some known theoretical estimates of time and memory complexity of lattice basis reduction and lattice sieving algorithms are presented. 
Tab. 6, illustr. 1, biblogr. 93.

References:
  1. D. J. Bernstein, Introduction to post-quantum cryptography, in Post-Quantum Cryptography (Springer, Heidelberg, 2009), pp. 1–14.
     
  2. C. Gidney and M. Ekerå, How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits, Quantum 5, 433 (2021).
     
  3. C. H. Bennett and G. Brassard, Quantum cryptography: Public key distribution and coin tossing, Theor. Comput. Sci. 560, 7–11 (2014).
     
  4. Yu. I. Manin, Computable and Incomputable (Sov. Radio, Moscow, 1980) [Russian].
     
  5. R. P. Feynman, Simulating physics with computers, Int. J. Theor. Phys. 21, 467–468 (1982).
     
  6. D. Deutsch, Quantum theory, the Church — Turing principle and the universal quantum computer, Proc. R. Soc. Lond. Ser. A. Math. Phys. Sci. 400 (1818), 97–117 (1985).
     
  7. D. Deutsch and R. Jozsa, Rapid solution of problems by quantum computation, Proc. R. Soc. Lond. Ser. A. Math. Phys. Sci. 439 (1907), 553–558 (1992).
     
  8. E. Bernstein and U. Vazirani, Quantum complexity theory, SIAM J. Comput. 26 (5), 1411–1473 (1997).
     
  9. D. R. Simon, On the power of quantum computation, SIAM J. Comput. 26 (5), 1474–1483 (1997).
     
  10. M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Camb. Univ. Press, Cambridge, 2010).
     
  11. 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.
     
  12. J. Proos and C. Zalka, Shor’s discrete logarithm quantum algorithm for elliptic curves, Quantum Inf. Comput. 3 (4), 317–344 (2003).
     
  13. 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.
     
  14. G. Brassard, P. Høyer and A. Tapp, Quantum cryptanalysis of hash and claw-free functions, in LATIN’98: Theoretical Informatics (Proc. 3rd Lat. Am. Symp., Campinas, Brazil, Apr. 20–24, 1998) (Springer, Heidelberg, 1998), pp. 163–169 (Lect. Notes Comput. Sci., Vol. 1380).
     
  15. G. Brassard, P. Høyer and A. Tapp, Quantum counting, in Automata, Languages and Programming (Proc. 25th Int. Colloq., Aalborg, Denmark, July 13–17, 1998) (Springer, Heidelberg, 1998), pp. 820–831 (Lect. Notes Comput. Sci., Vol. 1443).
     
  16. H. Kuwakado and M. Morii, Security on the quantum-type Even — Mansour cipher, in Proc. 2012 Int. Symp. Information Theory and Its Applications, Honolulu, HI, USA, Oct. 28–31, 2012 (IEEE Comput. Soc., Los Alamitos, CA, 2012), pp. 312–316.
     
  17. X. Dong, B. Dong, and X. Wang, Quantum attacks on some Feistel block ciphers, Des. Codes Cryptogr. 88 (6), 1179–1203 (2020).
     
  18. H. Xie and L. Yang, Using Bernstein — Vazirani algorithm to attack block ciphers, Des. Codes Cryptogr. 87 (5), 1161–1182 (2019).
     
  19. G. Leander and A. May, Grover meets Simon — quantumly attacking the FX-construction, in Advances in Cryptology — ASIACRYPT 2017 (Proc. 23rd Int. Conf. Theory and Applications of Cryptology and Information Security, Hong Kong, China, Dec. 3–7, 2017), Pt. II (Springer, Cham, 2017), pp. 161–178 (Lect. Notes Comput. Sci., Vol. 10625).
     
  20. H. Kuwakado and M. Morii, Quantum distinguisher between the 3-round Feistel cipher and the random permutation, in Proc. 2010 IEEE Int. Symp. Information Theory, Austin, TX, USA, June 13–18, 2010 (IEEE Comput. Soc., Los Alamitos, CA, 2010), pp. 2682–2685.
     
  21. S. Hodžić and L. R. Knudsen, A quantum distinguisher for 7/8-round SMS4 block cipher, Quantum Inf. Process. 19 (11), Paper ID 411 (2020).
     
  22. Q. Zhou, S. Lu, Z. Zhang, and J. Sun, Quantum differential cryptanalysis, Quantum Inf. Process. 14 (6), 2101–2109 (2015).
     
  23. R. Shi, H. Xie, H. Feng, F. Yuan, and B. Liu, Quantum zero correlation linear cryptanalysis, Quantum Inf. Process. 21 (8), Paper ID 293 (2022).
     
  24. M. Kaplan, G. Leurent, A. Leverrier, and M. Naya-Plasencia, Quantum differential and linear cryptanalysis, IACR Trans. Symmetric Cryptol. 2016 (1), 71–94 (2016).
     
  25. L. Chen, S. Jordan, Y.-K. Liu, [et al.], Report on post-quantum cryptography, Nat. Inst. Stand. Technol. Interag. Intern. Rep. NIST IR 8105 (NIST, Gaithersburg, MD, 2016). Available at doi.org/10.6028/NIST.IR.8105 (accessed Sept. 13, 2023).
     
  26. Post-Quantum Cryptography (NIST, Gaithersburg, MD, 2017). Available at csrc.nist.gov/projects/post-quantum-cryptography (accessed Sept. 13, 2023).
     
  27. A. K. Lenstra, H. W. Lenstra, and L. Lovász, Factoring polynomials with rational coefficients, Math. Ann. 261 (4), 515–534 (1982).
     
  28. A. Shamir, A polynomial-time algorithm for breaking the basic Merkle — Hellman cryptosystem, in Advances in Cryptology (Proc. Crypto 82, Santa Barbara, USA, Aug. 23–25, 1982) (Plenum Press, New York, 1983), pp. 279–288.
     
  29. C. P. Schnorr, A hierarchy of polynomial time lattice basis reduction algorithms, Theor. Comput. Sci. 53 (2–3), 201–224 (1987).
     
  30. C. P. Schnorr, A more efficient algorithm for lattice basis reduction, J. Algorithms 9 (1), 47–62 (1988).
     
  31. A. Frieze, J. Håstad, R. Kannan, J. Lagarias, and A. Shamir, Reconstructing truncated integer variables satisfying linear congruences, SIAM J. Comput. 17 (2), 262–280 (1988).
     
  32. J. Stern and P. Toffin, Cryptanalysis of a public-key cryptosystem based on approximations by rational numbers, in Advances in Cryptology — EUROCRYPT’90 (Proc. Workshop Theory and Application of Cryptographic Techniques, Aarhus, Denmark, May 21–24, 1990) (Springer, Heidelberg, 1991), pp. 313–317 (Lect. Notes Comput. Sci., Vol. 473).
     
  33. A. Joux and J. Stern, Cryptanalysis of another knapsack cryptosystem, in Advances in Cryptology — ASIACRYPT’91 (Proc. Int. Conf. Theory and Application of Cryptology, Fujiyoshida, Japan, Nov. 11–14, 1991) (Springer, Heidelberg, 1993), pp. 470–476 (Lect. Notes Comput. Sci., Vol. 739).
     
  34. M. Ajtai, Generating hard instances of lattice problems (extended abstract), in Proc. 28th Annu. ACM Symp. Theory of Computing, Philadelphia, PA, USA, May 22–24, 1996 (ACM, New York, 1996), pp. 99–108.
     
  35. M. Ajtai and C. Dwork, A public-key cryptosystem with worst-case/averagecase equivalence, in Proc. 29th Annu. ACM Symp. Theory of Computing, El Paso, TX, USA, May 4–6, 1997 (ACM, New York, 1997), pp. 284–293. 
     
  36. O. Goldreich, S. Goldwasser, and S. Halevi, Public-key cryptosystems from lattice reduction problems, in Advances in Cryptology — CRYPTO’97 (Proc. 17th Annu. Int. Cryptology Conf., Santa Barbara, USA, Aug. 17–21, 1997) (Springer, Heidelberg, 1997), pp. 112–131 (Lect. Notes Comput. Sci., Vol. 1294).
     
  37. P. Nguyen and J. Stern, Cryptanalysis of the Ajtai — Dwork cryptosystem, in Advances in Cryptology — CRYPTO’98 (Proc. 18th Annu. Int. Cryptology Conf., Santa Barbara, USA, Aug. 23–27, 1998) (Springer, Heidelberg, 1998), pp. 223–242 (Lect. Notes Comput. Sci., Vol. 1462).
     
  38. P. Nguyen and J. Stern, Cryptanalysis of the Goldreich — Goldwasser — Halevi Cryptosystem from CRYPTO’97, in Advances in Cryptology — CRYPTO’99 (Proc. 19th Annu. Int. Cryptology Conf., Santa Barbara, USA, Aug. 15–19, 1999) (Springer, Heidelberg, 1999), pp. 288–304 (Lect. Notes Comput. Sci., Vol. 1666).
     
  39. J. Hoffstein, J. Pipher, and J. H. Silverman, NTRU: A ring-based public key cryptosystem, in Algorithmic Number Theory (Proc. 3rd Int. Symp., Portland, OR, USA, June 21–25, 1998) (Springer, Heidelberg, 1998), pp. 267–288 (Lect. Notes Comput. Sci., Vol. 1423).
     
  40. J. H. Silverman, J. Pipher, and J. Hoffstein, An Introduction to Mathematical Cryptography (Springer, New York, 2008).
     
  41. J. H. Silverman, An introduction to lattices, lattice reduction, and lattice-based cryptography, in Lect. Notes 30th Annu. PCMI Graduate Summer School, Princeton, USA, July 5–25, 2020 (Inst. Adv. Study, Princeton, 2020). Available at ias.edu/sites/default/files/Silverman_PCMI_Note_DistributionVersion_220705.pdf (accessed Sept. 13, 2023).
     
  42. C. Peikert, A decade of lattice cryptography, Found. Trends Theor. Comput. Sci. 10 (4), 283–424 (2016).
     
  43. M. Ajtai, The shortest vector problem in $L_2$ is NP-hard for randomized reductions (extended abstract), in Proc. 30th Annu. ACM Symp. Theory of Computing, Dallas, USA, May 24–26, 1998 (ACM, New York, 1998), pp. 10–19.
     
  44. D. Micciancio, The shortest vector in a lattice is hard to approximate to within some constant, SIAM J. Comput. 30 (6), 2008–2035 (2001).
     
  45. I. Haviv and O. Regev, Tensor-based hardness of the shortest vector problem to within almost polynomial factors, in Proc. 39th Annu. ACM Symp. Theory of Computing, San Diego, CA, USA, June 11–13, 2007 (ACM, New York, 2007), pp. 469–477.
     
  46. D. Aharonov and O. Regev, Lattice problems in NP $\cap$ coNP, J. ACM 52 (5), 749–765 (2005).
     
  47. O. Goldreich, D. Micciancio, S. Safra, and J.-P. Seifert, Approximating shortest lattice vectors is not harder than approximating closest lattice vectors, Inf. Process. Lett. 71 (2), 55–61 (1999).
     
  48. D. Micciancio, Efficient reductions among lattice problems, in Proc. 19th Annu. ACM-SIAM Symp. Discrete Algorithms, San Francisco, USA, Jan. 20–22, 2008 (SIAM, Philadelphia, PA, 2008), pp. 84–93.
     
  49. O. Regev, On lattices, learning with errors, random linear codes, and cryptography, J. ACM 56 (6), 1–40 (2009). 
     
  50. A. Banerjee, C. Peikert, and A. Rosen, Pseudorandom functions and lattices, in Advances in Cryptology — EUROCRYPT 2012 (Proc. 31st Annu. Int. Conf. Theory and Applications of Cryptographic Techniques, Cambridge, UK, Apr. 15–19, 2012) (Springer, Heidelberg, 2012), pp. 719–737 (Lect. Notes Comput. Sci., Vol. 7237).
     
  51. J. Alwen, S. Krenn, K. Pietrzak, and D. Wichs, Learning with rounding, revisited, in Advances in Cryptology — CRYPTO 2013 (Proc. 33rd Annu. Cryptology Conf., Santa Barbara, USA, Aug. 18–22, 2013), Pt. I (Springer, Heidelberg, 2013), pp. 57–74 (Lect. Notes Comput. Sci., Vol. 8042).
     
  52. 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).
     
  53. 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 Sept. 13, 2023).
     
  54. Submission requirements and evaluation criteria for the post-quantum cryptography standardization process (NIST, Gaithersburg, MD, 2016). Available at csrc.nist.gov/csrc/media/projects/post-quantum-cryptography/documents/call-for-proposals-final-dec-2016.pdf (accessed Sept. 13, 2023).
     
  55. R. Avanzi, J. Bos, L. Ducas, [et al.], CRYSTALS-Kyber. Algorithm specifications and supporting documentation (NIST, Gaithersburg, MD, 2021). Available at pq-crystals.org/kyber/data/kyber-specification-round3-20210131.pdf (accessed Sept. 13, 2023).
     
  56. E. Fujisaki and T. Okamoto, Secure integration of asymmetric and symmetric encryption schemes, in Advances in Cryptology — CRYPTO’99 (Proc. 19th Annu. Int. Cryptology Conf., Santa Barbara, USA, Aug. 15–19, 1999) (Springer, Heidelberg, 1999), pp. 537–554 (Lect. Notes Comput. Sci., Vol. 1666).
     
  57. A. Basso, J. M. B. Mera, J.-P. D’Anvers, [et al.], SABER: mod-LWR based KEM (Round 3 Submission) (KU Leuven, Leuven, 2020). Available at esat.kuleuven.be/cosic/pqcrypto/saber/files/saberspecround3.pdf (accessed Sept. 13, 2023).
     
  58. C. Chen, O. Danba, J. Hoffstein, [et al.], NTRU. Algorithm specifications and supporting documentation (Eindh. Univ. Technol., Eindhoven, 2020). Available at cryptojedi.org/papers/ntrunistr3-20200930.pdf (accessed Sept. 13, 2023).
     
  59. E. E. Targhi and D. Unruh, Post-quantum security of the Fujisaki — Okamoto and OAEP transforms, in Theory of Cryptography (Proc. 14th Int. Conf., Beijing, China, Oct. 31 — Nov. 3, 2016), Pt. II (Springer, Heidelberg, 2016), pp. 192–216 (Lect. Notes Comput. Sci., Vol. 9986).
     
  60. E. Alkim, J. W. Bos, L. Ducas, [et al.],. FrodoKEM. Learning with errors key encapsulation: Algorithm specifications and supporting documentation (NIST, Gaithersburg, MD, 2021). Available at frodokem.org/files/FrodoKEM-specification-20210604.pdf (accessed Sept. 13, 2023).
     
  61. E. Fujisaki and T. Okamoto, Secure integration of asymmetric and symmetric encryption schemes, J. Cryptol. 26, 80–101 (2013).
     
  62. S. Bai, L. Ducas, E. Kiltz, [et al.], CRYSTALS-Dilithium. Algorithm specifications and supporting documentation (NIST, Gaithersburg, MD, 2021). Available at pq-crystals.org/dilithium/data/dilithium-specificationround3-20210208.pdf (accessed Sept. 13, 2023).
     
  63. P.-A. Fouque, J. Hoffstein, P. Kirchner, [et al.], Falcon: Fast-fourier lattice-based compact signatures over NTRU (NIST, Gaithersburg, MD, 2020). Available at falcon-sign.info/falcon.pdf (accessed Sept. 13, 2023).
     
  64. D. Coppersmith and A. Shamir, Lattice attacks on NTRU, in Advances in Cryptology — EUROCRYPT’97 (Proc. Int. Conf. Theory and Applications of Cryptographic Techniques, Konstanz, Germany, May 11–15, 1997) (Springer, Heidelberg, 1997), pp. 52–61 (Lect. Notes Comput. Sci., Vol. 1233).
     
  65. C. P. Schnorr and M. Euchner, Lattice basis reduction: Improved practical algorithms and solving subset sum problems, Math. Program. 66, 181–199 (1994).
     
  66. R. Kannan, Improved algorithms for integer programming and related lattice problems, in Proc. 15th Annu. ACM Symp. Theory of Computing, Boston, MA, USA, Apr. 25–27, 1983 (ACM, New York, 1983), pp. 193–206.
     
  67. 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).
     
  68. 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 Applications of Cryptographic Techniques, French Riviera, France, May 30 — June 3, 2010) (Springer, Heidelberg, 2010), pp. 257–278 (Lect. Notes Comput. Sci., Vol. 6110).
     
  69. 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).
     
  70. M. Ajtai, R. Kumar, D. Sivakumar A sieve algorithm for the shortest lattice vector problem, in Proc. 33rd Annu. ACM Symp. Theory of Computing (Hersonissos, Greece, July 6–8, 2001) (ACM, New York, 2001), pp. 601–610. 
     
  71. X. Pujol and D. Stehlé, Solving the shortest lattice vector problem in time 2 2,465n (Univ. California, San Diego, 2009) (Cryptology ePrint Archive, Paper ID 2009/605). Available at eprint.iacr.org/2009/605 (accessed Sept. 13, 2023).
     
  72. P. Q. Nguyen and T. Vidick, Sieve algorithms for the shortest vector problem are practical, J. Math. Cryptol. 2 (2), 181–207 (2008).
     
  73. 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.
     
  74. 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.
     
  75. G. Herold, E. Kirshanova, T. Laarhoven Speed-ups and time-memory 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).
     
  76. 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).
     
  77. T. Laarhoven, Search Problems in Cryptography: From Fingerprinting to Lattice Sieving (Tech. Univ. Eindhoven, Eindhoven, 2016).
     
  78. 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).
     
  79. E. Kirshanova, E. Mårtensson, E. W. Postlethwaite, and S. R. Moulik, Quantum algorithms for the approximate $k$-list problem and their application to lattice sieving, in Advances in Cryptology — ASIACRYPT 2019 (Proc. 25th Int. Conf. Theory and Application of Cryptology and Information Security, Kobe, Japan, Dec. 8–12, 2019), Pt. I (Springer, Cham, 2019), pp. 521–551 (Lect. Notes Comput. Sci., Vol. 11921).
     
  80. D. Micciancio, 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.
     
  81. 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).
     
  82. 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.
     
  83. G. Hanrot and D. Stehlé, Improved analysis of Kannan’s shortest lattice vector algorithm, in Advances in Cryptology — CRYPTO 2007 (Proc. 27th Annu. Cryptology Conf., Santa Barbara, USA, Aug. 19–23, 2007) (Springer, Heidelberg, 2007), pp. 170–186 (Lect. Notes Comput. Sci., Vol. 4622).
     
  84. G. Hanrot, X. Pujol, and D. Stehlé, Algorithms for the shortest and closest lattice vector problems, in Coding and Cryptology (Proc. 3rd Int. Workshop, Qingdao, China, May 30 — June 3, 2011) (Springer, Heidelberg, 2011), pp. 159–190 (Lect. Notes Comput. Sci., Vol. 6639).
     
  85. S. Y. Yang, P. C. Kuo, B. Y. Yang, and C. M. Cheng, Gauss sieve algorithm on GPUs, in Topics in Cryptology — CT-RSA 2017 (Cryptographers’ Track at the RSA Conf. 2017, San Francisco, USA, Feb. 14–17, 2017) (Springer, Cham, 2017), pp. 39–57 (Lect. Notes Comput. Sci., Vol. 10159).
     
  86. S. Bai, T. Laarhoven, and D. Stehlé, Tuple lattice sieving, LMS J. Comput. Math. 19 (A), 146–162 (2016).
     
  87. G. Herold and E. Kirshanova, Improved algorithms for the approximate $k$-list problem in Euclidean norm, in Public-Key Cryptography — PKC 2017 (Proc. 20th IACR Int. Conf. Practice and Theory of Public-Key Cryptography, Amsterdam, Netherlands, Mar. 28–31, 2017), Pt. I (Springer, Heidelberg, 2017), pp. 16–40 (Lect. Notes Comput. Sci., Vol. 10174).
     
  88. A. Becker, N. Gama, and A. Joux, A sieve algorithm based on overlattices, LMS J. Comput. Math. 17 (A), 49–70 (2014).
     
  89. T. Laarhoven, Sieving for shortest vectors in lattices using angular locality-sensitive hashing, in Advances in Cryptology — CRYPTO 2015 (Proc. 35th Annu. Cryptology Conf., Santa Barbara, USA, Aug. 16–20, 2015), Pt. I (Springer, Heidelberg, 2015), pp. 3–22 (Lect. Notes Comput. Sci., Vol. 9215).
     
  90. T. Laarhoven and A. Mariano, Progressive lattice sieving, in Post-Quantum Cryptography (Proc. 9th Int. Conf., Fort Lauderdale, FL, USA, Apr. 9–11, 2018) (Springer, Cham, 2018), pp. 292–311 (Lect. Notes Comput. Sci., Vol. 10786).
     
  91. A. Andoni, P. Indyk, H. L. Nguyen, and I. Razenshteyn, Beyond locality-sensitive hashing, in Proc. 25th Annu. ACM-SIAM Symp. Discrete Algorithms, Portland, Oregon, USA, Jan. 5–7, 2014 (SIAM, Philadelphia, PA, 2014), pp. 1018–1028.
     
  92. T. Laarhoven and B. de Weger, Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing, in Progress in Cryptology — LATINCRYPT 2015 (Proc. 4th Int. Conf. Cryptology and Information Security in Latin America, Guadalajara, Mexico, Aug. 23–26, 2015) (Springer, Cham, 2015), pp. 101–118 (Lect. Notes Comput. Sci., Vol. 9230).
     
  93. L. Ducas, M. Stevens, and W. van Woerden, Advanced lattice sieving on GPUs, with tensor cores, in Advances in Cryptology — EUROCRYPT 2021 (Proc. 40th Annu. Int. Conf. Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, Oct. 17–21, 2021), Pt. II (Springer, Cham, 2021), pp. 249–279 (Lect. Notes Comput. Sci., Vol. 12697).