Due to the development of quantum computing, there is a need for development and analysis of cryptosystems resistant to attacks with using a quantum computer - post-quantum algorithms cryptography. The strength of many well-known post-quantum cryptosystems, based on the theory of lattices, is based on the complexity of solving the problem finding the shortest vector in the lattice (SVP). For the previously proposed models of the quantum oracle used in the hybrid quantum-classical algorithm for solving the SVP problem, new refined estimates of implementation complexity. Designed and analyzed a new quantum oracle model that uses classical memory to storing a list of vectors.
Due to the development of quantum computing, there is a need for development and analysis of cryptosystems resistant to attacks with using a quantum computer - post-quantum algorithms cryptography. The strength of many well-known post-quantum cryptosystems, based on the theory of lattices, is based on the complexity of solving the problem finding the shortest vector in the lattice (SVP). For the previously proposed models of the quantum oracle used in the hybrid quantum-classical algorithm for solving the SVP problem, new refined estimates of implementation complexity. Designed and analyzed a new quantum oracle model that uses classical memory to storing a list of vectors.
Abstract Due to the development of quantum computing, there is a need for the development and analysis of cryptosystems resistant to attacks using a quantum computer (post-quantum cryptography algorithms). The security of many well-known post-quantum cryptosystems based on lattice theory depends on the complexity of solving the shortest vector problem (SVP). In this paper, a model of quantum oracle developed from Grover’s algorithm is described to implement a hybrid quantum–classical algorithm based on GaussSieve. This algorithm can be used for attacks on cryptosystems whose security depends on solving the SVP. Upper bounds for the number of qubits and the depth of the circuit were obtained for two implementations of the proposed quantum oracle model: minimizing the number of qubits and minimizing the circuit depth. The complexity of implementing the proposed quantum oracle model to attack post-quantum lattice-based cryptosystems that are finalists of the NIST post-quantum cryptography competition is analyzed.
Abstract Lattice-based cryptosystems are one of the main post-quantum alternatives to asymmetric cryptography currently in use. Most attacks on these cryptosystems can be reduced to the shortest vector problem (SVP) in a lattice. Previously, the authors proposed a quantum oracle model from Grover’s algorithm to implement a hybrid quantum-classical algorithm based on the GaussSieve algorithm and solving SVP. In this paper, a new model of a quantum oracle is proposed and analyzed. Two implementations of the new quantum oracle model are proposed and estimated. The complexity of implementing the new quantum oracle model to attack post-quantum lattice-based cryptosystems that are finalists of the NIST post-quantum cryptography competition is analyzed. Comparison of obtained results for new and existing models of quantum oracle is given.
Finding the shortest vector in a lattice is a problem that is believed to be hard both for classical and quantum computers. Many major postquantum secure cryptosystems base their security on the hardness of the shortest vector problem (SVP) (Moody, 2023). Finding the best classical, quantum, or hybrid classical–quantum algorithms for the SVP is necessary to select cryptosystem parameters that offer a sufficient level of security. Grover's search quantum algorithm provides a generic quadratic speedup, given access to an oracle implementing some function, which describes when a solution is found. In this article, we provide concrete implementation of such an oracle for the SVP. We define the circuit and evaluate costs in terms of the number of qubits, the number of gates, depth, and T-quantum cost. We then analyze how to combine Grover's quantum search for small SVP instances with state-of-the-art classical solvers that use well-known algorithms, such as the block Korkine Zolotorev (Schnorr and Euchner, 1994), where the former is used as a subroutine. This could enable solving larger instances of SVP with higher probability than classical state-of-the-art records, but still very far from posing any threat to cryptosystems being considered for standardization. Depending on the technology available, there is a spectrum of tradeoffs in creating this combination.
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 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...