It is known that the development of quantum computers will break the cryptographic schemes that are in use today. Since Shor’s algorithm is able to solve the factoring and discrete logarithm problems, all cryptographic systems based on these two problems will get broken in the presence of large-scale quantum computers. Lattice-based schemes, however, are considered secure against attacks with these new machines. In this paper we present an overview of lattice-based cryptosystems, showing the most recent and the most promising candidates for encryption and signatures based on lattice problems. We explain the advantages and disadvantages of the cryptographic schemes. We also adjoin details about zero knowledge identification. With this work we try to give insight to one of the most promising candidates of future cryptography, for the time when potential quantum computers exist. We also point out drawbacks of these systems, which discloses directions for future work in lattice-based cryptography.
It is known that the development of quantum computers will break the cryptographic schemes that are in use today. Since Shor’s algorithm is able to solve the factoring and discrete logarithm problems, all cryptographic systems based on these two problems will get broken in the presence of large-scale quantum computers. Lattice-based schemes, however, are considered secure against attacks with these new machines. In this paper we present an overview of lattice-based cryptosystems, showing the most recent and the most promising candidates for encryption and signatures based on lattice problems. We explain the advantages and disadvantages of the cryptographic schemes. We also adjoin details about zero knowledge identification. With this work we try to give insight to one of the most promising candidates of future cryptography, for the time when potential quantum computers exist. We also point out drawbacks of these systems, which discloses directions for future work in 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.
Quantum computers are moving closer to reality, and with that comes a serious concern for today’s public-key cryptography. Many of the encryption and digital signature systems we rely on now, such as RSA and ECC, may no longer be secure in the future. Because of this, researchers are actively looking for new methods that can protect digital communication in the post-quantum era. One of the most promising directions is lattice-based cryptography. This paper gives a simple and focused review of lattice-based signature schemes. It brings together the main ideas from the existing literature and explains how these schemes are built, why they are considered secure, and what makes them practical. The review mainly discusses schemes based on hard lattice problems such as SIS and LWE. To make the comparison clearer, a table is also included that compares different signature schemes in terms of key size, signature size, security level, and computational efficiency. Overall, this study shows why lattice-based signature schemes are becoming an important part of modern cryptographic research and why they may play a major role in securing digital systems against future quantum threats.
Alongside the growth of technology is the increasing demand for security of data and communication channels. As attacking power grows, devices become smaller and data expands, the security needs to be stronger yet less resource-consuming than ever before. Public key cryptography (PKC) is used in the majority of today's communications systems. The security of public-key cryptographic schemes, such as RSA and elliptic curve cryptography (ECC), is based on underlying mathematical problems such as factoring large integers or solving the discrete log problem. However, the discovery of Shor's Algorithm in 1994 insinuates that these schemes will be insecure when a full-scale quantum computer is developed, as these problems will be solvable in polynomial time. Therefore attention has moved towards post-quantum, or quantum-safe, cryptography (QSC). In 2016, the National Institute of Standards and Technology (NIST) announced the beginning of their efforts to migrate to QSC, a standardisation process which has involved the cryptographic community worldwide. There are five main types of QSC being considered for standardisation; lattice-based, code-based, multivariate-based, hash-based and isogeny-based. Lattice-based cryptography (LBC) offers a promising alternative to today's classical approaches. Hard problems based on lattices are believed to be unsolvable, even by a quantum-computer, in a feasible amount of time. In 1995, Ajtai showed that the average case complexity of these problems is at least as hard as solving the problems in the worst case. Furthermore, lattice-based schemes are the only remaining contender in the NIST process to provide the important primitives of encryption, key encapsulation and digital signature schemes (DSSs). A well-recognised open problem surrounding quantum-safe cryptography is its increase in bandwidth and computational complexity in comparison to existing cryptography. However, in comparison to other quantum-safe schemes, LBC has been shown to be relatively efficient. In this thesis, novel software designs of lattice-based schemes are presented and shown to be competitive with existing PKC. Additionally, physical attacks are considered and countermeasures are incorporated into the designs. DSSs are required for authentication, integrity and non-repudiation of data. This thesis provides an evaluation of three leading signature schemes, BLISS-B, Dilithium and \textsc{Falcon}, which vary in terms of their key features, such as the sampling processes used, and the structure of the lattices. Physical attacks on the three schemes are considered and the effect on performance of appropriate attack countermeasures is evaluated. A novel fault attack on the NIST candidate \textsc{Falcon} is also proposed. A further advantage of LBC is the ability to support cryptographic primitives with extended capabilities to facilitate certificate management and compute on encrypted data. The complexity of today's technology advances mean applications require more sophisticated primitives, which contrastingly are required to run on even smaller platforms. This thesis presents novel quantum-safe advanced cryptographic schemes, specifically lattice-based identity-based encryption (IBE) and hierarchical identity-based encryption (HIBE). IBE removes the need for certificate management, as a user's public key depends on their public identity. IBE is currently used in vital applications such as emergency services communication and so the development of a high-performance quantum-safe alternative is imperative. This thesis also introduces the first scalable HIBE scheme based on lattices. The first HIBE scheme based on structured lattices, Latte, was proposed by the National Centre for Cyber Security (NCSC) in 2017. However, the public key and ciphertext sizes increased with each delegation and hence it was not feasible to scale the algorithm. Skinny Latte, proposed in this thesis, remedies this issue by fixing the dimension of the lattice, thereby making public key and ciphertext sizes constant. This research also shows that it is practical for real-world deployment. Overall, this thesis demonstrates that lattice-based cryptography is practical for real-world applications. It considers both theoretical and physical attacks, and presents novel designs of advanced quantum-safe cryptographic primitives, which have only yet been realised by lattices.
Quantum computers are moving closer to reality, and with that comes a serious concern for today's public-key cryptography. Many of the encryption and digital signature systems we rely on now, such as RSA and ECC, may no longer be secure in the future. Because of this, researchers are actively looking for new methods that can protect digital communication in the post-quantum era. One of the most promising directions is lattice-based cryptography. This paper gives a simple and focused review of lattice-based signature schemes. It brings together the main ideas from the existing literature and explains how these schemes are built, why they are considered secure, and what makes them practical. The review mainly discusses schemes based on hard lattice problems such as SIS and LWE. To make the comparison clearer, a table is also included that compares different signature schemes in terms of key size, signature size, security level, and computational efficiency. Overall, this study shows why lattice-based signature schemes are becoming an important part of modern cryptographic research and why they may play a major role in securing digital systems against future quantum threats.
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.
The landscape of modern cryptography is fundamentally challenged by the advent of quantum computing. Current public-key cryptosystems, which form the bedrock of secure digital communication, rely on the computational hardness of problems such as integer factorization (RSA) and the discrete logarithm problem (ECC). However, Shor's algorithm, if implemented on a sufficiently powerful quantum computer, can efficiently break these schemes, rendering them insecure. This paper explores the critical transition from these classical number theory problems to lattice-based cryptography, presenting a comprehensive analysis of the motivations, theoretical underpinnings, and practical implications for forging post-quantum cryptographic security. We delve into the mathematical foundations of lattice problems, such as the Shortest Vector Problem (SVP) and Learning With Errors (LWE), which are believed to resist known quantum algorithms. Through a thorough literature review, we trace the evolution of cryptographic thought, detailing the vulnerabilities of pre-quantum schemes and the emergence of lattice-based constructions as leading candidates for post-quantum standardization. The methodology outlines a comparative theoretical analysis of security, efficiency, and robustness against both classical and quantum attacks. Results demonstrate the compelling advantages of lattice-based schemes in terms of provable security reductions and resistance to quantum threats, albeit with considerations for increased key and ciphertext sizes. The discussion highlights the challenges and opportunities in the deployment and standardization of these new cryptographic primitives, emphasizing their critical role in securing future digital infrastructures. This work concludes that lattice-based cryptography offers a robust and theoretically sound pathway to establishing enduring security in a quantum-threatened world.