Post-quantum cryptosystems: open problems and solutions. Lattice-based cryptosystems

E. S. Malygina ; A. V. Kutsenko ; S. A. Novoselov ; N. S. Kolesnikov ; A. O. Bakharev ; I. S. Khilchuk ; A. S. Shaporenko ; N. N. Tokareva

Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 4, pp. 46-90.

Résumé

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.

Détail

Keywords: post-quantum cryptography, quantum computer, integer lattice.

Bibliographie

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

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

[3] Bennett C. H., Brassard G., “Quantum cryptography: Public key distribution and coin tossing”, Theor. Comput. Sci., 560 (2014), 7–11 | DOI | MR | Zbl

[4] Yu. I. Manin, Computable and Incomputable, Sov. Radio, M., 1980 (Russian)

[5] Feynman R. P., “Simulating physics with computers”, Int. J. Theor. Phys., 21 (1982), 467–468 | DOI | MR

[6] Deutsch D., “Quantum theory, the Church — Turing principle and the universal quantum computer”, Proc. R. Soc. Lond. Ser. A. Math. Phys. Sci., 400:1818 (1985), 97–117 | MR | Zbl

[7] Deutsch D., Jozsa R., “Rapid solution of problems by quantum computation”, Proc. R. Soc. Lond. Ser. A. Math. Phys. Sci., 439:1907 (1992), 553–558 | MR | Zbl

[8] Bernstein E., Vazirani U., “Quantum complexity theory”, SIAM J. Comput., 26:5 (1997), 1411–1473 | DOI | MR | Zbl

[9] Simon D. R., “On the power of quantum computation”, SIAM J. Comput., 26:5 (1997), 1474–1483 | DOI | MR | Zbl

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

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

[12] Proos J., Zalka C., “Shor's discrete logarithm quantum algorithm for elliptic curves”, Quantum Inf. Comput., 3:4 (2003), 317–344 | MR | Zbl

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

[14] Brassard G., Høyer P., Tapp A., “Quantum cryptanalysis of hash and claw-free functions”, LATIN'98: Theoretical informatics, Proc. 3rd Lat. Am. Symp. (Campinas, Brazil, Apr. 20–24, 1998), Lect. Notes Comput. Sci., 1380, Springer, Heidelberg, 1998, 163–169 | DOI | MR | Zbl

[15] Brassard G., Høyer P., Tapp A., “Quantum counting”, Automata, languages and programming, Proc. 25th Int. Colloq. (Aalborg, Denmark, July 13–17, 1998), Lect. Notes Comput. Sci., 1443, Springer, Heidelberg, 1998, 820–831 | DOI | MR

[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), IEEE Comput. Soc., Los Alamitos, CA, 2012, 312–316

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

[18] Xie H., Yang L., “Using Bernstein — Vazirani algorithm to attack block ciphers”, Des. Codes Cryptogr., 87:5 (2019), 1161–1182 | DOI | MR | Zbl

[19] Leander G., May A., “Grover meets Simon — quantumly attacking the FX-construction”, Advances in cryptology — ASIACRYPT 2017, Proc. 23rd Int. Conf. Theory and Applications of Cryptology and Information Security (Hong Kong, China, Dec. 3–7, 2017), v. II, Lect. Notes Comput. Sci., 10625, Springer, Cham, 2017, 161–178 | DOI | MR | Zbl

[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), IEEE Comput. Soc., Los Alamitos, CA, 2010, 2682–2685 | DOI

[21] Hodžić S., Knudsen L. R., “A quantum distinguisher for 7/8-round SMS4 block cipher”, Quantum Inf. Process., 19:11 (2020), 411, 22 pp. | DOI | MR | Zbl

[22] Zhou Q., Lu S., Zhang Z., Sun J., “Quantum differential cryptanalysis”, Quantum Inf. Process., 14:6 (2015), 2101–2109 | DOI | Zbl

[23] Shi R., Xie H., Feng H., Yuan F., Liu B., “Quantum zero correlation linear cryptanalysis”, Quantum Inf. Process, 21:8 (2022), 293, 30 pp. | DOI | MR | Zbl

[24] Kaplan M., Leurent G., Leverrier A., Naya-Plasencia M., “Quantum differential and linear cryptanalysis”, IACR Trans. Symmetric Cryptol., 2016:1 (2016), 71–94 | DOI

