Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Quantum Nested Search for Lattice Enumeration

Runxi Cao, Baocang Wang, Juntao Gao

Published Jan 24, 2024• 0 citations
Publisher

Abstract

Abstract Lattice-based cryptographic regimes are the most promising quantum-resistant cryptographic algorithms, whose security depends on the difficulty of the SVP. Enumeration algorithms are the most basic and hopeful algorithms instantiated for solving SVPs, and are often used in public key cryptanalysis or as subroutines of lattice reduction algorithms. In this paper, we show how to speed up enumeration with the idea of nested search: if N is the number of nodes in the enumeration tree and T is the time required to process a node, our quantum enumeration can find the shortest vector on the lattice in time \(\sqrt{T\cdot N}\) . This is applied to the two most efficient types of enumeration: cylinder pruning as well as discrete pruning. The core idea of the algorithm is to reduce the size of the search space by transforming the original problem into a constraint-satisfiable problem, using the pruning conditions of the above two enumerations as constraints, and embedding the search for all possible solutions at the next level of the enumeration tree into the space of partially satisfied solutions at the previous level. Next, we accelerate this process using a quantum search algorithm. Compared to the work of bib24, we further reduce the time complexity of the algorithm with multiplication factor $\sqrt{T} $ by the quantum nested search algorithm.

DOI
10.21203/rs.3.rs-3887968/v1

Related papers

Nested quantum search and structured problems

Nicolas J. Cerf, Lov K. Grover, Colin P. Williams

A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order $\sqrt{d},$ where d is the dimension of the search space, whereas any classical algorithm necessarily scales as $O(d).$ It is shown here that an improved quantum search algorithm can be devised that exploits the structure of a tree search problem by nesting one quantum search within another. The average number of iterations required to find the solution of a typical hard instance of a constraint satisfaction problem is found to scale as $\sqrt{{d}^{\ensuremath{\alpha}}},$ with the constant $\ensuremath{\alpha}<1$ depending on the nesting depth and the type of problem considered. This corresponds to a square-root speedup over a classical nested search algorithm, of which our algorithm is the quantum counterpart. When applying a single nesting level to a problem with constraints of size 2 such as the graph coloring problem, $\ensuremath{\alpha}$ is estimated to be around 0.62.

arXiv:quant-ph/9806078•Physical Review A•Feb 9, 2000•104 citations

A Number Theoretic Investigation Of The Hardness Assumptions Underlying The Shortest Vector Problem In Lattice Cryptography

Jitendra Sharma

The lattice-based encryption paradigm (LBE) represents a new security model emphasizing flexible development, high levels of security, and efficient computations. It is now becoming more commonly seen as an alternative to other systems of post-quantum cryptography due to its foundations for both security (i.e., there is a high degree of confidence that lattice-based cryptography is secure) and efficiency with respect to computation. The theoretical basis for this report is related to the difficulty of solving the short vector problem (SVP) and other cryptographic hard problems concerning lattices. The report focuses on the hardness of lattice-based cryptography relative to three sub-components of the theoretical work: the relationship between geometric number theory and lattice-based systems, the application of AI to help determine parameters and the efficiencies of finding new lattice reduction algorithms, and finally estimating the difficulty to solve lattice problems. This report reviews the inherent difficulty of short vector problems (SVPs) and other kinds of SVPs, such as the closest vector problem. The report analyzes how to reduce both the time and space complexities for classical and quantum computing solutions through the discovery of new techniques based upon number-theoretic concepts. The report also discusses a number of examples, including digital signature products, encryption systems and homomorphic encryption systems as primitive constructions of cryptography based on lattices or through the properties of the lattice structures. Finally, based on number-theoretical relationships among complex numbers, the report provides a new theoretical approach to the construction of lattice-based systems and their strength relative to other types of cryptographic systems via the provision of theoretical bounds related to the lengths of lattice basis vectors.As a result of this research into bridging the divide between theoretical and practical cryptography, the results show that lattice-based systems have the capability of providing the strength to withstand quantum attacks. Through this research study, there is an improvement in how we understand mathematically the difficulty of lattices and how to create post-quantum secure cryptographic techniques through the use of lattices...

International Journal on Science and Technology•Mar 31, 2026•0 citations

Space-efficient classical and quantum algorithms for the shortest vector problem

Yanlin Chen, Kai-Min Chung, Ching–Yi Lai

