Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lattice-based Signature Schemes with Additional Features

Markus Rückert

Published Jan 1, 2011• 5 citations
Publisher

Abstract

Building cryptographic schemes upon as many fundamentally different hard problems as possible, seems to be the best way to hedge against future threats such as quantum computers. Being mainly based on the hardness of factoring and computing discrete logarithms, the present security landscape is at risk. In contrast, problems in lattices, such as finding short non-zero vectors, seem to withstand quantum computer attacks and the best known algorithms run in exponential time. In sharp contrast to other fields of cryptography, lattices admit a worst-case to average-case reduction (Ajtai 1996). Instead of assuming that a problem is hard for randomly chosen instances, lattice-based cryptosystems merely require the existence of a single hard instance, i.e., hardness in the worst case. With such an additional "trust anchor", the resulting security guarantees are much more plausible. Quite recently, we have seen an increased interest in lattice-based cryptography with many striking results. In this thesis, we are particularly interested in signature schemes, which provide a supporting pillar for today's economy. While we have seen basic signature schemes from lattices, e.g., (Gentry, Peikert, Vaikuntanathan 2008), (Lyubashevsky, Micciancio 2008), (Lyubashevsky 2009), or (Cash, Hofheinz, Kiltz, Peikert 2009), there are hardly any results dealing with the specific needs of applications, where ordinary signatures often fall too short. In this thesis, we build upon the above results and equip them with additional features, motivated by an exemplary selection of application scenarios. Hence, we demonstrate the great versatility of lattices in cryptography. In particular, we facilitate privacy-friendly electronic elections, fair online contract signing, signature compression, secure signatures in the strongest sense, as well as identity-based primitives. As far as possible, we avoid simplifying assumptions, such as the random oracle model. We believe that our techniques can be transferred to other application scenarios as well. Independently of the these results, we discuss the practical hardness of lattice problems and provide a framework for estimating the security of essentially all modern lattice-based cryptography.

DOI
10.26083/tuprints-00002393

Related papers

Towards Efficient Lattice-Based Cryptography

Richard Lindner

One essential quest in cryptography is the search for hard instances of a given computational problem that is known to be hard in the worst-case. In lattice cryptography we are in the unique situation that we have found a way of picking random instances which are at least as hard as well-studied lattice problems in the worst-case. At the same time, no attack running in subexponential time is known to break these problems, even for an adversary using quantum computers. Virtually all public-key schemes in use today are subject to such attacks, and the development of quantum computers is actively pursued, so it is prudent to investigate lattice-based alternatives. There are two fundamental open problems in lattice cryptography today and this thesis contributes to solving them. First, there exists a widely used efficiency improvement that allows for trapdoors whose asymptotic keysize and evaluation time are both quasilinear in the dimension of an associated lattice. This is accomplished by restricting oneself to lattices with special structure, so-called ideal lattices. This entails the use of newer security assumptions, but these have not been analyzed thoroughly so far. We start this work by comparing the class of ideal lattice problems with its general counterpart in terms of size. Affirming folklore, we find the number of restricted instances among all instances to be asymptotically negligible for those classes of lattices suggested for practical use. The second open problem is that while the connection to worst-case problems is well understood, the practical hardness of the related average-case problems is not. Specifically, there have been parameters suggested for practical usage, where current lattice basis reduction algorithms can solve these worst-case problems, but the related average-case problems, which these are reduced to and which represent the basis of practical security of the cryptosystems, are completely infeasible. In most cases, this lack of understanding has lead either to a very conservative choice of parameters, or none at all. This in turn makes it impossible for the resulting lattice schemes to compete with their counterparts based on other paradigms. We further the understanding of this practical security and at the same time improve the efficiency of several common related cryptographic schemes. Among other things, we find that for the SWIFFT compression function, solving certain problems closely related to finding collisions is easier than previously thought and we suggest efficient replacement parameters. We propose a novel zero-knowledge identification scheme that, to our knowledge, beats all competing post-quantum schemes, even those based on other paradigms. Possibly most important, we help to tighten the efficiency gap between lattice encryption schemes that are provably secure and the acclaimed ad-hoc encryption scheme NTRU. This is done by unifying many recent developments into a new provably secure design and providing a comprehensive analysis of practical security, which together results in a great leap of efficiency.

•Jan 1, 2011•0 citations

Practical Lattice-Based Digital Signature Schemes

