The standard public-key cryptosystems used today relies mathematical problems that require a lot of computing force to solve, so much that, with the right parameters, they are computationally unsolvable. But there are quantum algorithms that are able to solve these problems in much shorter time. These quantum algorithms have been known for many years, but have only been a problem in theory because of the lack of quantum computers. But with recent development in the building of quantum computers, the cryptographic world is looking for quantum-resistant replacements for today’s standard public-key cryptosystems. Public-key cryptosystems based on lattices are possible replacements. This thesis presents several possible candidates for new standard public-key cryptosystems, mainly NTRU and ring-LWE-based systems. The latticebased cryptosystems are shown to be very fast and have strong, provable security against quantum computers, but are a lot more complicated than RSA and Diffie-Hellman.
The standard public-key cryptosystems used today relies mathematical problems that require a lot of computing force to solve, so much that, with the right parameters, they are computationally unsolvable. But there are quantum algorithms that are able to solve these problems in much shorter time. These quantum algorithms have been known for many years, but have only been a problem in theory because of the lack of quantum computers. But with recent development in the building of quantum computers, the cryptographic world is looking for quantum-resistant replacements for today’s standard public-key cryptosystems. Public-key cryptosystems based on lattices are possible replacements. This thesis presents several possible candidates for new standard public-key cryptosystems, mainly NTRU and ring-LWE-based systems. The latticebased cryptosystems are shown to be very fast and have strong, provable security against quantum computers, but are a lot more complicated than RSA and Diffie-Hellman.
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.
Lattice-Based Cryptosystems and Quantum CryptanalysisQuantum computers are probably coming, though we don't know when-and when they arrive, they will, most likely, be able to break our standard public-key cryptography algorithms.In anticipation of this possibility, cryptographers have been working on quantum-resistant public-key algorithms.The National Institute for Standards and Technology (NIST) has been hosting a competition a since 2017, and there already are several proposed standards.b Most of these are based on lattice problems.The mathematics of lattice cryptography revolve around combining sets of vectors-that's the lattice-in a multi-dimensional space.These lattices are filled with multi-dimensional periodicities.The hard problem c that's used in cryptography is to find the shortest periodicity in a large, random-looking lattice.This can be turned into d a public-key cryptosystem in a variety of different ways.Research has been ongoing since 1996, and there has been some really great work since then-including many practical public-key algorithms.On April 10, Yilei Chen from Tsinghua University in Beijing posted a paper describing a new quantum attack on that shortest-path lattice problem.It's a very dense mathematical paper-63 pages long-and my guess is that only a few cryptographers are able to understand all of its details.(I was not one of them.)But the conclusion was pretty devastating, breaking essentially all of the lattice-based fully homomorphic encryption schemes and coming significantly closer to attacks against the recently proposed (and NIST-approved) lattice key-exchange and signature schemes.However, there was a small but critical mistake in the paper, on the bottom of page 37.It was independently discovered by Hongxun Wu from Berkeley and Thomas Vidick from the Weizmann Institute in Israel eight days later.The attack algorithm in its current form doesn't work.This was discussed last week at the Cryptographers' Panel e at the RSA Conference.Adi Shamir, the "S" in RSA and a 2002 recipient of ACM's A.M. Turing award, described the result as psychologically significant because it shows that there is still a lot to be discovered about quantum
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.
Among the different cryptosystems, the Public Key Cryptosystems (PKCS) are of great usage and are used in many applications. Most of the current PKCS are based on a hard problem making the cryptanalysis of such cipher infeasible given the current computing and memory availability. However, Quantum Computing threatens all the current PKCS as they offer a new model that can solve those hard problems, e.g. the factorization problem of RSA or the discrete logarithm problem of ELGAMAL algorithm. Lattice Based PKCS are a promising filed to introduce an immune cipher system against quantum cryptanalysis. This paper presents a summary of recent progress in the field of lattice-based cryptography, by focusing on the recent advancement in lattice-based public key cryptosystems and key exchange mechanisms based on the learning with errors (LWE) problem and its ring variant Ring-LWE.
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 use of public key cryptosystems range from securely encrypting emails and files to creating digital signatures for non-repudiation. The security of public key cryptosystems is based on computationally "unsolvable" complex mathematical problems. This tends to change with the introduction of quantum computers that undoubtedly pose a threat to the current schemes. In response to that extensive research has been conducted that resulted in several cryptosystems that are believed to be quantum resistant. This thesis presents a concise overview of multiple hash-based signature schemes and provides a comparative description and analysis of them. The comparisons are based on different signature scheme properties, such as key sizes, signature sizes and security level provided. The proposed quantum resistant schemes are also compared to the standard schemes used today, such as RSA and ECDSA.