A lattice is the integer span of some linearly independent vectors. Lattice problems have many significant applications in coding theory and cryptographic systems for their conjectured hardness. The Shortest Vector Problem (SVP), which asks to find a shortest nonzero vector in a lattice, is one of the well-known problems that are believed to be hard to solve, even with a quantum computer. In this paper we propose space-efficient classical and quantum algorithms for solving SVP. Currently the best time-efficient algorithm for solving SVP takes 2^{n+o(n)} time and 2^{n+o(n)} space. Our classical algorithm takes 2^{2.05n+o(n)} time to solve SVP and it requires only 2^{0.5n+o(n)} space. We then adapt our classical algorithm to a quantum version, which can solve SVP in time 2^{1.2553n+o(n)} with 2^{0.5n+o(n)} classical space and only poly(n) qubits.

arXiv:1709.00378•Quantum Information and Computation•Mar 1, 2018•3 citations

Variational quantum solutions to the Shortest Vector Problem

Martin R. Albrecht, Miloš Prokop, Yixin Shen +1 more

A fundamental computational problem is to find a shortest non-zero vector in Euclidean lattices, a problem known as the Shortest Vector Problem (SVP). This problem is believed to be hard even on quantum computers and thus plays a pivotal role in post-quantum cryptography. In this work we explore how (efficiently) Noisy Intermediate Scale Quantum (NISQ) devices may be used to solve SVP. Specifically, we map the problem to that of finding the ground state of a suitable Hamiltonian. In particular, (i) we establish new bounds for lattice enumeration, this allows us to obtain new bounds (resp. estimates) for the number of qubits required per dimension for any lattices (resp. random q-ary lattices) to solve SVP; (ii) we exclude the zero vector from the optimization space by proposing (a) a different classical optimisation loop or alternatively (b) a new mapping to the Hamiltonian. These improvements allow us to solve SVP in dimension up to 28 in a quantum emulation, significantly more than what was previously achieved, even for special cases. Finally, we extrapolate the size of NISQ devices that is required to be able to solve instances of lattices that are hard even for the best classical algorithms and find that with approximately 103 noisy qubits such instances can be tackled.

arXiv:2202.06757•Quantum•Mar 2, 2023•16 citations

From Number Theory to Lattices: The Post-Quantum Cryptographic Paradigm

Zen Revista, Zen Revista

The landscape of modern cryptography, traditionally anchored in the computational hardness of number-theoretic problems such as integer factorization and the discrete logarithm problem, faces an existential threat from the advent of quantum computing. Shor's algorithm, discovered in 1994, demonstrates the theoretical capability of a sufficiently powerful quantum computer to efficiently solve these problems, rendering widely used cryptographic schemes like RSA and Elliptic Curve Cryptography (ECC) insecure. This imminent threat necessitates a paradigm shift towards post-quantum cryptography (PQC), which aims to develop cryptographic algorithms resistant to both classical and quantum attacks. Among the various candidates for PQC, lattice-based cryptography has emerged as a particularly promising area. This paper provides a comprehensive overview of the transition from classical number theory-based cryptography to lattice-based schemes. We explore the fundamental mathematical principles underlying lattices, introduce key lattice problems such as the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), Small Integer Solution (SIS), and Learning With Errors (LWE), and discuss their application in constructing quantum-resistant cryptographic primitives. Furthermore, we analyze the security, efficiency, and practical considerations of prominent lattice-based cryptosystems, highlighting their role in the ongoing NIST post-quantum cryptography standardization process. The paper concludes by discussing the challenges and future directions in the deployment and research of lattice-based cryptographic solutions.

•Feb 9, 2026•0 citations

Improved (Provable) Algorithms for the Shortest Vector Problem via Bounded Distance Decoding

Divesh Aggarwal, Yanlin Chen, Rajendra Kumar +1 more

