Abstract Almost all practically relevant asymmetric cryptosystems like RSA or ECC are either based on the hardness of factoring or on the hardness of the discrete logarithm problem. However, both problems could be solved efficiently on a large enough quantum computer. While quantum computers powerful enough to break currently used parameter sets are not available yet, they are heavily researched and expected to reach maturity in 15 to 20 years. As a consequence, research on alternative quantum-safe cryptosystems is required. One alternative is lattice-based cryptography which allows the construction of asymmetric public-key encryption and signature schemes that offer a good balance between security, performance, and key as well as ciphertext sizes.
Abstract Almost all practically relevant asymmetric cryptosystems like RSA or ECC are either based on the hardness of factoring or on the hardness of the discrete logarithm problem. However, both problems could be solved efficiently on a large enough quantum computer. While quantum computers powerful enough to break currently used parameter sets are not available yet, they are heavily researched and expected to reach maturity in 15 to 20 years. As a consequence, research on alternative quantum-safe cryptosystems is required. One alternative is lattice-based cryptography which allows the construction of asymmetric public-key encryption and signature schemes that offer a good balance between security, performance, and key as well as ciphertext sizes.
The invention of public-key cryptography (PKC) by Diffie and Hellman in 1976 is one of two milestones marking the beginning of modern cryptography. The security of a PKC system requires that it should be infeasible to compute the private key from a given public key, which in turn is typically guaranteed by the difficulty in solving some cryptographic-friendly mathematical problems. Among those problems, the integer factorization and discrete logarithm problems play pivotal roles in the development of public-key cryptography. In particular, the assumption that there is no polynomial time (classical) algorithm that solves the above two problems constitutes the basis for the security of almost all currently used public-key cryptosystems, such as RSA and ElGamal. However, Shor [1] found an efficient quantum solving algorithm for the integer factorization and discrete logarithm problems in 1994, which would destroy the security basis for most real deployed PKC systems if large-scale quantum computers become available. The rapid development of quantum technology in recent years suggests that we are getting closer to the quantum crisis of current PKC systems. As a response to the quantum crisis, the research community has made many efforts to post-quantum cryptography (PQC) that are believed to resist quantum computer attacks. Lattice-based cryptography is one of the main directions in this area, and has become the most promising PQC candidate for standardization. The research of lattice-based cryptography dates back to the seminal work of Ajtai [2], which first based the security of cryptographic primitives on the difficulty of solving some lattice problems such as the approximate shortest vector problem and the closest vector problem. After more than two decades of development, lattice-based cryptography has gained substantial progress. In theory, we have witnessed the construction of many powerful cryptographic primitives that were not known before. In practice, the public key size of lattice-based cryptosystems has been significantly reduced from several gigabytes to a few kilobytes. For current applications and standardization, key exchanges, public-key encryptions (PKEs) and signatures are the most desired lattice-based cryptosystems, where the first two are often used to ensure information secrecy, while the last provides information authentication. Note that public-key encryptions are equivalent to two-round key exchanges, also known as the key encapsulation mechanism (KEM). In the following, we focus on lattice-based PKEs/KEMs. The design principle of lattice-based PKEs/KEMs follows two approaches: a trapdoor one-way function and an approximate commutative one-way function. In the first approach, a trapdoor one-way function f and its trapdoor f−1 are generated as the public key and private key. A plaintext m is encrypted as c = f(m), and the ciphertext is decrypted as m = f−1(c). The NTRU scheme and its variants follow such an approach. In the second approach, an approximate commutative function fs and a random input a are generated, the public key is (a, b = fs(a)) and the private key is s. A plaintext m is encrypted as c1 = gr(a), c2 = gr(b) + E(m), where r is a random element, g is an approximate commutative one-way function and E is the encoding of an error-correction code. The ciphertext (c1, c2) is decrypted as m = D(c2 − fs(c1)), where D is the decoding of an error-correction code. The correctness of decryption is guaranteed by the approximate commutative property (gr(b) = gr(fs(a)) ≈ fs(gr(a)) = fs(c1)) and the error-correction code. Learning with errors (LWE) problem-based PKE/KEM schemes and their variants follow such an approach. The standardization of PQC has received substantial support from national funding agencies, such as the European Union projects PQCrypto and SAFEcrypto. The USA National Institute of Standard and Technology (NIST) started the post-quantum standardization project in 2012, organized a worldwide ‘competition’ in 2016 and plans to deliver draft standards before 2024. After two rounds of evaluation, seven schemes were accepted as the round-three candidates on 22 July 2020, of which five are lattice-based schemes. In 2017, the International organization for standardization started a study project of post-quantum cryptography named SD8. Most LWE-based PKE schemes such as Kyber and LAC follow the Lindner-Peikert framework [3] up to the choices of ring structure, noise distribution and parameters. As the size of noise in lattice-based PKEs/EKMs is typically larger than the lower bits of the ciphertext, many schemes often artificially drop a few lower bits to optimize the practical performance without significantly increasing the final decryption noise. Kyber [4] is one of the most promising PKE/KEM candidates in the NIST PQC standardization, whose security is provably based on the difficulty of so-called module LWE (MLWE) problems. The use of MLWE allowed Kyber to obtain additional flexibility and security advantages, while keeping the same efficiency as those based on the ring-LWE problems. The strategy of dropping some lower bits is used to compress both the public-key and ciphertext sizes. For a targeted 128-bit quantum security, the public-key and ciphertext sizes of Kyber is around a single kilobyte. LAC [5] uses several techniques to reduce the modulus as small as possible: it uses a byte-level modulus, embeds powerful error-correcting codes to maximize the noise-modulus rate, provides a different style of modulus to avoid potential attacks for special polynomial ring structures and optimizes the polynomial multiplication algorithm of the bit-level secret and noise. Based on these techniques, LAC reduces the public key to 544–1056 bytes and the ciphertext to 664–1464 bytes. Meanwhile, it achieves similar computational performance compared with NTT technique schemes. By observing the asymmetries in lattice-based cryptosystems, Zhang and Yu et al. [6] proposed asymmetric MLWE and asymmetric MSIS problems, which yield further size-optimized KEMs and signature schemes to those from standard counterparts. Compared to the seven NIST round-three candidates at Category III security, their KEM scheme has parameters (public key + ciphertext size) smaller than Classic McEliece, CRYSTALS-Kyber, NTRU and Saber; their signature scheme has parameters (public key + signature size) smaller than CRYSTALS-Dilithium and Rainbow, but slightly larger than FALCON, where CRYSTALS-Kyber, NTRU, Saber, CRYSTALS-Dilithium and FALCON are lattice-based schemes. One important application of lattice-based PKEs/KEMs is to build authenticated key exchange (AKE), which could provide additional authentication to the established session key. There are several generic ways to construct AKE from lattice-based PKEs/KEMs. In the PKE setting, Xue and Lu et al. [7] proposed a more compact KEM-based framework via a new primitive named ‘2-key KEM’, which shares some item between different ciphertexts. In the only password setting, Zhang and Yu [8] presented a two-round PAKE framework from the splittable-PKEs that can be instantiated from lattices. The only known AKE that does not rely on lattice-based PKEs/KEMs was given in Ref. [9], which has two-round messages and provides implicit authentication. This work was supported by the National Natural Science Foundation of China (6197239 to X.L.; 62022018 and 61932019 to J.Z.) and the National Key Research and Development Program of China (2018YFB0804105 to J.Z.). Conflict of interest statement. None declared.
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.
The advent of quantum computing poses a significant threat to the security foundations of current asymmetric cryptographic schemes, which primarily rely on the perceived difficulty of integer factorization and discrete logarithm problems. Shor's algorithm, in particular, demonstrates that a sufficiently powerful quantum computer could break these schemes efficiently, necessitating the development of quantum-resistant alternatives. This paper explores the construction of quantum-secure primitives utilizing ideal lattices, a specialized class of lattices that offer enhanced efficiency and structural advantages compared to general lattices. We delve into the theoretical underpinnings of ideal lattices, including the Ring Learning With Errors (Ring-LWE) problem and the NTRU problem, which are believed to be hard even for quantum computers. The paper reviews the evolution of lattice-based cryptography, analyzes the security reductions from worst-case lattice problems to average-case problem instances relevant for cryptographic constructions, and discusses the practical implications for key encapsulation mechanisms and digital signatures. We examine the current state of ideal lattice-based schemes, such as those standardized by NIST, and consider their performance characteristics, key sizes, and resistance to known attacks, including side-channel vulnerabilities. Our analysis highlights that ideal lattices provide a robust and efficient foundation for building the next generation of asymmetric cryptographic primitives, moving beyond the vulnerabilities inherent in factoring-based systems.
Digital signatures are an important primitive for building secure systems and are used in most real-world security protocols. However, almost all popular signature schemes are either based on the factoring assumption (RSA) or the hardness of the discrete logarithm problem (DSA/ECDSA). In the case of classical cryptanalytic advances or progress on the development of quantum computers, the hardness of these closely related problems might be seriously weakened. A potential alternative approach is the construction of signature schemes based on the hardness of certain lattice problems that are assumed to be intractable by quantum computers. Due to significant research advancements in recent years, lattice-based schemes have now become practical and appear to be a very viable alternative to number-theoretic cryptography. In this article, we focus on recent developments and the current state of the art in lattice-based digital signatures and provide a comprehensive survey discussing signature schemes with respect to practicality. Additionally, we discuss future research areas that are essential for the continued development of lattice-based cryptography.
The imminent threat of quantum computing poses a significant challenge to the security of current public-key cryptographic systems, most notably RSA. These classical algorithms rely on mathematical problems, such as integer factorization and discrete logarithms, which are efficiently solvable by Shor's algorithm on a sufficiently powerful quantum computer. This paper explores ideal lattices as a robust post-quantum foundation for asymmetric cryptography, offering a compelling alternative to traditional schemes. We delve into the mathematical underpinnings of ideal lattices, including the Ring Learning With Errors (RLWE) and Shortest Vector Problem (SVP), which are conjectured to be hard even for quantum computers. The advantages of ideal lattice-based cryptography, such as its quantum resistance, efficiency, and versatility in constructing various cryptographic primitives, are thoroughly discussed. We examine prominent examples like NTRU and CRYSTALS-Kyber, highlighting their design principles and performance characteristics. Furthermore, the paper addresses the ongoing standardization efforts by NIST and the practical considerations for migrating to lattice-based schemes. The objective is to present a comprehensive analysis demonstrating why ideal lattices are a leading candidate for securing digital communications in the quantum era, providing a secure and efficient pathway beyond the limitations of RSA.
The advent of quantum computing poses a significant threat to the security of current asymmetric cryptographic systems, which underpin much of modern digital communication and security. These systems, predominantly RSA and Elliptic Curve Cryptography (ECC), rely on the computational hardness of mathematical problems such as integer factorization and the discrete logarithm problem. Shor's algorithm, a quantum algorithm, demonstrates the ability to efficiently solve these problems, rendering classical public-key cryptography vulnerable to attacks by sufficiently powerful quantum computers. This paper argues for and thoroughly examines the strategic imperative of transitioning from these classical cryptographic foundations to a new paradigm based on lattices, which are believed to be resistant to quantum attacks. We delve into the fundamental mathematical problems underlying lattice-based cryptography, such as the Shortest Vector Problem (SVP) and the Learning With Errors (LWE) problem, whose worst-case hardness is leveraged to achieve cryptographic security. A comprehensive literature review is provided, tracing the evolution of quantum threats and the emergence of lattice-based schemes. The methodology details the construction principles of prominent lattice-based cryptosystems. Results demonstrate their theoretical security against quantum adversaries and highlight their practical attributes, including compact key sizes and competitive performance. The discussion section contextualizes lattice-based cryptography within the broader landscape of post-quantum candidates, examining their strengths, weaknesses, and the ongoing standardization efforts by organizations like NIST. We conclude that lattice-based cryptography offers a robust and promising foundation for building resilient asymmetric cryptographic systems in the post-quantum era, ensuring the long-term security of digital information through a necessary re-architecture of cryptographic primitives.