This thesis is about lattices. Much of the cryptography that is being used today, can be broken by (large) quantum computers in the future! There are multiple computational problems involving lattices that are easy in dimension 2 or 3 but are hard in high dimensions. These problems are, as far as we know, difficult for both classical computers and quantum computers. Therefore, we can use lattices to build so-called post-quantum cryptography, which will remain secure even when large quantum computers are built. A goal of cryptography is to make secure communication between two or more parties possible. There are two important cryptographic protocols: encryption and signature schemes. Encryption makes the content of messages incomprehensible for eavesdroppers. A signature scheme enables one to verify whether a message was really sent by some party. The two parties hold different keys in a signature scheme, just like in the real world: one party writes signatures with a special pen, while the other knows the precise colour composition of the ink in the pen. Encryption is similar: everyone can encrypt a message using a public key, while deciphering is only possible for one owning the private key. Lattices can be used to generate such a public/private key pair. The private key is a description of the lattice, that consists of the shortest lattice points. This key is private because it is difficult in high dimensions, to even compute a somewhat short lattice point. The public key is an arbitrary description of the lattice, which usually consists of long lattice points. The fastest algorithm that upon input a public key, computes the private key associated to it, requires time and memory that grows exponentially as a function of the dimension. Part II concerns the dual attack. This is an algorithm that, upon input a description of a lattice and a point, outputs the lattice point that is the closest to the point while making use of the dual lattice. Every dual lattice point corresponds with a wave function (in fact, character) that is maximal at every lattice point. Using this wave function, one can decide whether a point is close to the lattice or not. By subdividing the lattice like a chess board into a black sublattice and a white coset, you can determine whether the black sublattice is closer to the point than the white coset. If this method is repeatedly sufficiently many times, one can determine which lattice point is closest to the point. Chapter 3 shows that an assumption that was used in literature to analyse the so-called dual-sieve attack is incorrect, because it produces contradictions in multiple theoretic regimes, and experiments show that it leads to wrong predictions. Chapter 4 contains an alternative assumption for the dual-sieve attack. This assumption leads to accurate predictions for multiple important probability distributions of points. Part III concerns the lattice isomorphism problem (LIP). Special lattices with good properties are convenient when building a signature scheme, because they make a signature scheme very efficient. Because every cryptology researcher knows a good description of such a lattice, the lattice has to be hidden differently. Using LIP we can hide the lattice by randomly rotating it. The specific rotation now becomes the private key. Chapter 5 is dedicated to the construction of the signature scheme Hawk, which is based on LIP. To find the private key of Hawk, one needs to solve smLIP, a module variant of LIP for the simple lattice Z^n, the lattice consisting of all integer vectors. Security of Hawk is based on the new one more shortest vector problem (omSVP). In Chapter 6 we study automorphisms of the module lattice: a rotation that maps the lattice to itself. Theorem 6.2 states that, using a nontrivial automorphism, it becomes much easier to find a short vector, and to solve smLIP. An automorphism sends a short lattice point to a (possibly different) short lattice point, and therefore may easily solve omSVP. If smLIP is a difficult computational problem, then it will be difficult to find a nontrivial automorphism, and thus, it will be difficult to solve omSVP by ‘just’ finding a nontrivial automorphism.
This thesis is about lattices. Much of the cryptography that is being used today, can be broken by (large) quantum computers in the future! There are multiple computational problems involving lattices that are easy in dimension 2 or 3 but are hard in high dimensions. These problems are, as far as we know, difficult for both classical computers and quantum computers. Therefore, we can use lattices to build so-called post-quantum cryptography, which will remain secure even when large quantum computers are built. A goal of cryptography is to make secure communication between two or more parties possible. There are two important cryptographic protocols: encryption and signature schemes. Encryption makes the content of messages incomprehensible for eavesdroppers. A signature scheme enables one to verify whether a message was really sent by some party. The two parties hold different keys in a signature scheme, just like in the real world: one party writes signatures with a special pen, while the other knows the precise colour composition of the ink in the pen. Encryption is similar: everyone can encrypt a message using a public key, while deciphering is only possible for one owning the private key. Lattices can be used to generate such a public/private key pair. The private key is a description of the lattice, that consists of the shortest lattice points. This key is private because it is difficult in high dimensions, to even compute a somewhat short lattice point. The public key is an arbitrary description of the lattice, which usually consists of long lattice points. The fastest algorithm that upon input a public key, computes the private key associated to it, requires time and memory that grows exponentially as a function of the dimension. Part II concerns the dual attack. This is an algorithm that, upon input a description of a lattice and a point, outputs the lattice point that is the closest to the point while making use of the dual lattice. Every dual lattice point corresponds with a wave function (in fact, character) that is maximal at every lattice point. Using this wave function, one can decide whether a point is close to the lattice or not. By subdividing the lattice like a chess board into a black sublattice and a white coset, you can determine whether the black sublattice is closer to the point than the white coset. If this method is repeatedly sufficiently many times, one can determine which lattice point is closest to the point. Chapter 3 shows that an assumption that was used in literature to analyse the so-called dual-sieve attack is incorrect, because it produces contradictions in multiple theoretic regimes, and experiments show that it leads to wrong predictions. Chapter 4 contains an alternative assumption for the dual-sieve attack. This assumption leads to accurate predictions for multiple important probability distributions of points. Part III concerns the lattice isomorphism problem (LIP). Special lattices with good properties are convenient when building a signature scheme, because they make a signature scheme very efficient. Because every cryptology researcher knows a good description of such a lattice, the lattice has to be hidden differently. Using LIP we can hide the lattice by randomly rotating it. The specific rotation now becomes the private key. Chapter 5 is dedicated to the construction of the signature scheme Hawk, which is based on LIP. To find the private key of Hawk, one needs to solve smLIP, a module variant of LIP for the simple lattice Z^n, the lattice consisting of all integer vectors. Security of Hawk is based on the new one more shortest vector problem (omSVP). In Chapter 6 we study automorphisms of the module lattice: a rotation that maps the lattice to itself. Theorem 6.2 states that, using a nontrivial automorphism, it becomes much easier to find a short vector, and to solve smLIP. An automorphism sends a short lattice point to a (possibly different) short lattice point, and therefore may easily solve omSVP. If smLIP is a difficult computational problem, then it will be difficult to find a nontrivial automorphism, and thus, it will be difficult to solve omSVP by ‘just’ finding a nontrivial automorphism.
Digital signatures and key exchange protocols are the two most important public key cryptographic primitives used in the electronic transmission of data. The goal of key exchange is to preserve the secrecy of the communication, while the goal of digital signatures is to guarantee the authenticity of the exchanged messages. Constructions of digital signature schemes based on classical mathematical assumptions appeared shortly following the invention of public key cryptography in the late 1970s. And just like with key exchange, the most efficient variants are based on number-theoretic problems that are believed to be (sub)-exponentially hard for classical machines, but are solved in polynomial time by Shor’s algorithm on a powerful-enough quantum computer. Also, like for key exchange, the most efficient constructions that we believe to be quantum safe are based on the presumed hardness of lattice problems over polynomial rings. One interesting difference between key exchange and digital signatures is that key exchange appears to inherently require that some mathematical problem be computationally hard. Digital signatures, on the other hand, can be generically constructed from any one-way function [1,2]. So even though they certainly fall into the category of public key primitives based on their usage, their existence requires much weaker assumptions. Additionally, the transformation from a one-way function to a digital signature is not too inefficient. For example, the total parameter size (public key + signature) of the SPHINCS+ scheme [3] is around 40 kB. While these sizes are larger, and signing times considerably longer, than those of signatures based on factoring or discrete log, it is still a usable scheme for many applications. And being only based on symmetric assumptions (e.g. one wayness and collision resistance of cryptographic hash functions), its security is very attractive. In order to be considered an interesting alternative to the above-mentioned signature, a scheme based on a mathematical assumption would need to have significant performance advantages. Schemes based on factoring and the discrete logarithm problem were significantly shorter and faster, and so the generic approach lay dormant for over four decades. The new quantum-safe schemes will need to have similar performance advantages if they are to be used in lieu of this safe approach. Below, we describe two techniques for constructing lattice-based digital signatures with output sizes being just a few kilobytes. On a very high level, lattice-based signature constructions follow the two known approaches for constructing classical signatures. In the first approach, the signer outputs a function f and an image y = f(x) as his public key and keeps x as his secret key. To sign a message μ, he gives a non-interactive zero-knowledge proof that he knows an x satisfying y = f(x), using the message μ to create the ‘challenge’ H(μ) for the proof (where H is a public function that maps μ to something ‘random looking’). If the function f is one way then the verifier should be convinced that the proof could have only been created by the entity who knows x. A classic example of this type of scheme is the Schnorr signature scheme [4] based on the hardness of the discrete logarithm problem. The second approach is to create a function f together with a trapdoor f−1, output f as the public key and keep f−1 as the secret key. A message μ is signed by using the secret trapdoor to create a pre-image x such that f(x) = H(μ). Again, if the function f is one way then only someone in possession of a trapdoor should be able to invert it. An example of such a construction based on a ‘factoring-like’ assumption is the RSA signature scheme [5]. The high-level ideas for lattice-based signatures follow the above blueprints, but the technical details are significantly more involved. The main reason for the complications is the different algebraic structure of the hard one-way function underlying lattice cryptography. While the domain of the function in discrete log and RSA-based one-way functions are groups, the domains in lattice-based signatures are sets that are not closed under any operation—in particular, they are elements in a group that have small norms. This crucial small norm requirement precludes us from using uniformly random masking as in Schnorr signatures or having a trapdoor for a bijective one-way function as in RSA signatures. These barriers have, nevertheless, been overcome and the resulting digital signatures are quite practical. In 2017, the US National Institute of Standards and Technology (NIST) began a ‘competition’ for a quantum-safe key exchange and digital signatures standard. At the time of this writing, this process is in the third round and there are two lattice-based signatures remaining—each following one of the above high-level designs. The CRYSTALS-Dilithium [6] scheme follows the Schnorr framework, but adds a crucial rejection-sampling step to keep the size of the coefficients small. The FALCON scheme [7] utilizes a randomized trapdoor sampling technique that uses a secret trapdoor for f−1 to produce random pre-images from a particular distribution. Because there is no longer a bijection, it is crucial to also have the property that the distribution of the outputted pre-images does not leak information about the trapdoor. Both schemes are relatively fast and their parameters (public key + signature size) are the shortest of all quantum-safe signature schemes. While both schemes are based on lattices, they have rather different characteristics. FALCON has very short parameters (see Table 1), but entails a rather complicated procedure for signature generation. In particular, it uses (an optimized version of) the GPV sampler [8], which requires floating-point arithmetic with approximately 64 bits of precision. Requiring such high precision means that subtle implementation errors may not get detected even with rigorous testing. Dilithium, on the other hand, has larger parameters but a very simple implementation where all the sampling in the signing is done in a power-of-2 range; it is thus much less prone to implementation errors. It is quite possible that in the future both schemes will be used for different applications. Approximate parameter sizes (in bytes) for the CRYSTALS-Dilithium and FALCON digital signature schemes at approximately 128-bit security levels. Approximate parameter sizes (in bytes) for the CRYSTALS-Dilithium and FALCON digital signature schemes at approximately 128-bit security levels. 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
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.
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 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 security of conventional public-key cryptography schemes is based on mathematical problems which are considered to be infeasible to solve by classical computers in a reasonable amount of time. However, the rise of quantum computers might break this security in the future. Post-quantum cryptography (PQC) aims to achieve secure schemes which are resistant against attacks assisted by quantum computers. Public-key cryptography refers to asymmetric cryptography in which encryption is done with a public key and decryption is done with a private key. Characteristic properties of public-key cryptography include the possibility to derive the private key from public information by solving some presumably hard problem. The hardness of the problem constitutes the basis for the system's security. In the post-quantum era, the security must be based on problems that are too hard to solve even for quantum computers. In this thesis, we will study lattice-based cryptography which is believed to serve as a good candidate for secure post-quantum public-key cryptography. Our main attention is in the problem of learning with errors, which is in the base of some lattice-based schemes and is linked to the hard problem of finding short vectors in a lattice.