James Howe, Thomas Pöppelmann, Maire P. O'Neill +2 more

Digital signatures are an important primitive for building secure systems and are used in most real-world security protocols. However, almost all popular signature schemes are either based on the factoring assumption (RSA) or the hardness of the discrete logarithm problem (DSA/ECDSA). In the case of classical cryptanalytic advances or progress on the development of quantum computers, the hardness of these closely related problems might be seriously weakened. A potential alternative approach is the construction of signature schemes based on the hardness of certain lattice problems that are assumed to be intractable by quantum computers. Due to significant research advancements in recent years, lattice-based schemes have now become practical and appear to be a very viable alternative to number-theoretic cryptography. In this article, we focus on recent developments and the current state of the art in lattice-based digital signatures and provide a comprehensive survey discussing signature schemes with respect to practicality. Additionally, we discuss future research areas that are essential for the continued development of lattice-based cryptography.

ACM Transactions on Embedded Computing Systems•Apr 21, 2015•59 citations

On the Design and Improvement of Lattice-based Cryptosystems

Rachid El Bansarkhani

Digital signatures and encryption schemes constitute arguably an integral part of cryptographic schemes with the goal to meet the security needs of present and future private and business applications. However, almost all public key cryptosystems applied in practice are put at risk due to its vulnerability to quantum attacks as a result of Shor's quantum algorithm. The magnitude of economic and social impact is tremendous inherently asking for alternatives replacing classical schemes in case large-scale quantum computers are built. Lattice-based cryptography emerged as a powerful candidate attracting lots of attention not only due to its conjectured resistance against quantum attacks, but also because of its unique security guarantee to provide worst-case hardness of average-case instances. Hence, the requirement of imposing further assumptions on the hardness of randomly chosen instances disappears, resulting in more efficient instantiations of cryptographic schemes. The best known lattice attack algorithms run in exponential time. In this thesis we contribute to a smooth transition into a world with practically efficient lattice-based cryptographic schemes. This is indeed accomplished by designing new algorithms and cryptographic schemes as well as improving existing ones. Our contributions are threefold. First, we construct new encryption schemes that fully exploit the error term in LWE instances. To this end, we introduce a novel computational problem that we call Augmented LWE (A-LWE), differing from the original LWE problem only in the way the error term is produced. In fact, we embed arbitrary data into the error term without changing the target distributions. Following this, we prove that A-LWE instances are indistinguishable from LWE samples. This allows to build powerful encryption schemes on top of the A-LWE problem that are simple in its representations and efficient in practice while encrypting huge amounts of data realizing message expansion factors close to 1. This improves, to our knowledge, upon all existing encryption schemes. Due to the versatility of the error term, we further add various security features such as CCA and RCCA security or even plug lattice-based signatures into parts of the error term, thus providing an additional mechanism to authenticate encrypted data. Based on the methodology to embed arbitrary data into the error term while keeping the target distributions, we realize a novel CDT-like discrete Gaussian sampler that beats the best known samplers such as Knuth-Yao or the standard CDT sampler in terms of running time. At run time the table size amounting to 44 elements is constant for every discrete Gaussian parameter and the total space requirements are exactly as large as for the standard CDT sampler. Further results include a very efficient inversion algorithm for ring elements in special classes of cyclotomic rings. In fact, by use of the NTT it is possible to efficiently check for invertibility and deduce a representation of the corresponding unit group. Moreover, we generalize the LWE inversion algorithm for the trapdoor candidate of Micciancio and Peikert from power of two moduli to arbitrary composed integers using a different approach. In the second part of this thesis, we present an efficient trapdoor construction for ideal lattices and an associated description of the GPV signature scheme. Furthermore, we improve the signing step using a different representation of the involved perturbation matrix leading to enhanced memory usage and running times. Subsequently, we introduce an advanced compression algorithm for GPV signatures, which previously suffered from huge signature sizes as a result of the construction or due to the requirement of the security proof. We circumvent this problem by introducing the notion of public and secret randomness for signatures. In particular, we generate the public portion of a signature from a short uniform random seed without violating the previous conditions. This concept is subsequently transferred to the multi-signer setting which increases the efficiency of the compression scheme in presence of multiple signers. Finally in this part, we propose the first lattice-based sequential aggregate signature scheme that enables a group of signers to sequentially generate an aggregate signature of reduced storage size such that the verifier is still able to check that each signer indeed signed a message. This approach is realized based on lattice-based trapdoor functions and has many application areas such as wireless sensor networks. In the final part of this thesis, we extend the theoretical foundations of lattices and propose new representations of lattice problems by use of Cauchy integrals. Considering lattice points as simple poles of some complex functions allows to operate on lattice points via Cauchy integrals and its generalizations. For instance, we can deduce for the one-dimensional and two-dimensional case simple expressions for the number of lattice points inside a domain using trigonometric or elliptic functions.

