The closest vector problem (CVP) is a fundamental optimization problem in lattice-based cryptography and its conjectured hardness underpins the security of lattice-based cryptosystems. Furthermore, Schnorr's lattice-based factoring algorithm reduces integer factoring (the foundation of current cryptosystems, including RSA) to the CVP. Recent work has investigated the inclusion of a heuristic CVP approximation `refinement' step in the lattice-based factoring algorithm, using quantum variational algorithms to perform the heuristic optimization. This coincides with the emergence of probabilistic computing as a hardware accelerator for randomized algorithms including tasks in combinatorial optimization. In this work we investigate the application of probabilistic computing to the heuristic optimization task of CVP approximation refinement in lattice-based factoring. We present the design of a probabilistic computing algorithm for this task, a discussion of `prime lattice' parameters, and experimental results showing the efficacy of probabilistic computing for solving the CVP as well as its efficacy as a subroutine for lattice-based factoring. The main results found that (a) this approach is capable of finding the maximal available CVP approximation refinement in time linear in problem size and (b) probabilistic computing used in conjunction with the lattice parameters presented can find the composite prime factors of a semiprime number using up to 100x fewer lattice instances than similar quantum and classical methods.
The closest vector problem (CVP) is a fundamental optimization problem in lattice-based cryptography and its conjectured hardness underpins the security of lattice-based cryptosystems. Furthermore, Schnorr's lattice-based factoring algorithm reduces integer factoring (the foundation of current cryptosystems, including RSA) to the CVP. Recent work has investigated the inclusion of a heuristic CVP approximation refinement' step in the lattice-based factoring algorithm, using quantum variational algorithms to perform the heuristic optimization. This coincides with the emergence of probabilistic computing as a hardware accelerator for randomized algorithms including tasks in combinatorial optimization. In this work we investigate the application of probabilistic computing to the heuristic optimization task of CVP approximation refinement in lattice-based factoring. We present the design of a probabilistic computing algorithm for this task, a discussion of prime lattice' parameters, and experimental results showing the efficacy of probabilistic computing for solving the CVP as well as its efficacy as a subroutine for lattice-based factoring. The main results found that (a) this approach is capable of finding the maximal available CVP approximation refinement in time linear in problem size and (b) probabilistic computing used in conjunction with the lattice parameters presented can find the composite prime factors of a semiprime number using up to 100x fewer lattice instances than similar quantum and classical methods.
Abstract The NP-hardness of the closest vector problem (CVP) is an important basis for quantum-secure cryptography, in much the same way that integer factorisation’s conjectured hardness is at the foundation of cryptosystems like RSA. Recent work with heuristic quantum algorithms (Yan et al 2022 arXiv: 2212.12372 [quant-ph]) indicates the possibility to find close approximations to (constrained) CVP instances that could be incorporated within fast sieving approaches for factorisation. This work explores both the practicality and scalability of the proposed heuristic approach to explore the potential for a quantum advantage for approximate CVP, without regard for the subsequent factoring claims. We also extend the proposal to include an antecedent ‘pre-training’ scheme to find and fix a set of parameters that generalise well to increasingly large lattices, which both optimises the scalability of the algorithm, and permits direct numerical analyses. Our results further indicate a noteworthy quantum speed-up for lattice problems obeying a certain ‘prime’ structure, approaching fifth order advantage for quantum approximate optimisation algorithm of fixed depth p = 10 compared to classical brute-force, motivating renewed discussions about the necessary lattice dimensions for quantum-secure cryptosystems in the near-term.
Inspired by quantum annealing, digital annealing computers specified for annealing computations have been realized on a large scale, such as the Digital Annealer (DA) developed by Fujitsu and the CMOS Annealing Machine developed by Hitachi. With the progress achieved using these computers, it has become necessary to estimate the computational hardness of cryptographic problems. This paper focuses on lattice problems, such as the closest vector problem (CVP) and shortest vector problem (SVP), which are a class of optimization problems. These problems form the basis of the security of lattice-based cryptography, which is a prime candidate for the NIST post-quantum cryptography standardization. For these lattice problems, we propose methods for generating an Ising model and solving the Ising model on annealing computers with a bit representation as the input, which represents encodings to map each integer variable in the SVP into binary variables. We propose two methods for SVPs, a basic method and a variant incorporating approximately the concept of the classical lattice enumeration. In our experimental results obtained using the second-generation DA, we succeeded in finding a shortest nonzero lattice vector in 40- and 45-dimensional lattices in the Darmstadt SVP Challenge. The basic method with a hybrid bit representation was the fastest among our methods with a bit representation, and the expected running time was estimated as 664 and 13,750 seconds for the 40- and 45-dimensional lattices, respectively. These results provide a benchmark for solving the SVP with annealing computers.
The advent of large-scale quantum computers poses an existential threat to the security of current public-key cryptosystems, such as RSA and Elliptic Curve Cryptography (ECC), which rely on the computational intractability of integer factorization and discrete logarithms. This paper explores lattice-based cryptography as a promising candidate for post-quantum security. We delve into the mathematical foundations of lattices, specifically focusing on hard problems like the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), Small Integer Solution (SIS), and Learning With Errors (LWE) problems, which are believed to remain intractable even for quantum computers. We provide a comprehensive review of prominent lattice-based constructions, including NTRU, Kyber, and Dilithium, highlighting their security proofs, efficiency considerations, and suitability for various cryptographic primitives such as public-key encryption, key-exchange mechanisms, and digital signatures. Furthermore, we discuss the challenges and opportunities associated with their deployment, including parameter selection, resistance to side-channel attacks, and integration into existing cryptographic infrastructures. By examining the theoretical underpinnings and practical implications, this work aims to solidify understanding of lattice-based methods as a robust and essential component of the cryptographic landscape in the quantum era, moving beyond the traditional RSA frontier.
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 availability of working quantum computers has led to several proposals and claims of quantum advantage. In 2023, this has included claims that quantum computers can successfully factor large integers, by optimizing the search for nearby integers whose prime factors are all small. This paper demonstrates that the hope of factoring numbers of commercial significance using these methods is unfounded. Mathematically, this is because the density of smooth numbers (numbers all of whose prime factors are small) decays exponentially as n grows. Our experimental reproductions and analysis show that lattice-based factoring does not scale successfully to larger numbers, that the proposed quantum enhancements do not alter this conclusion, and that other simpler classical optimization heuristics perform much better for lattice-based factoring. However, many topics in this area have interesting applications and mathematical challenges, independently of factoring itself. We consider particular cases of the CVP, and opportunities for applying quantum techniques to other parts of the factorization pipeline, including the solution of linear equations modulo 2. Though the goal of factoring 1000-bit numbers is still out-of-reach, the combinatoric landscape is promising, and warrants further research with more circumspect objectives.
In 1994, P. Shor discovered quantum algorithms that can break both the RSA cryptosystem and the ElGamal cryptosystem. In 2007, D-Wave demonstrated the first quantum computer. These events and further developments have brought a crisis to secret communication. In 2016, the National Institute of Standards and Technology (NIST) launched a global project to solicit and select a handful of encryption algorithms with the ability to resist quantum computer attacks. In 2022, it announced four candidates, CRYSTALS-Kyber, CRYSTALS-Dilithium, Falcon, and Sphincs+, for post-quantum cryptography standards. The first three are based on lattice theory and the last on a hash function. The security of lattice-based cryptosystems relies on the computational complexity of the shortest vector problem (SVP), the closest vector problem (CVP), and their generalizations. As we will explain, the SVP is a ball-packing problem, and the CVP is a ball-covering problem. Furthermore, both the SVP and CVP are equivalent to arithmetic problems for positive definite quadratic forms. This paper will briefly describe the mathematical problems on which lattice-based cryptography is built so that cryptographers can extend their views and learn something useful.