The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results. 1) A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer 4 ≤ q ≤ √n, our algorithm takes q^{13n+o(n)} time and requires poly(n)⋅ q^{16n/q²} memory. This tradeoff which ranges from enumeration (q = √n) to sieving (q constant), is a consequence of a new time-memory tradeoff for Discrete Gaussian sampling above the smoothing parameter. 2) A quantum algorithm that runs in time 2^{0.9533n+o(n)} and requires 2^{0.5n+o(n)} classical memory and poly(n) qubits. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [Divesh Aggarwal et al., 2015] that has a time and space complexity 2^{n+o(n)}. 3) A classical algorithm for SVP that runs in time 2^{1.741n+o(n)} time and 2^{0.5n+o(n)} space. This improves over an algorithm of [Yanlin Chen et al., 2018] that has the same space complexity. The time complexity of our classical and quantum algorithms are expressed using a quantity related to the kissing number of a lattice. A known upper bound of this quantity is 2^{0.402n}, but in practice for most lattices, it can be much smaller and even 2^o(n). In that case, our classical algorithm runs in time 2^{1.292n} and our quantum algorithm runs in time 2^{0.750n}.

Leibniz international proceedings in informatics•Jan 1, 2021•1 citation
Abstract Lattice-based cryptographic regimes are the most promising quantum-resistant cryptographic algorithms, whose security depends on the difficulty of the SVP. Enumeration algorithms are the most basic and hopeful algorithms instantiated for solving SVPs, and are often used in public key cryptanalysis or as subroutines of lattice reduction algorithms. In this paper, we show how to speed up enumeration with the idea of nested search: if N is the number of nodes in the enumeration tree and T is the time required to process a node, our quantum enumeration can find the shortest vector on the lattice in time (\sqrt{T\cdot N}) . This is applied to the two most efficient types of enumeration: cylinder pruning as well as discrete pruning. The core idea of the algorithm is to reduce the size of the search space by transforming the original problem into a constraint-satisfiable problem, using the pruning conditions of the above two enumerations as constraints, and embedding the search for all possible solutions at the next level of the enumeration tree into the space of partially satisfied solutions at the previous level. Next, we accelerate this process using a quantum search algorithm. Compared to the work of bib24, we further reduce the time complexity of the algorithm with multiplication factor T\sqrt{T} T​ by the quantum nested search algorithm.
A quantum algorithm is known that solves an unstructured search problem in a number of iterations of order d,\sqrt{d},d​, where d is the dimension of the search space, whereas any classical algorithm necessarily scales as O(d).O(d).O(d). It is shown here that an improved quantum search algorithm can be devised that exploits the structure of a tree search problem by nesting one quantum search within another. The average number of iterations required to find the solution of a typical hard instance of a constraint satisfaction problem is found to scale as $\sqrt{{d}^{\ensuremath{\alpha}}},$ with the constant $\ensuremath{\alpha}<1$ depending on the nesting depth and the type of problem considered. This corresponds to a square-root speedup over a classical nested search algorithm, of which our algorithm is the quantum counterpart. When applying a single nesting level to a problem with constraints of size 2 such as the graph coloring problem, $\ensuremath{\alpha}$ is estimated to be around 0.62.
The lattice-based encryption paradigm (LBE) represents a new security model emphasizing flexible development, high levels of security, and efficient computations. It is now becoming more commonly seen as an alternative to other systems of post-quantum cryptography due to its foundations for both security (i.e., there is a high degree of confidence that lattice-based cryptography is secure) and efficiency with respect to computation. The theoretical basis for this report is related to the difficulty of solving the short vector problem (SVP) and other cryptographic hard problems concerning lattices. The report focuses on the hardness of lattice-based cryptography relative to three sub-components of the theoretical work: the relationship between geometric number theory and lattice-based systems, the application of AI to help determine parameters and the efficiencies of finding new lattice reduction algorithms, and finally estimating the difficulty to solve lattice problems. This report reviews the inherent difficulty of short vector problems (SVPs) and other kinds of SVPs, such as the closest vector problem. The report analyzes how to reduce both the time and space complexities for classical and quantum computing solutions through the discovery of new techniques based upon number-theoretic concepts. The report also discusses a number of examples, including digital signature products, encryption systems and homomorphic encryption systems as primitive constructions of cryptography based on lattices or through the properties of the lattice structures. Finally, based on number-theoretical relationships among complex numbers, the report provides a new theoretical approach to the construction of lattice-based systems and their strength relative to other types of cryptographic systems via the provision of theoretical bounds related to the lengths of lattice basis vectors.As a result of this research into bridging the divide between theoretical and practical cryptography, the results show that lattice-based systems have the capability of providing the strength to withstand quantum attacks. Through this research study, there is an improvement in how we understand mathematically the difficulty of lattices and how to create post-quantum secure cryptographic techniques through the use of lattices...
A lattice is the integer span of some linearly independent vectors. Lattice problems have many significant applications in coding theory and cryptographic systems for their conjectured hardness. The Shortest Vector Problem (SVP), which asks to find a shortest nonzero vector in a lattice, is one of the well-known problems that are believed to be hard to solve, even with a quantum computer. In this paper we propose space-efficient classical and quantum algorithms for solving SVP. Currently the best time-efficient algorithm for solving SVP takes 2^{n+o(n)} time and 2^{n+o(n)} space. Our classical algorithm takes 2^{2.05n+o(n)} time to solve SVP and it requires only 2^{0.5n+o(n)} space. We then adapt our classical algorithm to a quantum version, which can solve SVP in time 2^{1.2553n+o(n)} with 2^{0.5n+o(n)} classical space and only poly(n) qubits.
A fundamental computational problem is to find a shortest non-zero vector in Euclidean lattices, a problem known as the Shortest Vector Problem (SVP). This problem is believed to be hard even on quantum computers and thus plays a pivotal role in post-quantum cryptography. In this work we explore how (efficiently) Noisy Intermediate Scale Quantum (NISQ) devices may be used to solve SVP. Specifically, we map the problem to that of finding the ground state of a suitable Hamiltonian. In particular, (i) we establish new bounds for lattice enumeration, this allows us to obtain new bounds (resp. estimates) for the number of qubits required per dimension for any lattices (resp. random q-ary lattices) to solve SVP; (ii) we exclude the zero vector from the optimization space by proposing (a) a different classical optimisation loop or alternatively (b) a new mapping to the Hamiltonian. These improvements allow us to solve SVP in dimension up to 28 in a quantum emulation, significantly more than what was previously achieved, even for special cases. Finally, we extrapolate the size of NISQ devices that is required to be able to solve instances of lattices that are hard even for the best classical algorithms and find that with approximately 103 noisy qubits such instances can be tackled.
The landscape of modern cryptography, traditionally anchored in the computational hardness of number-theoretic problems such as integer factorization and the discrete logarithm problem, faces an existential threat from the advent of quantum computing. Shor's algorithm, discovered in 1994, demonstrates the theoretical capability of a sufficiently powerful quantum computer to efficiently solve these problems, rendering widely used cryptographic schemes like RSA and Elliptic Curve Cryptography (ECC) insecure. This imminent threat necessitates a paradigm shift towards post-quantum cryptography (PQC), which aims to develop cryptographic algorithms resistant to both classical and quantum attacks. Among the various candidates for PQC, lattice-based cryptography has emerged as a particularly promising area. This paper provides a comprehensive overview of the transition from classical number theory-based cryptography to lattice-based schemes. We explore the fundamental mathematical principles underlying lattices, introduce key lattice problems such as the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), Small Integer Solution (SIS), and Learning With Errors (LWE), and discuss their application in constructing quantum-resistant cryptographic primitives. Furthermore, we analyze the security, efficiency, and practical considerations of prominent lattice-based cryptosystems, highlighting their role in the ongoing NIST post-quantum cryptography standardization process. The paper concludes by discussing the challenges and future directions in the deployment and research of lattice-based cryptographic solutions.
The most important computational problem on lattices is the Shortest Vector Problem (SVP). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for SVP. We present the following results. 1) A new algorithm for SVP that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer 4 ≤ q ≤ √n, our algorithm takes q^{13n+o(n)} time and requires poly(n)⋅ q^{16n/q²} memory. This tradeoff which ranges from enumeration (q = √n) to sieving (q constant), is a consequence of a new time-memory tradeoff for Discrete Gaussian sampling above the smoothing parameter. 2) A quantum algorithm that runs in time 2^{0.9533n+o(n)} and requires 2^{0.5n+o(n)} classical memory and poly(n) qubits. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [Divesh Aggarwal et al., 2015] that has a time and space complexity 2^{n+o(n)}. 3) A classical algorithm for SVP that runs in time 2^{1.741n+o(n)} time and 2^{0.5n+o(n)} space. This improves over an algorithm of [Yanlin Chen et al., 2018] that has the same space complexity. The time complexity of our classical and quantum algorithms are expressed using a quantity related to the kissing number of a lattice. A known upper bound of this quantity is 2^{0.402n}, but in practice for most lattices, it can be much smaller and even 2^o(n). In that case, our classical algorithm runs in time 2^{1.292n} and our quantum algorithm runs in time 2^{0.750n}.