Academician O.B. Lupanov International Scientific Seminar "Discrete Mathematics and Its Applications"
Upper bounds of complexity of quantum oracle for problem of finding shortest vector on integer lattice
Alexander Olegovich Bakharev
Abstract
Due to the development of quantum computing, there is a need for development and analysis of cryptosystems resistant to attacks with using a quantum computer - post-quantum algorithms cryptography. The strength of many well-known post-quantum cryptosystems, based on the theory of lattices, is based on the complexity of solving the problem finding the shortest vector in the lattice (SVP). For the previously proposed models of the quantum oracle used in the hybrid quantum-classical algorithm for solving the SVP problem, new refined estimates of implementation complexity. Designed and analyzed a new quantum oracle model that uses classical memory to storing a list of vectors.