Geodesic
Estimates of implementation complexity for quantum cryptanalysis of post-quantum lattice-based cryptosystems
Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 3, pp. 5-42

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

Due to the development of quantum computing, there is a need for the development and analysis of cryptosystems resistant to attacks using a quantum computer (post-quantum cryptography algorithms). The security of many well-known post-quantum cryptosystems based on lattice theory depends on the complexity of solving the shortest vector problem (SVP). In this paper, a model of quantum oracle developed from Grover's algorithm is described to implement a hybrid quantum-classical algorithm based on GaussSieve. This algorithm can be used for attacks on cryptosystems, the security of which depends on solving the SVP problem. Upper bounds for the number of qubits and the depth of the circuit were obtained for two implementations of the proposed quantum oracle model: minimizing the number of qubits and minimizing the circuit depth. The complexity of implementing the proposed quantum oracle model to attack post-quantum lattice-based cryptosystems that are finalists of the NIST post-quantum cryptography competition is analyzed. Tab. 6, illustr. 12, bibliogr. 34.
Keywords: quantum search, public-key cryptography, lattice-based cryptography, post-quantum cryptography, Grover's algorithm, quantum computation. 
@article{DA_2023_30_3_a0,
     author = {A. O. Bakharev},
     title = {Estimates of implementation complexity for quantum cryptanalysis of post-quantum lattice-based cryptosystems},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--42},
     publisher = {mathdoc},
     volume = {30},
     number = {3},
     year = {2023},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2023_30_3_a0/}
}
TY  - JOUR
AU  - A. O. Bakharev
TI  - Estimates of implementation complexity for quantum cryptanalysis of post-quantum lattice-based cryptosystems
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2023
SP  - 5
EP  - 42
VL  - 30
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2023_30_3_a0/
LA  - ru
ID  - DA_2023_30_3_a0
ER  - 
%0 Journal Article
%A A. O. Bakharev
%T Estimates of implementation complexity for quantum cryptanalysis of post-quantum lattice-based cryptosystems
%J Diskretnyj analiz i issledovanie operacij
%D 2023
%P 5-42
%V 30
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2023_30_3_a0/
%G ru
%F DA_2023_30_3_a0
A. O. Bakharev. Estimates of implementation complexity for quantum cryptanalysis of post-quantum lattice-based cryptosystems. Diskretnyj analiz i issledovanie operacij, Tome 30 (2023) no. 3, pp. 5-42. http://geodesic.mathdoc.fr/item/DA_2023_30_3_a0/