The security of classical public-key cryptosystems, which operate based on the computational intractability of integer factorization and discrete logarithm problems, is profoundly threatened by the rapid development of quantum computing. Post-Quantum Cryptography (PQC) has been proposed to improve security against quantum attacks. Lattice-based cryptography is widely regarded as one of the most promising PQC method because of its proven security, efficient implementation, and functional versatility, and it has achieved significant progress in both algorithmic design and engineering implementation in recent years. This paper presents a systematic survey of the status of research on lattice-based cryptographic algorithms. First, the fundamental theory of lattices and their core hard problems are discussed. Next, the technical characteristics and performance of encryption and key encapsulation mechanisms, digital signature schemes, and key exchange protocols constructed based on lattice hard problems are reviewed and compared. Subsequently, the principles and optimization paths of two key technologies for lattice cryptography implementation, namely polynomial multiplication using the fast Number Theoretic Transform (NTT) and pre-image sampling algorithms, are discussed. Finally, considering the PQC standardization process of the National Institute of Standards and Technology (NIST), an outlook on future research directions for lattice-based cryptography is presented. The research directions include the development of more "succinct" fundamental hard problems, strengthening security proofs, improving algorithm efficiency, and countering novel attacks. This review serves as a reference for promoting the practical deployment and further research of lattice-based cryptography.
The security of classical public-key cryptosystems, which operate based on the computational intractability of integer factorization and discrete logarithm problems, is profoundly threatened by the rapid development of quantum computing. Post-Quantum Cryptography (PQC) has been proposed to improve security against quantum attacks. Lattice-based cryptography is widely regarded as one of the most promising PQC method because of its proven security, efficient implementation, and functional versatility, and it has achieved significant progress in both algorithmic design and engineering implementation in recent years. This paper presents a systematic survey of the status of research on lattice-based cryptographic algorithms. First, the fundamental theory of lattices and their core hard problems are discussed. Next, the technical characteristics and performance of encryption and key encapsulation mechanisms, digital signature schemes, and key exchange protocols constructed based on lattice hard problems are reviewed and compared. Subsequently, the principles and optimization paths of two key technologies for lattice cryptography implementation, namely polynomial multiplication using the fast Number Theoretic Transform (NTT) and pre-image sampling algorithms, are discussed. Finally, considering the PQC standardization process of the National Institute of Standards and Technology (NIST), an outlook on future research directions for lattice-based cryptography is presented. The research directions include the development of more "succinct" fundamental hard problems, strengthening security proofs, improving algorithm efficiency, and countering novel attacks. This review serves as a reference for promoting the practical deployment and further research of lattice-based cryptography.
Classical cryptography has been around for a long time in the documented human history, but most classical ciphers were broken and even solved by hand. Shannon introduced the notion of perfect secrecy that formally defines confidentiality in the information-theoretic sense, which is only possible in the restricted scenarios where the message is no longer than the encryption key. The invention of public-key cryptography (the Diffie-Hellman key exchange protocol in 1976 and the RSA crypto-system in 1977) marks the birth of modern cryptography, allowing parties to exchange messages securely without sharing any secrets in advance. Furthermore, it provides computational security based on the conjectured hardness of mathematical problems such as factorization and the discrete logarithm. Public-key cryptography has found numerous applications in the Internet, financial and banking industry, and blockchains, and it plays a crucial role in protecting information security and asset safety. Unfortunately, in the 1990s, Shor proposed efficient quantum algorithms that solve number-theoretic problems, including factorization and discrete logarithms in polynomial time. Once a quantum computer of a particular scale becomes a reality, it will cause a devastating blow to the existing public-key infrastructure. To deal with such a ‘quantum crisis’, academia and industry are looking into the design, analysis and standardization of cryptographic algorithms that can resist quantum computers referred to as post-quantum cryptography (PQC). The National Institute of Standards and Technology (NIST) has been soliciting proposals for the post-quantum public-key algorithms since 2016. More recently, the Chinese Association for Cryptologic Research (CACR) held a competition on designing cryptographic algorithms whose public-key cryptography track focused on post-quantum cryptographic algorithms. Lattice-based cryptography is considered by most to be the mainstream technical route of post-quantum cryptography, which is reflected in the number of proposals (and their percentage of the total) received in the NIST PQC process. To reflect the status quo of post-quantum cryptography, we invite leading experts in this area to contribute three technical perspectives that aim to help readers understand the algorithms, the underlying basic techniques and different technical routes to achieve quantum resistance. The first perspective, presented by Lu and Zhang, introduces public-key cryptographic algorithms whose quantum security is reducible from the conjectured quantum hardness of lattice problems. In particular, they mainly focus on public-key encryption (PKE) and the key encapsulation mechanism (KEM), which are essential building blocks for securing the confidentiality of communication without pre-shared secrets. Both types of crypto-systems are solicited by the NIST PQC standardization and the CACR algorithm design competition. This perspective gives a comprehensive survey on practical lattice-based PKEs/KEMs, and their best-known quantum and classical attacks. Another important post-quantum crypto-system is digital signature, which ensures that three goals of information security are met other than confidentiality, namely, integrity, authentication and non-repudiation. The second perspective is on lattice-based signature by Lyubashevsky. In this perspective, he surveys different techniques in building lattice-based post-quantum crypto-systems, discusses the challenges in overcoming performance issues and gives us state-of-the-art digital signature schemes. In addition to ensuring the ‘static’ security of information in storage and transmission, advanced cryptographic algorithms and protocols can guarantee information security during the computation process (possibly among multiple parties), referred to as privacy-preserving computation. Cryptographic techniques involved in privacy-preserving computation include secure multi-party computation, zero-knowledge proof and fully homomorphic encryption. There is a pressing need to migrate them to the post-quantum era. The third perspective, by Yu and Xie, presents practical instantiations of these algorithms and discusses possible ways to migrate them to their quantum-resistant counterparts. To summarize, post-quantum cryptography has received widespread attention and made significant progress in recent years. Some post-quantum cryptographic algorithms, such as the lattice-based candidate, also have other advantages (e.g., computational efficiency and full homomorphism) over their classical counterparts. Lattice-based cryptography is an emerging field with high theoretical value and wide application, and we encourage young researchers to enter and explore this new and exciting field.
The need and emergence of quantum computing under National Quantum Mission threatens the cyber-security of existing cryptographic protocols, especially public-key schemes built on integer factorization and discrete logarithms. Lattice-based cryptography has gained prominence as a robust candidate for post-quantum cryptography—offering security against quantum attacks while enabling efficient operations, parallelization, and novel functionalities. This paper analyzes the mathematical foundations of lattices, explores hardness assumptions underlying widely studied lattice problems, highlights prominent cryptographic constructions, analyzes performance trade-offs, and reviews standardization efforts. This paper concludes by identifying ongoing issues and future directions for lattice-based cryptographic systems in a quantum-secure digital world. The algorithm has been implemented in Python.
Mostly, existing public-key cryptosystems are constructed on the mathematical complexity of large integer factorization and solving discrete logarithms, which will be irresistible to attacks of future quantum computers. Due to the rapidly growing vulnerabilities in cryptographic systems recently, post-quantum cryptography (PQC) has turned out to be a need for the crypto community and has become a necessary research domain for the welfare of society. Lattice-based cryptography is measured as the most capable PQC because of its intense security proofs based on worst-case hardness, balanced performance in security, and efficient computation. This chapter provides a mathematical foundation of lattice-based cryptography, existing digital signatures, different attacks on lattice-based signatures with toy examples, challenges in lattice-based digital signatures, and future research directions. For scholars and academicians functioning in this emerging field of post PQC, the main unresolved issues evaluated in this study will provide an easily navigable reference and a unified, comprehensive source of data on lattice-based cryptography.
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 imminent threat posed by the development of cryptographically relevant quantum computers necessitates a paradigm shift in public-key cryptography. Traditional cryptosystems like RSA and Elliptic Curve Cryptography (ECC), which underpin global digital security, are vulnerable to quantum algorithms such as Shor's algorithm. This vulnerability mandates a proactive migration to post-quantum cryptography (PQC) to secure long-term sensitive data. Among the various candidates for post-quantum security, lattice-based cryptography has emerged as a particularly promising and robust solution. This paper explores the fundamental principles of lattice-based cryptography, detailing its security foundations rooted in the presumed hardness of lattice problems like the Short Integer Solution (SIS) and Learning With Errors (LWE) problems. We review the significant progress in the field, including its selection as a primary candidate in the NIST Post-Quantum Cryptography standardization process. We discuss its advantages in terms of provable security, versatility, and potential for efficient implementation across diverse platforms, from cloud infrastructure to the Internet of Things (IoT). We also address the practical implications and challenges of its deployment, asserting its indispensable role in fortifying public-key security against future quantum attacks, thereby establishing it as a post-quantum imperative.
The advent of large-scale quantum computers poses a profound and imminent threat to the security foundations of modern cryptography. Widely deployed public-key cryptosystems, such as RSA and Elliptic Curve Cryptography (ECC), rely on problems like integer factorization and discrete logarithms, which Shor's algorithm can efficiently solve. This necessitates a proactive transition to post-quantum cryptography (PQC). Among leading candidates, lattice-based cryptography stands out due to its robust security guarantees, based on hard problems lacking known efficient quantum solutions, and structural properties facilitating efficient implementation. This paper explores the fundamental principles of lattice-based cryptography, detailing underlying mathematical hard problems such as the Shortest Vector Problem (SVP) and Learning With Errors (LWE). We review the evolution of lattice-based schemes, from early constructions to contemporary candidates like Kyber and Dilithium, emphasizing their suitability for Key Encapsulation Mechanisms (KEMs) and Digital Signature Schemes (DSS). Furthermore, we analyze their performance characteristics, security assumptions, and resilience against classical and quantum attacks, providing a critical comparison with other PQC families. This comprehensive overview, structured through a systematic critical analysis framework, highlights the ascendancy of lattice-based cryptography as a cornerstone for future quantum-resistant security infrastructure, offering theoretical underpinnings, practical implications, and actionable future research directions for a post-quantum world.