Geodesic
Development and comparison of quantum oracle models for the hybrid attack on post-quantum lattice-based cryptosystems
Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 43-48.

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

Every year, quantum computing is developing with increasing force. Therefore, there is a need to design and analyze cryptosystems that will be resistant to attacks using a quantum computer. The security of many well-known post-quantum lattice-based cryptosystems depends on the complexity of solving the shortest vector problem (SVP). One of the most efficient algorithms to solve this problem is the GaussSieve algorithm. For the previously proposed model of the quantum oracle used in the hybrid quantum-classical algorithm for solving SVP, new updated bounds of the number of qubits and the depth of the scheme are obtained. This improvement is achieved by optimizing all quantum operations with integers used in the model. A new quantum oracle model is proposed and analyzed, which uses classical memory to store a list of vectors. This model requests the number of qubits that is logarithmic to the length of the list in the GaussSieve algorithm. Upper bounds on the complexity of the attack of post-quantum cryptosystems that have become finalists of the NIST competition have been obtained. These upper bounds indicate that the exponential length of the list from the GaussSieve algorithm imposes limitations on the possibility of implementing hybrid attacks on the known standards of post-quantum cryptosystems.
Keywords: quantum search, public-key cryptography, post-quantum cryptography. 
@article{PDMA_2022_15_a10,
     author = {A. O. Bakharev},
     title = {Development and comparison of quantum oracle models for the hybrid attack on post-quantum lattice-based cryptosystems},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {43--48},
     publisher = {mathdoc},
     number = {15},
     year = {2022},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2022_15_a10/}
}
TY  - JOUR
AU  - A. O. Bakharev
TI  - Development and comparison of quantum oracle models for the hybrid attack on post-quantum lattice-based cryptosystems
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2022
SP  - 43
EP  - 48
IS  - 15
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2022_15_a10/
LA  - ru
ID  - PDMA_2022_15_a10
ER  - 
%0 Journal Article
%A A. O. Bakharev
%T Development and comparison of quantum oracle models for the hybrid attack on post-quantum lattice-based cryptosystems
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2022
%P 43-48
%N 15
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2022_15_a10/
%G ru
%F PDMA_2022_15_a10
A. O. Bakharev. Development and comparison of quantum oracle models for the hybrid attack on post-quantum lattice-based cryptosystems. Prikladnaya Diskretnaya Matematika. Supplement, no. 15 (2022), pp. 43-48. http://geodesic.mathdoc.fr/item/PDMA_2022_15_a10/

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

[2] Micciancio D. and Voulgaris P., “Faster exponential time algorithms for the shortest vector problem”, Proc. 21 Ann. ACM-SIAM Symp. Discrete Algorithms, Society for Industrial and Applied Mathematics, USA, 2010, 1468–1480 | DOI | MR | Zbl

[3] Grover L. K., “A fast quantum mechanical algorithm for database search”, Proc. 28 Ann. ACM Symp. Theory of Computing, ACM, N.Y., 1996, 212–219 | MR | Zbl

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

[5] Bakharev A. O., “Razrabotka i analiz orakula dlya gibridnoi ataki na kriptograficheskuyu sistemu NTRU s ispolzovaniem algoritma kvantovogo poiska”, Prikladnaya diskretnaya matematika. Prilozhenie, 2021, no. 14, 62–67

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

[7] D'Anvers J.- P., Karmakar A., Roy S. S., and Vercauteren F., SABER: Mod-LWR based KEM, https://www.esat.kuleuven.be/cosic/pqcrypto/saber/files/saberspecround1.pdf

[8] Avanzi R., Bos J., Ducas L., et al., CRYSTALS-Kyber Algorithm Specifications and Supporting Documentation, https://cryptojedi.org/papers/kybernist-20171130.pdf