Geodesic
Development and analysis of oracle for the hibrid attack on a cryptographic system NTRU using a quantum search algorithm
Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 62-67.

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 the paper, a model of the quantum oracle which is required for the implementation of the hybrid quantum-classical algorithm for solving SVP is proposed and analyzed. For the public key post-quantum cryptosystem NTRU which is the finalist of the third round of the NIST competition, upper bounds for the number of qubits and the depth of the scheme are obtained. The bounds are based on the proposed model of the quantum oracle.
Keywords: cryptosystem NTRU, quantum search, public-key cryptography, post-quantum cryptography. 
@article{PDMA_2021_14_a13,
     author = {A. O. Bakharev},
     title = {Development and analysis of oracle for the hibrid attack on a cryptographic system {NTRU} using a quantum search algorithm},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {62--67},
     publisher = {mathdoc},
     number = {14},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2021_14_a13/}
}
TY  - JOUR
AU  - A. O. Bakharev
TI  - Development and analysis of oracle for the hibrid attack on a cryptographic system NTRU using a quantum search algorithm
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2021
SP  - 62
EP  - 67
IS  - 14
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2021_14_a13/
LA  - ru
ID  - PDMA_2021_14_a13
ER  - 
%0 Journal Article
%A A. O. Bakharev
%T Development and analysis of oracle for the hibrid attack on a cryptographic system NTRU using a quantum search algorithm
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2021
%P 62-67
%N 14
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2021_14_a13/
%G ru
%F PDMA_2021_14_a13
A. O. Bakharev. Development and analysis of oracle for the hibrid attack on a cryptographic system NTRU using a quantum search algorithm. Prikladnaya Diskretnaya Matematika. Supplement, no. 14 (2021), pp. 62-67. http://geodesic.mathdoc.fr/item/PDMA_2021_14_a13/

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

[2] Micciancio D., Voulgaris P., “Faster exponential time algorithms for the Shortest Vector roblem”, 21st Ann. ACM Symp. Discrete Algorithms (SODA), 2010, 1468–1480 | MR | Zbl

[3] Grover L. K., “A fast quantum mechanical algorithm for database search”, 28th Ann. ACM Symp. Theory Comput. (STOC), 1996, 212–219 | MR | Zbl

[4] Nielsen M. A., Chuang I. L., Quantum Computation and Quantum Information, Cambridge University Press, Cambridge, 2010 | MR | Zbl

[5] https://csrc.nist.gov/Projects/post-quantum-cryptography/round-3-submissions

[6] Chen C., Danba O., Hoffstein J., et al., NTRU Algorithm Specifications and Supporting Documentation, , 2019 https://ntru.org/

[7] Zhong H.-S., Wang H., Deng Y.-H., et al., “Quantum computational advantage using photons”, Science, 370:6523 (2020), 1460–1463