A Faster Lattice Reduction Method Using Quantum Search

Thijs Laarhoven, Michele Mosca, Joop van de Pol

Florian Göpfert, Christine van Vredendaal, Thomas Wunderer

JunYao, GuihuaZeng, FuchenZhu

Lattice-based cryptosystems rely on certain lattice problems for their socurity, such as the shortest vector and the closest vector probtems. NTRU is a kind of lattice based public key cryptosysytem gaining much attention because of its high efficiency. Its encryption and decryption use a mixing system suggested by polynomial algebra combined with a clustering principle based on elementary probability theory. With the availability of quantum computers, the security of cryptosystems based on classical mathematic problems needs to be reevaluated. Since lattice reduction is the main threat to lattice-based cryptosystems, lattice reduction using quantum search algorithms are analyzed to evaluate the security of NTRU in this paper. According to our results, original security paratneters proposed for NTRU should be increased in the event that Grover's quantum search algorithm is used for lattice reduction.

Atsushi Miyauchi

Presented here is a matrix inversion method utilizing quantum searching algorithm. In this method, huge Hilbert space as a whole spanned by myriad of eigen states is searched and evaluated efficiently by sequential reduction in dimension one by one. Total iteration steps required for search are proportional to the number of unknown variables. Our method could solve very large linear equations with sufficiently high probability faster than any existing classical algorithms, which roughly depends on the cube of unknown variables.

Hossein Mehri‐Dehnavi, Hasan Dashtianeh, Hossein Yahyavi Kuchaksaraei +3 more

Demosthenes Ellinas, Christos Konstandakis

Joining independent quantum searches provides novel collective modes of quantum search (merging) by utilizing the algorithm’s underlying algebraic structure. If n quantum searches, each targeting a single item, join the domains of their classical oracle functions and sum their Hilbert spaces (merging), instead of acting independently (concatenation), then they achieve a reduction of the search complexity by factor O(√n).