Despite being considered the first practical lattice-based cryptosystem, interest from the post-quantum cryptography society in the Goldreich-Goldwasser-Halevi (GGH) lattice-based cryptosystem drastically drop due to the embedding-based attacks. The attacks successfully simplified the underlying Closest-Vector Problem (CVP) and made the security of the scheme broken. The attacks become noxious to the GGH cryptosystem due to its ability to simplify the underlying CVP which triggered the enlargement of lattice gaps. Consequently, the simplified CVP can be reduced to a Shortest-Vector Problem (SVP) variant which can be solved by using lattice-reduction algorithms such as the LLL algorithm in a shorter amount of time. The simpler way to evade from these attacks is by implementing larger lattice dimensions which immediately reduce the efficiency of this scheme. Recently, an improved version of the GGH cryptosystem, namely the GGH-MKA cryptosystem, has been proven immune to the embedding-based attacks. The improvement is made by preventing the simplification of the underlying CVP. For that purpose, an error vector is introduced. The error vector is non-eliminable and at the same time maintains the lattice gap. Consequently, the underlying CVP remains in its original form without being simplified. In this study, we showed that the error vector is not unique. We proposed another error vector to combat the embedding-based attacks. We proved that the new error vector has similar capabilities in terms of preventing the simplification of the underlying CVP and maintaining the lattice gap. By improving the security of the GGH cryptosystem, more interest from the mainstream post-quantum discussion could be redirected to the scheme to make it competent and relevant again.
Despite being considered the first practical lattice-based cryptosystem, interest from the post-quantum cryptography society in the Goldreich-Goldwasser-Halevi (GGH) lattice-based cryptosystem drastically drop due to the embedding-based attacks. The attacks successfully simplified the underlying Closest-Vector Problem (CVP) and made the security of the scheme broken. The attacks become noxious to the GGH cryptosystem due to its ability to simplify the underlying CVP which triggered the enlargement of lattice gaps. Consequently, the simplified CVP can be reduced to a Shortest-Vector Problem (SVP) variant which can be solved by using lattice-reduction algorithms such as the LLL algorithm in a shorter amount of time. The simpler way to evade from these attacks is by implementing larger lattice dimensions which immediately reduce the efficiency of this scheme. Recently, an improved version of the GGH cryptosystem, namely the GGH-MKA cryptosystem, has been proven immune to the embedding-based attacks. The improvement is made by preventing the simplification of the underlying CVP. For that purpose, an error vector is introduced. The error vector is non-eliminable and at the same time maintains the lattice gap. Consequently, the underlying CVP remains in its original form without being simplified. In this study, we showed that the error vector is not unique. We proposed another error vector to combat the embedding-based attacks. We proved that the new error vector has similar capabilities in terms of preventing the simplification of the underlying CVP and maintaining the lattice gap. By improving the security of the GGH cryptosystem, more interest from the mainstream post-quantum discussion could be redirected to the scheme to make it competent and relevant again.
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.
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.
The advent of quantum computing poses a significant existential threat to the security foundations of current public-key cryptography, most notably the widely adopted RSA algorithm. Shor's algorithm, specifically, can efficiently break the mathematical problems underlying RSA and elliptic curve cryptography, necessitating a paradigm shift towards quantum-resistant solutions. This paper explores lattice-based cryptography as the leading candidate for this post-quantum era. We delve into the fundamental mathematical principles of lattices, including hard problems like the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), Short Integer Solution (SIS), and Learning With Errors (LWE), which form the bedrock of their security. The paper reviews prominent lattice-based schemes such as NTRU, CRYSTALS-Kyber, CRYSTALS-Dilithium, and Falcon, highlighting their construction, security properties, and performance characteristics. We analyze their resilience against both classical and quantum attacks, discuss their progress in the NIST Post-Quantum Cryptography Standardization process, and evaluate their practical implications and implementation challenges. The discussion emphasizes the provable security, versatility, and efficiency of lattice-based methods, positioning them as the robust and essential successor to RSA for safeguarding digital communications and data in a quantum-enabled future.
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...
The advent of quantum computing poses a significant existential threat to current public-key cryptographic systems, most notably RSA and Elliptic Curve Cryptography (ECC), which rely on the presumed hardness of integer factorization and discrete logarithm problems. Shor's algorithm, a quantum algorithm, can efficiently solve these problems, rendering classical asymmetric primitives insecure. This paper addresses the imperative need for post-quantum cryptography (PQC) by exploring lattice-based constructs as robust alternatives for asymmetric primitives. We provide a comprehensive overview of the fundamental mathematical problems underlying lattice-based cryptography, such as the Shortest Vector Problem (SVP), Closest Vector Problem (CVP), Learning With Errors (LWE), and Ring Learning With Errors (RLWE). The paper surveys prominent lattice-based schemes, including NTRU, CRYSTALS-Kyber, and CRYSTALS-Dilithium, analyzing their security foundations, performance characteristics, and the extent to which they offer a viable "post-quantum RSA." We delve into the methodology of constructing these primitives, discuss their resilience against both classical and quantum attacks, and evaluate their practical implications for key sizes, computational efficiency, and deployment challenges. Our analysis highlights that lattice-based cryptography, particularly the NIST-standardized schemes, presents a strong candidate for securing digital communications in the quantum era, offering provable security rooted in worst-case to average-case reductions for lattice problems.
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.