Solving the shortest vector problem in lattices faster using quantum search

DOI10.1007/978-3-642-38616-9_6MaRDI QIDQ4928590zbMATH OpenOpenAlexFDO

Authors Thijs Laarhoven, Michele Mosca, Joop van de Pol

Publication date 14 June 2013

Published in Post-Quantum Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.6176

zbMATH Keywords

latticesquantum algorithmsquantum searchshortest vector problemsieving

Mathematics Subject Classification ID

Quantum computation (81P68) Quantum cryptography (quantum-theoretic aspects) (81P94) Cryptography (94A60)

Abstract: By applying Grover's quantum search algorithm to the lattice algorithms of Micciancio and Voulgaris, Nguyen and Vidick, Wang et al., and Pujol and Stehl'{e}, we obtain improved asymptotic quantum results for solving the shortest vector problem. With quantum computers we can provably find a shortest vector in time $2^{1.799n+o(n)}$, improving upon the classical time complexity of $2^{2.465n+o(n)}$ of Pujol and Stehl'{e} and the $2^{2n+o(n)}$ of Micciancio and Voulgaris, while heuristically we expect to find a shortest vector in time $2^{0.312n+o(n)}$, improving upon the classical time complexity of $2^{0.384n+o(n)}$ of Wang et al. These quantum complexities will be an important guide for the selection of parameters for post-quantum cryptosystems based on the hardness of the shortest vector problem.

Recommendations

• Finding shortest lattice vectors faster using quantum search
• Quantum algorithms for the approximate \(k\)-list problem and their application to lattice sieving
• Lattice Sieving via Quantum Random Walks
• Algorithms and Computation
• On the shortness of vectors to be found by the ideal-SVP quantum algorithm

Cited in

(16)

• Quantum algorithm design: techniques and applications
• Optimization of search space for finding very short lattice vectors
• Quantum algorithms for the approximate \(k\)-list problem and their application to lattice sieving
• The lattice-based digital signature scheme qTESLA
• Quantum LLL with an application to Mersenne number cryptosystems
• Estimating quantum speedups for lattice sieves
• Quantum Computation and Lattice Problems
• Using quantum key distribution for cryptographic purposes: a survey
• Homomorphic Encryption Standard
• Mildly Short Vectors in Cyclotomic Ideal Lattices in Quantum Polynomial Time
• Algorithms and Computation
• Lattice Sieving via Quantum Random Walks
• Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method
• Quantum lattice enumeration in limited depth
• Finding shortest lattice vectors faster using quantum search
• Quantum cryptography beyond quantum key distribution

Describes a project that uses

Uses Software

• BKZ

This page was built for publication: Solving the shortest vector problem in lattices faster using quantum search

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4928590)