[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, NIST, Gaithersburg, MD, 2016, 15 pp. (accessed Sept. 13, 2023) | DOI

[26] Post-quantum cryptography, NIST, Gaithersburg, MD, 2017 (accessed Sept. 13, 2023) csrc.nist.gov/projects/post-quantum-cryptography

[27] Lenstra A. K., Lenstra H. W., Lovász L., “Factoring polynomials with rational coefficients”, Math. Ann., 261:4 (1982), 515–534 | DOI | MR | Zbl

[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), Plenum Press, New York, 1983, 279–288 | DOI | MR

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

[30] Schnor C. P., “A more efficient algorithm for lattice basis reduction”, J. Algorithms, 9:1 (1988), 47–62 | DOI | MR | Zbl

[31] Frieze A., Håstad J., Kannan R., Lagarias J., Shamir A., “Reconstructing truncated integer variables satisfying linear congruences”, SIAM J. Comput., 17:2 (1988), 262–280 | DOI | MR | Zbl

[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), Lect. Notes Comput. Sci., 473, Springer, Heidelberg, 1991, 313–317 | DOI | MR

[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), Lect. Notes Comput. Sci., 739, Springer, Heidelberg, 1993, 470–476 | DOI | Zbl

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

[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), ACM, New York, 1997, 284–293 | MR

[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), Lect. Notes Comput. Sci., 1294, Springer, Heidelberg, 1997, 112–131 | DOI | MR | Zbl

[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), Lect. Notes Comput. Sci., 1462, Springer, Heidelberg, 1998, 223–242 | DOI | MR | Zbl

[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), Lect. Notes Comput. Sci., 1666, Springer, Heidelberg, 1999, 288–304 | DOI | MR | Zbl

[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), Lect. Notes Comput. Sci., 1423, Springer, Heidelberg, 1998, 267–288 | DOI | MR | Zbl

[40] Silverman J. H., Pipher J., Hoffstein J., An introduction to mathematical cryptography, Springer, New York, 2008 | MR | Zbl

[41] Silverman J. H., “An introduction to lattices, lattice reduction, and lattice-based cryptography”, Lect. Notes 30th Annu. PCMI Graduate Summer School (Princeton, USA, July 5–25, 2020), Inst. Adv. Study, Princeton, 2020, 70 pp. (accessed Sept. 13, 2023) ias.edu/sites/default/files/Silverman_PCMI_Note_DistributionVersion_220705.pdf | MR

[42] Peikert C., “A decade of lattice cryptography”, Found. Trends Theor. Comput. Sci., 10:4 (2016), 283–424 | DOI | MR

[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), ACM, New York, 1998, 10–19 | Zbl

[44] Micciancio D., “The shortest vector in a lattice is hard to approximate to within some constant”, SIAM J. Comput., 30:6 (2001), 2008–2035 | DOI | MR | Zbl

[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), ACM, New York, 2007, 469–477 | MR | Zbl

[46] Aharonov D., Regev O., “Lattice problems in $\text{NP}\cap\text{coNP}$”, J. ACM, 52:5 (2005), 749–765 | DOI | MR | Zbl

[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., 71:2 (1999), 55–61 | DOI | MR | Zbl

[48] Micciancio D., “Efficient reductions among lattice problems”, Proc. 19th Annu. ACM-SIAM Symp. Discrete Algorithms (San Francisco, USA, Jan. 20–22, 2008), SIAM, Philadelphia, PA, 2008, 84–93 | MR | Zbl

[49] Regev O., “On lattices, learning with errors, random linear codes, and cryptography”, J. ACM, 56:6 (2009), 1–40 | DOI | MR

[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), Lect. Notes Comput. Sci., 7237, Springer, Heidelberg, 2012, 719–737 | DOI | MR | Zbl

[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), v. I, Lect. Notes Comput. Sci., 8042, Springer, Heidelberg, 2013, 57–74 | DOI | Zbl

[52] 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

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

[54] Submission requirements and evaluation criteria for the post-quantum cryptography standardization process, NIST, Gaithersburg, MD, 2016 (accessed Sept. 13, 2023) csrc.nist.gov/csrc/media/projects/post-quantum-cryptography/documents/call-for-proposals-final-dec-2016.pdf

[55] Avanzi R., Bos J., Ducas L. et al., CRYSTALS-Kyber. Algorithm specifications and supporting documentation, NIST, Gaithersburg, MD, 2021 (accessed Sept. 13, 2023) pq-crystals.org/kyber/data/kyber-specification-round3-20210131.pdf

[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), Lect. Notes Comput. Sci., 1666, Springer, Heidelberg, 1999, 537–554 | DOI | Zbl

[57] Basso A., Mera J. M. B., D'Anvers J.-P. et al., SABER: mod-LWR based KEM (Round 3 Submission), KU Leuven, Leuven, 2020 (accessed Sept. 13, 2023) esat.kuleuven.be/cosic/pqcrypto/saber/files/saberspecround3.pdf

[58] Chen C., Danba O., Hoffstein J. et al., NTRU. Algorithm specifications and supporting documentation, Eindh. Univ. Technol., Eindhoven, 2020 (accessed Sept. 13, 2023) cryptojedi.org/papers/ntrunistr3-20200930.pdf

[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), v. II, Lect. Notes Comput. Sci., 9986, Springer, Heidelberg, 2016, 192–216 | DOI | MR | Zbl

[60] Alkim E., Bos J. W., Ducas L. et al., FrodoKEM. Learning with errors key encapsulation: Algorithm specifications and supporting documentation, NIST, Gaithersburg, MD, 2021 (accessed Sept. 13, 2023) frodokem.org/files/FrodoKEM-specification-20210604.pdf

[61] Fujisaki E., Okamoto T., “Secure integration of asymmetric and symmetric encryption schemes”, J. Cryptol., 26 (2013), 80–101 | DOI | MR | Zbl

[62] Bai S., Ducas L., Kiltz E. et al., CRYSTALS-Dilithium. Algorithm specifications and supporting documentation, NIST, Gaithersburg, MD (accessed Sept. 13, 2023) pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf

[63] Fouque P.-A., Hoffstein J., Kirchner P. et al., Falcon: Fast-fourier lattice-based compact signatures over NTRU, NIST, Gaithersburg, MD, 2020 (accessed Sept. 13, 2023) falcon-sign.info/falcon.pdf

[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), Lect. Notes Comput. Sci., 1233, Springer, Heidelberg, 1997, 52–61 | DOI | MR

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

[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), ACM, New York, 1983, 193–206

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

[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), Lect. Notes Comput. Sci., 6110, Springer, Heidelberg, 2010, 257–278 | DOI | MR | Zbl

[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), Lect. Notes Comput. Sci., 7073, Springer, Heidelberg, 2011, 1–20 | DOI | MR | Zbl

[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), ACM, New York, 2001, 601–610 | MR | Zbl

[71] Pujol X., Stehlé D., Solving the shortest lattice vector problem in time $2^{2{,}465n}$, Univ. California, San Diego, 2009; Cryptology Archive, (accessed Sept. 13, 2023) 2009/605

[72] 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

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

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

[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), v. I, Lect. Notes Comput. Sci., 10769, Springer, Cham, 2018, 407–436 | DOI | MR | Zbl

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

[77] Laarhoven T., Search problems in cryptography: From fingerprinting to lattice sieving, Tech. Univ. Eindhoven, Eindhoven, 2016, 230 pp.

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

[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), v. I, Lect. Notes Comput. Sci., 11921, Springer, Cham, 2019, 521–551 | DOI | MR | Zbl

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

[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), Lect. Notes Comput. Sci., 11505, Springer, Cham, 2019, 3–22 | DOI | MR | Zbl

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

[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), Lect. Notes Comput. Sci., 4622, Springer, Heidelberg, 2007, 170–186 | DOI | MR | Zbl

[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), Lect. Notes Comput. Sci., 6639, Springer, Heidelberg, 2011, 159–190 | DOI | MR | Zbl

[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), Lect. Notes Comput. Sci., 10159, Springer, Cham, 2017, 39–57 | DOI | MR | Zbl

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

[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), v. I, Lect. Notes Comput. Sci., 10174, Springer, Heidelberg, 2017, 16–40 | DOI | MR | Zbl

[88] Becker A., Gama N., Joux A., “A sieve algorithm based on overlattices”, LMS J. Comput. Math., 17:A (2014), 49–70 | DOI | MR

[89] Laarhoven T., “Sieving for shortest vectors in lattices using angular locality-sensitive hashing”, Advances in cryptology — CRYPTO 2015, Proc. 35th Annu. Cryptology Conf. (Santa Barbara, USA, Aug. 16–20, 2015), v. I, Lect. Notes Comput. Sci., 9215, Springer, Heidelberg, 2015, 3–22 | DOI | MR | Zbl

[90] Laarhoven T., Mariano A., “Progressive lattice sieving”, Post-quantum cryptography, Proc. 9th Int. Conf. (Fort Lauderdale, FL, USA, Apr. 9–11, 2018), Lect. Notes Comput. Sci., 10786, Springer, Cham, 2018, 292–311 | DOI | MR | Zbl

[91] Andoni A., Indyk P., Nguyen H. L., Razenshteyn I., “Beyond locality-sensitive hashing”, Proc. 25th Annu. ACM-SIAM Symp. Discrete Algorithms (Portland, Oregon, USA, Jan. 5–7, 2014), SIAM, Philadelphia, PA, 2014, 1018–1028 | DOI | MR | Zbl

[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), Lect. Notes Comput. Sci., 9230, Springer, Cham, 2015, 101–118 | DOI | MR | Zbl

[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), v. II, Lect. Notes Comput. Sci., 12697, Springer, Cham, 2021, 249–279 | DOI | MR | Zbl