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.
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 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.
Classical cryptography has been around for a long time in the documented human history, but most classical ciphers were broken and even solved by hand. Shannon introduced the notion of perfect secrecy that formally defines confidentiality in the information-theoretic sense, which is only possible in the restricted scenarios where the message is no longer than the encryption key. The invention of public-key cryptography (the Diffie-Hellman key exchange protocol in 1976 and the RSA crypto-system in 1977) marks the birth of modern cryptography, allowing parties to exchange messages securely without sharing any secrets in advance. Furthermore, it provides computational security based on the conjectured hardness of mathematical problems such as factorization and the discrete logarithm. Public-key cryptography has found numerous applications in the Internet, financial and banking industry, and blockchains, and it plays a crucial role in protecting information security and asset safety. Unfortunately, in the 1990s, Shor proposed efficient quantum algorithms that solve number-theoretic problems, including factorization and discrete logarithms in polynomial time. Once a quantum computer of a particular scale becomes a reality, it will cause a devastating blow to the existing public-key infrastructure. To deal with such a ‘quantum crisis’, academia and industry are looking into the design, analysis and standardization of cryptographic algorithms that can resist quantum computers referred to as post-quantum cryptography (PQC). The National Institute of Standards and Technology (NIST) has been soliciting proposals for the post-quantum public-key algorithms since 2016. More recently, the Chinese Association for Cryptologic Research (CACR) held a competition on designing cryptographic algorithms whose public-key cryptography track focused on post-quantum cryptographic algorithms. Lattice-based cryptography is considered by most to be the mainstream technical route of post-quantum cryptography, which is reflected in the number of proposals (and their percentage of the total) received in the NIST PQC process. To reflect the status quo of post-quantum cryptography, we invite leading experts in this area to contribute three technical perspectives that aim to help readers understand the algorithms, the underlying basic techniques and different technical routes to achieve quantum resistance. The first perspective, presented by Lu and Zhang, introduces public-key cryptographic algorithms whose quantum security is reducible from the conjectured quantum hardness of lattice problems. In particular, they mainly focus on public-key encryption (PKE) and the key encapsulation mechanism (KEM), which are essential building blocks for securing the confidentiality of communication without pre-shared secrets. Both types of crypto-systems are solicited by the NIST PQC standardization and the CACR algorithm design competition. This perspective gives a comprehensive survey on practical lattice-based PKEs/KEMs, and their best-known quantum and classical attacks. Another important post-quantum crypto-system is digital signature, which ensures that three goals of information security are met other than confidentiality, namely, integrity, authentication and non-repudiation. The second perspective is on lattice-based signature by Lyubashevsky. In this perspective, he surveys different techniques in building lattice-based post-quantum crypto-systems, discusses the challenges in overcoming performance issues and gives us state-of-the-art digital signature schemes. In addition to ensuring the ‘static’ security of information in storage and transmission, advanced cryptographic algorithms and protocols can guarantee information security during the computation process (possibly among multiple parties), referred to as privacy-preserving computation. Cryptographic techniques involved in privacy-preserving computation include secure multi-party computation, zero-knowledge proof and fully homomorphic encryption. There is a pressing need to migrate them to the post-quantum era. The third perspective, by Yu and Xie, presents practical instantiations of these algorithms and discusses possible ways to migrate them to their quantum-resistant counterparts. To summarize, post-quantum cryptography has received widespread attention and made significant progress in recent years. Some post-quantum cryptographic algorithms, such as the lattice-based candidate, also have other advantages (e.g., computational efficiency and full homomorphism) over their classical counterparts. Lattice-based cryptography is an emerging field with high theoretical value and wide application, and we encourage young researchers to enter and explore this new and exciting field.
Lattice cryptography has become one of the focal points in the era of quantum computing development. RSA and ECC, traditional public key cryptosystems, may become insecure in the face of quantum computers. In contrast, lattice cryptography is considered a potential solution for cryptographic security in the quantum computing age due to its inherent mathematical problems that require the use of quantum computers to solve. Moreover, lattice cryptographic algorithms can achieve efficient encryption and decryption processes and support a variety of cryptographic constructions, including encryption, signatures, and fully homomorphic encryption (FHE). With its high efficiency, multifunctionality, and high security, lattice cryptography has applications in various fields such as finance, e-commerce, government agencies, military, and network communications. It has also become one of the top contenders for the post-quantum cryptographic algorithm standards that have been recognized by the National Institute of Standards and Technology (NIST). This paper discusses the main contributions of lattice cryptography to society and its potential future development directions, as well as the challenges it may face and potential solutions. This thesis elaborates on lattice-based cryptography and comprehensively discusses the key technologies of lattice cryptography, its applications, security analysis, performance evaluation, and the latest progress.
The security of most widely used public-key cryptography is fundamentally based on two computationally intractable problems: the integer factorization problem and the elliptic-curve discrete logarithm problem. However, these problems can be solved easily in polynomial time with the help of large-scale quantum computers using Shor's, Proos and Zalka's algorithm. Post-quantum cryptography provides schemes based on hard problems that are hard-to-solve not only by adversaries with classical computers but also by adversaries with large-scale quantum computers. Lattice-based cryptography is a branch of post-quantum cryptography consisting of schemes based on hard lattice problems. The National Institute of Standards and Technology (NIST) recently published the first set of standard post-quantum schemes. Kyber and HQC are the standard key-encapsulation mechanism/public-key encryption schemes, whereas Dilithium, Sphincs+, and Falcon are the standard digital signature algorithms. Although NIST's selection of the first set of post-quantum cryptographic standards is one of the most significant steps toward the transition from classical public-key cryptography to post-quantum cryptography, the field of post-quantum cryptography is still in a nascent stage compared to the decade-old classical public-key cryptography, such as RSA or ECDSA. Therefore, a major focus of this thesis is to bridge the gap between the theory and practice of post-quantum cryptography by exploring various problems that arise during the real-world deployment of post-quantum cryptography. Specifically, I focus on improving the practicality of lattice-based cryptography by proposing new efficient schemes, designing lightweight post-quantum schemes suitable for resource-constrained devices, efficient implementations, analyzing practical physical attacks on implementations of the post-quantum schemes, and designing their countermeasures to thwart the attacks. The first area of research of this dissertation is the exploration of various design choices for lattice-based key-encapsulation mechanisms to make them suitable in different environments under various operational constraints such as memory, silicon area, execution time, power requirement, etc. In our first contribution, we have explored various design choices for lattice-based key-encapsulation mechanisms, focusing on improving execution time on various hardware and software platforms. Our first design, Scabbard, is a suite of three key-encapsulation mechanisms that improved the state-of-the-art post-quantum key-encapsulation mechanism designs by reducing execution time, stack memory requirements, and/or area footprint. In our second contribution, we performed another design space exploration based on hardware resources (such as block RAM, distributed RAM, look-up tables, etc.) estimation and proposed the lattice-based key-encapsulation mechanism, Rudraksh, for resource-constrained devices. We also substantiate our claim of its usefulness with real-world implementations on an FPGA. The second area of research of this dissertation is the analysis of physical attacks. This attack analysis is essential when the attacker can access a device that executes cryptographic implementations, and such scenarios occur frequently in real-world deployments. Therefore, this is a crucial problem to address before deploying post-quantum cryptographic schemes in real-world applications, and countermeasures against physical attacks need to be developed as a prevention measure. In our third contribution, we proposed side-channel attack-resistant masked implementations of lattice-based KEM, Saber KEM, one of the NIST finalist KEMs. We showed that masked Saber outperforms the state-of-the-art masked implementations of Kyber, one of the NIST standards. Our investigations show that this is largely due to power-of-two moduli. Our final contribution to this thesis is physical attack analyses on implementations of the standard key-encapsulation mechanism Kyber. We proposed a cross-attack, fault-injection attack on the masked implementation of Kyber. We showed that the exploited vulnerability was introduced due to the algorithmic change caused by masking.
Background: The imminent threat posed by cryptographically relevant quantum computers to classical public-key infrastructure specifically RSA and Elliptic-Curve Cryptography (ECC), whose security rests on the conjectured computational intractability of integer factorisation and the discrete logarithm problem respectively has propelled lattice-based cryptography to the centre of global post-quantum standardisation efforts. On 13 August 2024, the United States National Institute of Standards and Technology (NIST) published three landmark Federal Information Processing Standards (FIPS): FIPS 203 (ML-KEM, derived from CRYSTALS-Kyber), FIPS 204 (ML-DSA, derived from CRYSTALS-Dilithium), and FIPS 205 (SLH-DSA, derived from SPHINCS+), with FIPS 206 (FN-DSA, derived from FALCON) in advanced draft. The first three of these standards rest on algebraic structures intimately connected to classical number theory: polynomial rings over integer quotients, cyclotomic fields, and the algebraic geometry of ideal lattices in rings of integers of number fields. Objectives: This article provides: (1) a rigorous mathematical exposition of the lattice problems underpinning NIST’s post-quantum standards, specifically the Learning With Errors (LWE), Ring-LWE (RLWE), Module-LWE (MLWE), Short Integer Solution (SIS), and NTRU problems, and their connections to algebraic number theory; (2) a comparative performance analysis of NIST-standardised lattice-based algorithms against classical RSA and ECC benchmarks; (3) a security analysis examining known classical and quantum attacks on each hard problem; (4) a comparative evaluation of the four NIST-selected algorithms across key size, signature size, and computational benchmarks; and (5) a strategic assessment of the migration challenges facing deployed cryptographic infrastructure. Methods: The study synthesises peer-reviewed literature, NIST official standards documentation (FIPS 203, 204, 205, and draft FIPS 206), and independently published performance benchmarks published between June 2024 and June 2026. Mathematical security analysis is grounded in the worst-case to average-case reductions established by Regev (2005) for LWE and by Lyubashevsky, Peikert, and Regev (2013) [11, 18] for Ring-LWE. Performance data are drawn from Garani (2024) [8], the ARM Cortex-M0+ benchmarking study of Ratnayaka and Fischer (2026) [4], and the cross-platform evaluation by Alzahrani et al. (2025) [2]. Results: NIST’s three August 2024 standards establish a comprehensive lattice-based post-quantum portfolio. ML-KEM-768 produces a 1,184-byte public key and 1,088-byte ciphertext, achieving IND-CCA2 security under the MLWE assumption at NIST Level 3 (AES-192 equivalent). ML-DSA-65 produces 1,952-byte public keys and 3,309-byte signatures under the Module-LWE and Module-SIS assumptions at Level 3. FN-DSA-512 (FALCON, draft FIPS 206) produces 897-byte public keys and 666-byte signatures under the NTRU assumption, offering the most compact lattice-based signatures. Performance benchmarks on an Intel Core i7-12700K (3.6 GHz) confirm that ML-KEM key generation is orders of magnitude faster than RSA-3072 key generation. The algebraic structure of cyclotomic polynomial rings ∑₂ⁿ = Z[x]/(x^n + 1) is central to the efficiency of all three lattice-based NIST standards. Conclusion: Lattice-based cryptography, grounded in the algebraic number theory of ideal lattices over cyclotomic fields, provides the most comprehensive and mathematically well-founded response to the quantum computational threat. The August 2024 NIST standardisation of ML-KEM, ML-DSA, and SLH-DSA represents a landmark in cryptographic history, and the imminent finalisation of FN-DSA will complete the post-quantum toolbox. Organisations should prioritise immediate migration planning, leveraging hybrid classical-quantum schemes during transition, with full transition to NIST post-quantum standards recommended by 2030 per NSA and CISA guidance.
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.