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/