•Jan 1, 2015•0 citations

Lattice-based digital signatures

Vadim Lyubashevsky

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.

National Science Review•Apr 28, 2021•9 citations

On the Security of Lattice-Based Signature Schemes in a Post-Quantum World

Nina Bindel

Digital signatures are indispensable for security on the Internet, because they guarantee authenticity, integrity, and non-repudiation, of namely e-mails, software updates, and in the Transport Layer Security (TLS) protocol which is used for secure data transfer, for example. Most signature schemes that are currently in use such as the RSA signature scheme, are considered secure as long as the integer factorization problem or the discrete logarithm (DL) problem are computationally hard. At present, no algorithms have yet been found to solve these problems on conventional computers in polynomial time. However, in 1997, Shor published a polynomial-time algorithm that uses quantum computation to solve the integer factorization and the DL problem. In particular, this means that RSA signatures are considered broken as soon as large-scale quantum computers exist. Due to significant advances in the area of quantum computing, it is reasonable to assume that within 20 years, quantum computers that are able to break the RSA scheme, could exist. In order to maintain authenticity, integrity, and non-repudiation of data, cryptographic schemes that cannot be broken by quantum attacks are required. In addition, these so-called post-quantum secure schemes should be sufficiently efficient to be suitable for all established applications. Furthermore, solutions enabling a timely and secure transition from classical to post-quantum schemes are needed. This thesis contributes to the above-mentioned transition. In this thesis, we present the two lattice-based digital signature schemes TESLA and qTESLA, whereby lattice-based cryptography is one of five approaches to construct post-quantum secure schemes. Furthermore, we prove that our signature schemes are secure as long as the so-called Learning With Errors (LWE) problem is computationally hard to solve. It is presumed that even quantum computers cannot solve the LWE problem in polynomial time. The security of our schemes is proven using security reductions. Since our reductions are tight and explicit, efficient instantiations are possible that provably guarantee a selected security level, as long as the corresponding LWE instance provides a certain hardness level. Since both our reductions (as proven in the quantum random oracle model) and instantiations, take into account quantum attackers, TESLA and qTESLA are considered post-quantum secure. Concurrently, the run-times for generating and verifying signatures of qTESLA are similar (or faster) than those of the RSA scheme. However, key and signature sizes of RSA are smaller than those of qTESLA. In order to protect both the theoretical signature schemes and their implementations against attacks, we analyze possible vulnerabilities against implementation attacks. In particular, cache-side-channel attacks resulting from observing the cache behavior and fault attacks, which recover secret information by actively disrupting the execution of an algorithm are focused. We present effective countermeasures for each implementation attack we found. Our analyses and countermeasures also influence the design and implementation of qTESLA. Although our schemes are considered (post-quantum) secure according to state-of-the-art LWE attacks, cryptanalysis of lattice-based schemes is still a relatively new field of research in comparison to RSA schemes. Hence, there is a lack of confidence in the concrete instantiations and their promised security levels. However, due to developments within the field of quantum computers, a transition to post-quantum secure solutions seems to be more urgently required than ever. To solve this dilemma, we present an approach to combine two schemes, e.g., qTESLA and the RSA signature scheme, so that the combination is secure as long as one of the two combined schemes is secure. We present several of such combiners to construct hybrid signature schemes and hybrid key encapsulation mechanisms to ensure both authenticity and confidentiality in our Public-Key Infrastructure (PKI). Lastly, we also demonstrate how to apply the resulting hybrid schemes in standards such as X.509 or TLS. To summarize, this work presents post-quantum secure candidates which can, using our hybrid schemes, add post-quantum security to the current classical security in our PKI.

•Jan 1, 2018•0 citations

Lattice-based Blind Signatures

Markus Rückert

