In this paper, we provide a comprehensive overview of a recent debate over the quantum versus classical solvability of bounded distance decoding (BDD). Specifically, we review the work of Eldar and Hallgren [EH22], [Hal21] demonstrating a quantum algorithm solving $λ_1 2^{-Ω(\sqrt{k \log q})}$-BDD in polynomial time for lattices of periodicity $q$, finite group rank $k$, and shortest lattice vector length $λ_1$. Subsequently, we prove the results of [DvW21a], [DvW21b] with far greater detail and elaboration than in the original work. Namely, we show that there exists a deterministic, classical algorithm achieving the same result.
In this paper, we provide a comprehensive overview of a recent debate over the quantum versus classical solvability of bounded distance decoding (BDD). Specifically, we review the work of Eldar and Hallgren [EH22], [Hal21] demonstrating a quantum algorithm solving λ12−Ω(klogq)-BDD in polynomial time for lattices of periodicity q, finite group rank k, and shortest lattice vector length λ1. Subsequently, we prove the results of [DvW21a], [DvW21b] with far greater detail and elaboration than in the original work. Namely, we show that there exists a deterministic, classical algorithm achieving the same result.
We give a quantum algorithm for solving the Bounded Distance Decoding (BDD) problem with a subexponential approximation factor on a class of integer lattices. The quantum algorithm uses a well-known but challenging-to-use quantum state on lattices as a type of approximate quantum eigenvector to randomly self-reduce the BDD instance to a random BDD instance which is solvable classically. The running time of the quantum algorithm is polynomial for one range of approximation factors and subexponential time for a second range of approximation factors. The subclass of lattices we study has a natural description in terms of the lattice's periodicity and finite abelian group rank. This view makes for a clean quantum algorithm in terms of finite abelian groups, uses very relatively little from lattice theory, and suggests exploring approximation algorithms for lattice problems in parameters other than dimension alone. A talk on this paper sparked many lively discussions and resulted in a new classical algorithm matching part of our result. We leave it as a challenge to give a classcial algorithm matching the general case.
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. ∙ 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 q13n+o(n) time and requires poly(n)⋅q16n/q2 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. ∙ A quantum algorithm for SVP that runs in time 20.950n+o(n) and requires 20.5n+o(n) classical memory and poly(n) qubits. In Quantum Random Access Memory (QRAM) model this algorithm takes only 20.835n+o(n) time and requires a QRAM of size 20.293n+o(n), poly(n) qubits and 20.5n classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [ADRS15] that has a time and space complexity 2n+o(n). ∙ A classical algorithm for SVP that runs in time 21.669n+o(n) time and 20.5n+o(n) space. This improves over an algorithm of [CCL18] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number which is 20.402n. We conjecture that for most lattices this quantity is a 2o(n). Assuming that this is the case, our classical algorithm runs in time 21.292n+o(n), our quantum algorithm runs in time 20.750n+o(n) and our quantum algorithm in QRAM model runs in time 20.667n+o(n).
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}.
The Systematic Normal Form (SysNF) is a canonical form of lattices introduced in [Eldar,Shor '16], in which the basis entries satisfy a certain co-primality condition. Using a "smooth" analysis of lattices by SysNF lattices we design a quantum algorithm that can efficiently solve the following variant of the bounded-distance-decoding problem: given a lattice L, a vector v, and numbers b = λ_1(L)/n^{17}, a = λ_1(L)/n^{13} decide if v's distance from L is in the range [a/2, a] or at most b, where λ_1(L) is the length of L's shortest non-zero vector. Improving these parameters to a = b = λ_1(L)/\sqrt{n} would invalidate one of the security assumptions of the Learning-with-Errors (LWE) cryptosystem against quantum attacks.
Abstract. The most important computational problem on lattices is the shortest vector problem ([Formula: see text]). In this paper, we present new algorithms that improve the state-of-the-art for provable classical/quantum algorithms for [Formula: see text]. We present the following results: (1) A new algorithm for [Formula: see text] that provides a smooth tradeoff between time complexity and memory requirement. For any positive integer [Formula: see text], our algorithm takes [Formula: see text] time and requires [Formula: see text] memory. This tradeoff, which ranges from enumeration ([Formula: see text]) to sieving ([Formula: see text] constant), is a consequence of a new time-memory tradeoff for discrete Gaussian sampling above the smoothing parameter. (2) A quantum algorithm for [Formula: see text] that runs in time [Formula: see text] and requires [Formula: see text] classical memory and [Formula: see text] qubits. In a quantum random access memory (QRAM) model, this algorithm takes only [Formula: see text] time and requires a QRAM of size [Formula: see text], [Formula: see text] qubits and [Formula: see text] classical space. This improves over the previously fastest classical (which is also the fastest quantum) algorithm due to [D. Aggarwal et al., Solving the shortest vector problem in 2 n time using discrete Gaussian sampling: Extended abstract, in Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing (STOC), 2015, pp. 733–742] that has a time and space complexity [Formula: see text]. (3) A classical algorithm for [Formula: see text] that runs in time [Formula: see text] time and [Formula: see text] space. This improves over an algorithm of [Y. Chen, K. Chung, and C. Lai, Quantum Inf. Comput., 18 (2018), pp. 285–306] that has the same space complexity. The time complexity of our classical and quantum algorithms are obtained using a known upper bound on a quantity related to the lattice kissing number, which is [Formula: see text]. We conjecture that for most lattices this quantity is a [Formula: see text]. Assuming that this is the case, our classical algorithm runs in time [Formula: see text], our quantum algorithm runs in time [Formula: see text], and our quantum algorithm in a QRAM model runs in time [Formula: see text]. As a direct application of our result, using the reduction in [L. Ducas, Des. Codes. Cryptogr., 92 (2024), pp. 909–916], we obtain a provable quantum algorithm for the lattice isomorphism problem in the case of the trivial lattice [Formula: see text] ([Formula: see text] LIP ) that runs in time [Formula: see text]. Our algorithm requires a QRAM of size [Formula: see text], [Formula: see text] qubits and [Formula: see text] classical space.
In the upcoming era of quantum computation, those successful classical, number-theoretical public-key cryptosystems that get widely deployed nowadays, such as RSA or ElGamal, all face severe insecurity if the adversary gets access to quantum computers. More urgently, time-insensitive secrets on today’s systems are facing immediate threats of the same level due to the “harvest now, decrypt later” attack. The field of post-quantum cryptography aims at building quantum-safe systems to prepare for the future. Among all candidate post-quantum proposals, lattice-based cryptography, which builds cryptosystems based on lattice problems, so far provides the best results in terms of performance, simplicity, and versatility. It is thus important to better understand the complexity of lattice problems. In this thesis, we study a couple of new lower and upper bounds for various lattice problems under various complexity notions. These new results include: 1. (Fine-grained hardness/lower bounds.) The fine-grained (exponential-time) complexity studies the precise constant c in the 2^{n^c} or 2^{c·n} running time for solving a computational problem, usually based on (variants of) the exponential time hypothesis (ETH) or the strong exponential time hypothesis (SETH). Under this complexity notion, for the bounded distance decoding problem (BDD), we give quantitatively improved bounds on the approximation factor α for which BDD_α cannot be solved in 2^{o(n)} or 2^{c·n} time, assuming variants of ETH or SETH, respectively, and for part of our results also assuming a geometric conjecture known as exponential lattice kissing number. For the shortest vector problem (SVP), we show a qualitatively improved result that for some constant approximation factor γ>1, SVP_γ cannot be solved in 2^{c·n} time, assuming a variant of SETH; previously, only analogous result for non-approximate, exact SVP was known. 2. (“Standard” NP-hardness.) The NP-hardness is a classical flag for identifying a computational problem as being hard. For SVP, previously only NP-hardness results under randomized reductions are known (except in corner cases), and whether SVP is “standardly” NP-hard under deterministic reductions is a notoriously longstanding open problem. We propose conjectures about ways to derandomize existing reductions, which would lead to the “standard” NP-hardness of approximate SVP. We also present empirical evidences that support the conjectures. 3. (Parallel algorithms/upper bounds.) The parallel complexity/sequentiality of a computational problem is crucial for its applications in time-release/timed cryptography. We show logarithmic-depth parallel algorithms for a sequential version of the short integer solution problem (SIS), which is used in a certain proof of sequential work (PoSW) timed-cryptographic protocol. This means that sequential SIS has low parallel complexity, as opposed to its previous conjecture. Moreover, we show a polylogarithmic-depth parallel attack that (almost) breaks that PoSW protocol.