This dissertation examines the NTRU cryptosystem, one of the earliest and most updated lattice-based public key cryptographic schemes. Presented in 1996 by Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman, NTRU was conceived as an alternative to classical cryptographic protocols such as the RSA cryptosystem and Diffie–Hellman systems, whose security is based upon the computational intractability of integer factorisation and discrete logarithm problems. Although these problems remain infeasible for classical computation, the coming of sufficiently powerful quantum computers would render such schemes helpless through the application of the already existing Shor’s algorithm. By contrast, NTRU derives its security from hard problems in lattice theory, for which no efficient quantum algorithms are currently known, thereby establishing it as one of the foremost candidates for secure communication in the post-quantum era. The first chapter begins with a rigorous introduction to the theory of lattices, displaying their main algebraic and geometric properties together with several fundamental computational problems, most notably the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). The computational hardness and infeasibility of these problems constitutes the mathematical foundation upon which NTRU is built. Particular attention is given to the Lenstra–Lenstra–Lovasz (LLL) lattice reduc- ´ tion algorithm. Its theoretical framework, geometric interpretation, and algorithmic behaviour are examined in detail, with special emphasis on its ability to construct reduced lattice bases that mirror some of the properties given by orthogonality, while remaining computationally feasible. The dissertation further explores the decisive role played by lattice reduction techniques in cryptography, both as practical tools for addressing difficult lattice problems and as powerful methods in the analysis of cryptosystems. Following this necessary theoretical development, in the second chapter the NTRU public key cryptosystem is presented and described in detail. The processes of key generation, encryption, and decryption are presented alongside the correct selection criteria of the system’s parameters, required to guarantee both correctness and security. Finally, the third chapter examines the security issues of NTRU through a range of attack models, including conventional attacks and, mainly, sophisticated attacks based on lattice reduction methods, thereby illustrating the deep connection between the security of NTRU and the intrinsic difficulty of solving lattice problems efficiently. Taken together, this dissertation presents a full guide of the mathematical structures underlying the NTRU cryptosystem, highlighting the fundamental role of algebraic tools such as lattice theory in the construction of cryptographic systems capable of withstanding the paradigm shift that is rapidly approaching with the rise of quantum computation.
This dissertation examines the NTRU cryptosystem, one of the earliest and most updated lattice-based public key cryptographic schemes. Presented in 1996 by Jeffrey Hoffstein, Jill Pipher and Joseph H. Silverman, NTRU was conceived as an alternative to classical cryptographic protocols such as the RSA cryptosystem and Diffie–Hellman systems, whose security is based upon the computational intractability of integer factorisation and discrete logarithm problems. Although these problems remain infeasible for classical computation, the coming of sufficiently powerful quantum computers would render such schemes helpless through the application of the already existing Shor’s algorithm. By contrast, NTRU derives its security from hard problems in lattice theory, for which no efficient quantum algorithms are currently known, thereby establishing it as one of the foremost candidates for secure communication in the post-quantum era. The first chapter begins with a rigorous introduction to the theory of lattices, displaying their main algebraic and geometric properties together with several fundamental computational problems, most notably the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP). The computational hardness and infeasibility of these problems constitutes the mathematical foundation upon which NTRU is built. Particular attention is given to the Lenstra–Lenstra–Lovasz (LLL) lattice reduc- ´ tion algorithm. Its theoretical framework, geometric interpretation, and algorithmic behaviour are examined in detail, with special emphasis on its ability to construct reduced lattice bases that mirror some of the properties given by orthogonality, while remaining computationally feasible. The dissertation further explores the decisive role played by lattice reduction techniques in cryptography, both as practical tools for addressing difficult lattice problems and as powerful methods in the analysis of cryptosystems. Following this necessary theoretical development, in the second chapter the NTRU public key cryptosystem is presented and described in detail. The processes of key generation, encryption, and decryption are presented alongside the correct selection criteria of the system’s parameters, required to guarantee both correctness and security. Finally, the third chapter examines the security issues of NTRU through a range of attack models, including conventional attacks and, mainly, sophisticated attacks based on lattice reduction methods, thereby illustrating the deep connection between the security of NTRU and the intrinsic difficulty of solving lattice problems efficiently. Taken together, this dissertation presents a full guide of the mathematical structures underlying the NTRU cryptosystem, highlighting the fundamental role of algebraic tools such as lattice theory in the construction of cryptographic systems capable of withstanding the paradigm shift that is rapidly approaching with the rise of quantum computation.
This chapter introduces lattice-based cryptography, a critical mathematical framework for securing communications in the post-quantum era. While classical public-key cryptosystems rely on the intractability of integer factorization and discrete logarithms, these foundations are fundamentally vulnerable to quantum computing threats, specifically Shor's algorithm. To address this vulnerability, the text explores cryptosystems built upon the algebraic structure of lattices, defined as discrete points in n-dimensional Euclidean space generated by linearly independent vectors. The chapter systematically covers the mathematical properties of lattices, associated computational problems, and distance metrics. It provides an in-depth examination of lattice basis reduction algorithms, which are fundamental to both the design and security evaluation of these systems. Furthermore, the chapter details the operational mechanics—including encryption, decryption, and cryptanalysis—of prominent post-quantum architectures, specifically the GGH and NTRU public-key cryptosystems. By transitioning from classical number theory to high-dimensional geometry, this chapter equips readers with the cryptographic primitives necessary to withstand future quantum attacks.
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.
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.
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 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.
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.