Geodesic
Research of $k$-sieve algorithm for solving the shortest vector problem in a lattice
Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 157-162.

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

Quantum computing has been actively developing in recent decades: the number of qubits operated by a quantum compute is increasing and the probability of computational errors is decreasing. Therefore, there is a need to design and analyze post-quantum cryptosystems — cryptosystems resistant to attacks using a quantum computer. One of the main approaches to designing such cryptosystems is lattice theory. In this approach, the security of most cryptosystems is reduced to solving the problem of finding the shortest vector in the lattice (SVP). The results of the analysis of the $8$-sieve algorithm for solving SVP are presented. We propose a new trade-off between runtime and amount of memory used by the $8$-sieve algorithm. A comparison with known $k$-sieve algorithms is given. The proposed algorithm has the minimum running time on the segment $(2^{0.155n}, 2^{0.189n})$ of memory used among the known $k$-sieve algorithms.
Keywords: lattice-based cryptography, $k$-sieve, SVP, post-quantum cryptography. 
@article{PDMA_2024_17_a40,
     author = {A. O. Bakharev},
     title = {Research of $k$-sieve algorithm for solving the shortest vector problem in a lattice},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {157--162},
     publisher = {mathdoc},
     number = {17},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2024_17_a40/}
}
TY  - JOUR
AU  - A. O. Bakharev
TI  - Research of $k$-sieve algorithm for solving the shortest vector problem in a lattice
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2024
SP  - 157
EP  - 162
IS  - 17
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2024_17_a40/
LA  - ru
ID  - PDMA_2024_17_a40
ER  - 
%0 Journal Article
%A A. O. Bakharev
%T Research of $k$-sieve algorithm for solving the shortest vector problem in a lattice
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2024
%P 157-162
%N 17
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2024_17_a40/
%G ru
%F PDMA_2024_17_a40
A. O. Bakharev. Research of $k$-sieve algorithm for solving the shortest vector problem in a lattice. Prikladnaya Diskretnaya Matematika. Supplement, no. 17 (2024), pp. 157-162. http://geodesic.mathdoc.fr/item/PDMA_2024_17_a40/

[1] Kannan R., “Improved algorithms for integer programming and related lattice problems”, Proc. 15th Ann. ACM Symp. Theory Comput. (Boston, Massachusetts, USA, April 25–27, 1983), ACM, N.Y., 1983, 193–206

[2] Fincke U. and 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

[3] Ajtai M., Kumar R., and Sivakumar D., “A sieve algorithm for the shortest lattice vector problem”, Proc. 33rd Ann. ACM Symp. Theory Comput. (Hersonissos, Greece, July 6–8, 2001), ACM, N.Y., 2001, 601–610 | MR | Zbl

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

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

[6] Herold G. and Kirshanova E., “Improved algorithms for the approximate $k$-list problem in Euclidean norm”, LNCS, 10174, 2017, 16–40 | MR | Zbl

[7] Becker A., Ducas L., Gama G., and Laarhoven T., “New directions in nearest neighbor searching with applications to lattice sieving”, Proc. 27th Ann. ACM-SIAM Symp. Discrete Algorithms (Arlington, VA, USA, Jan. 10–12, 2016), SIAM, Philadelphia, PA, 2016, 10–24 | DOI | MR | Zbl

[8] Chailloux A. and Loyer J., “Classical and quantum 3 and 4-sieves to solve SVP with low memory”, LNCS, 14154, 2023, 225–255 | MR | Zbl

[9] Laarhoven T., Search Problems in Cryptography, From Fingerprinting to Lattice Sieving, Ph.D. Thesis, Eindhoven University of Technology, 2016

[10] Herold G., Kirshanova E., Laarhoven T., “Speed-ups and time–memory trade-offs for tuple lattice sieving”, LNCS, 10769, 2018, 407–436 | MR | Zbl

[11] Ajtai M., “The shortest vector problem in $L_2$ is NP-hard for randomized reductions (extended abstract)”, Proc. 30th Ann. ACM Symp. Theory Comput. (Dallas, Texas, USA, May 24–26, 1998), ACM, N.Y., 1998, 10–19 | Zbl

[12] Klein P., “Finding the closest lattice vector when it's unusually close”, Proc. 11th Ann. ACM-SIAM Symp. Discrete Algorithms (San Francisco, California, USA, Jan. 9–11, 2000), SIAM, Philadelphia, PA, 2000, 937–941 | MR | Zbl

[13] https://latticechallenge.org/svp-challenge