Motivated by the need to have secure blind signatures even in the presence of quantum computers, we present two efficient blind signature schemes based on hard worst-case lattice problems. Both schemes are provably secure in the random oracle model and unconditionally blind. The first scheme is based on preimage samplable functions that were introduced at STOC 2008 by Gentry, Peikert, and Vaikuntanathan. The scheme is stateful and runs in 3 moves. The second scheme builds upon the PKC 2008 identification scheme of Lyubashevsky. It is stateless, has 4 moves, and its security is based on the hardness of worst-case problems in ideal lattices.

Dagstuhl Seminar Proceedings•Jan 1, 2009•1 citation
Building cryptographic schemes upon as many fundamentally different hard problems as possible, seems to be the best way to hedge against future threats such as quantum computers. Being mainly based on the hardness of factoring and computing discrete logarithms, the present security landscape is at risk. In contrast, problems in lattices, such as finding short non-zero vectors, seem to withstand quantum computer attacks and the best known algorithms run in exponential time. In sharp contrast to other fields of cryptography, lattices admit a worst-case to average-case reduction (Ajtai 1996). Instead of assuming that a problem is hard for randomly chosen instances, lattice-based cryptosystems merely require the existence of a single hard instance, i.e., hardness in the worst case. With such an additional "trust anchor", the resulting security guarantees are much more plausible. Quite recently, we have seen an increased interest in lattice-based cryptography with many striking results. In this thesis, we are particularly interested in signature schemes, which provide a supporting pillar for today's economy. While we have seen basic signature schemes from lattices, e.g., (Gentry, Peikert, Vaikuntanathan 2008), (Lyubashevsky, Micciancio 2008), (Lyubashevsky 2009), or (Cash, Hofheinz, Kiltz, Peikert 2009), there are hardly any results dealing with the specific needs of applications, where ordinary signatures often fall too short. In this thesis, we build upon the above results and equip them with additional features, motivated by an exemplary selection of application scenarios. Hence, we demonstrate the great versatility of lattices in cryptography. In particular, we facilitate privacy-friendly electronic elections, fair online contract signing, signature compression, secure signatures in the strongest sense, as well as identity-based primitives. As far as possible, we avoid simplifying assumptions, such as the random oracle model. We believe that our techniques can be transferred to other application scenarios as well. Independently of the these results, we discuss the practical hardness of lattice problems and provide a framework for estimating the security of essentially all modern lattice-based cryptography.
One essential quest in cryptography is the search for hard instances of a given computational problem that is known to be hard in the worst-case. In lattice cryptography we are in the unique situation that we have found a way of picking random instances which are at least as hard as well-studied lattice problems in the worst-case. At the same time, no attack running in subexponential time is known to break these problems, even for an adversary using quantum computers. Virtually all public-key schemes in use today are subject to such attacks, and the development of quantum computers is actively pursued, so it is prudent to investigate lattice-based alternatives. There are two fundamental open problems in lattice cryptography today and this thesis contributes to solving them. First, there exists a widely used efficiency improvement that allows for trapdoors whose asymptotic keysize and evaluation time are both quasilinear in the dimension of an associated lattice. This is accomplished by restricting oneself to lattices with special structure, so-called ideal lattices. This entails the use of newer security assumptions, but these have not been analyzed thoroughly so far. We start this work by comparing the class of ideal lattice problems with its general counterpart in terms of size. Affirming folklore, we find the number of restricted instances among all instances to be asymptotically negligible for those classes of lattices suggested for practical use. The second open problem is that while the connection to worst-case problems is well understood, the practical hardness of the related average-case problems is not. Specifically, there have been parameters suggested for practical usage, where current lattice basis reduction algorithms can solve these worst-case problems, but the related average-case problems, which these are reduced to and which represent the basis of practical security of the cryptosystems, are completely infeasible. In most cases, this lack of understanding has lead either to a very conservative choice of parameters, or none at all. This in turn makes it impossible for the resulting lattice schemes to compete with their counterparts based on other paradigms. We further the understanding of this practical security and at the same time improve the efficiency of several common related cryptographic schemes. Among other things, we find that for the SWIFFT compression function, solving certain problems closely related to finding collisions is easier than previously thought and we suggest efficient replacement parameters. We propose a novel zero-knowledge identification scheme that, to our knowledge, beats all competing post-quantum schemes, even those based on other paradigms. Possibly most important, we help to tighten the efficiency gap between lattice encryption schemes that are provably secure and the acclaimed ad-hoc encryption scheme NTRU. This is done by unifying many recent developments into a new provably secure design and providing a comprehensive analysis of practical security, which together results in a great leap of efficiency.
Digital signatures are an important primitive for building secure systems and are used in most real-world security protocols. However, almost all popular signature schemes are either based on the factoring assumption (RSA) or the hardness of the discrete logarithm problem (DSA/ECDSA). In the case of classical cryptanalytic advances or progress on the development of quantum computers, the hardness of these closely related problems might be seriously weakened. A potential alternative approach is the construction of signature schemes based on the hardness of certain lattice problems that are assumed to be intractable by quantum computers. Due to significant research advancements in recent years, lattice-based schemes have now become practical and appear to be a very viable alternative to number-theoretic cryptography. In this article, we focus on recent developments and the current state of the art in lattice-based digital signatures and provide a comprehensive survey discussing signature schemes with respect to practicality. Additionally, we discuss future research areas that are essential for the continued development of lattice-based cryptography.
Digital signatures and encryption schemes constitute arguably an integral part of cryptographic schemes with the goal to meet the security needs of present and future private and business applications. However, almost all public key cryptosystems applied in practice are put at risk due to its vulnerability to quantum attacks as a result of Shor's quantum algorithm. The magnitude of economic and social impact is tremendous inherently asking for alternatives replacing classical schemes in case large-scale quantum computers are built. Lattice-based cryptography emerged as a powerful candidate attracting lots of attention not only due to its conjectured resistance against quantum attacks, but also because of its unique security guarantee to provide worst-case hardness of average-case instances. Hence, the requirement of imposing further assumptions on the hardness of randomly chosen instances disappears, resulting in more efficient instantiations of cryptographic schemes. The best known lattice attack algorithms run in exponential time. In this thesis we contribute to a smooth transition into a world with practically efficient lattice-based cryptographic schemes. This is indeed accomplished by designing new algorithms and cryptographic schemes as well as improving existing ones. Our contributions are threefold. First, we construct new encryption schemes that fully exploit the error term in LWE instances. To this end, we introduce a novel computational problem that we call Augmented LWE (A-LWE), differing from the original LWE problem only in the way the error term is produced. In fact, we embed arbitrary data into the error term without changing the target distributions. Following this, we prove that A-LWE instances are indistinguishable from LWE samples. This allows to build powerful encryption schemes on top of the A-LWE problem that are simple in its representations and efficient in practice while encrypting huge amounts of data realizing message expansion factors close to 1. This improves, to our knowledge, upon all existing encryption schemes. Due to the versatility of the error term, we further add various security features such as CCA and RCCA security or even plug lattice-based signatures into parts of the error term, thus providing an additional mechanism to authenticate encrypted data. Based on the methodology to embed arbitrary data into the error term while keeping the target distributions, we realize a novel CDT-like discrete Gaussian sampler that beats the best known samplers such as Knuth-Yao or the standard CDT sampler in terms of running time. At run time the table size amounting to 44 elements is constant for every discrete Gaussian parameter and the total space requirements are exactly as large as for the standard CDT sampler. Further results include a very efficient inversion algorithm for ring elements in special classes of cyclotomic rings. In fact, by use of the NTT it is possible to efficiently check for invertibility and deduce a representation of the corresponding unit group. Moreover, we generalize the LWE inversion algorithm for the trapdoor candidate of Micciancio and Peikert from power of two moduli to arbitrary composed integers using a different approach. In the second part of this thesis, we present an efficient trapdoor construction for ideal lattices and an associated description of the GPV signature scheme. Furthermore, we improve the signing step using a different representation of the involved perturbation matrix leading to enhanced memory usage and running times. Subsequently, we introduce an advanced compression algorithm for GPV signatures, which previously suffered from huge signature sizes as a result of the construction or due to the requirement of the security proof. We circumvent this problem by introducing the notion of public and secret randomness for signatures. In particular, we generate the public portion of a signature from a short uniform random seed without violating the previous conditions. This concept is subsequently transferred to the multi-signer setting which increases the efficiency of the compression scheme in presence of multiple signers. Finally in this part, we propose the first lattice-based sequential aggregate signature scheme that enables a group of signers to sequentially generate an aggregate signature of reduced storage size such that the verifier is still able to check that each signer indeed signed a message. This approach is realized based on lattice-based trapdoor functions and has many application areas such as wireless sensor networks. In the final part of this thesis, we extend the theoretical foundations of lattices and propose new representations of lattice problems by use of Cauchy integrals. Considering lattice points as simple poles of some complex functions allows to operate on lattice points via Cauchy integrals and its generalizations. For instance, we can deduce for the one-dimensional and two-dimensional case simple expressions for the number of lattice points inside a domain using trigonometric or elliptic functions.
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.
Digital signatures are indispensable for security on the Internet, because they guarantee authenticity, integrity, and non-repudiation, of namely e-mails, software updates, and in the Transport Layer Security (TLS) protocol which is used for secure data transfer, for example. Most signature schemes that are currently in use such as the RSA signature scheme, are considered secure as long as the integer factorization problem or the discrete logarithm (DL) problem are computationally hard. At present, no algorithms have yet been found to solve these problems on conventional computers in polynomial time. However, in 1997, Shor published a polynomial-time algorithm that uses quantum computation to solve the integer factorization and the DL problem. In particular, this means that RSA signatures are considered broken as soon as large-scale quantum computers exist. Due to significant advances in the area of quantum computing, it is reasonable to assume that within 20 years, quantum computers that are able to break the RSA scheme, could exist. In order to maintain authenticity, integrity, and non-repudiation of data, cryptographic schemes that cannot be broken by quantum attacks are required. In addition, these so-called post-quantum secure schemes should be sufficiently efficient to be suitable for all established applications. Furthermore, solutions enabling a timely and secure transition from classical to post-quantum schemes are needed. This thesis contributes to the above-mentioned transition. In this thesis, we present the two lattice-based digital signature schemes TESLA and qTESLA, whereby lattice-based cryptography is one of five approaches to construct post-quantum secure schemes. Furthermore, we prove that our signature schemes are secure as long as the so-called Learning With Errors (LWE) problem is computationally hard to solve. It is presumed that even quantum computers cannot solve the LWE problem in polynomial time. The security of our schemes is proven using security reductions. Since our reductions are tight and explicit, efficient instantiations are possible that provably guarantee a selected security level, as long as the corresponding LWE instance provides a certain hardness level. Since both our reductions (as proven in the quantum random oracle model) and instantiations, take into account quantum attackers, TESLA and qTESLA are considered post-quantum secure. Concurrently, the run-times for generating and verifying signatures of qTESLA are similar (or faster) than those of the RSA scheme. However, key and signature sizes of RSA are smaller than those of qTESLA. In order to protect both the theoretical signature schemes and their implementations against attacks, we analyze possible vulnerabilities against implementation attacks. In particular, cache-side-channel attacks resulting from observing the cache behavior and fault attacks, which recover secret information by actively disrupting the execution of an algorithm are focused. We present effective countermeasures for each implementation attack we found. Our analyses and countermeasures also influence the design and implementation of qTESLA. Although our schemes are considered (post-quantum) secure according to state-of-the-art LWE attacks, cryptanalysis of lattice-based schemes is still a relatively new field of research in comparison to RSA schemes. Hence, there is a lack of confidence in the concrete instantiations and their promised security levels. However, due to developments within the field of quantum computers, a transition to post-quantum secure solutions seems to be more urgently required than ever. To solve this dilemma, we present an approach to combine two schemes, e.g., qTESLA and the RSA signature scheme, so that the combination is secure as long as one of the two combined schemes is secure. We present several of such combiners to construct hybrid signature schemes and hybrid key encapsulation mechanisms to ensure both authenticity and confidentiality in our Public-Key Infrastructure (PKI). Lastly, we also demonstrate how to apply the resulting hybrid schemes in standards such as X.509 or TLS. To summarize, this work presents post-quantum secure candidates which can, using our hybrid schemes, add post-quantum security to the current classical security in our PKI.
Motivated by the need to have secure blind signatures even in the presence of quantum computers, we present two efficient blind signature schemes based on hard worst-case lattice problems. Both schemes are provably secure in the random oracle model and unconditionally blind. The first scheme is based on preimage samplable functions that were introduced at STOC 2008 by Gentry, Peikert, and Vaikuntanathan. The scheme is stateful and runs in 3 moves. The second scheme builds upon the PKC 2008 identification scheme of Lyubashevsky. It is stateless, has 4 moves, and its security is based on the hardness of worst-case problems in ideal lattices.